C++ 解决八数码问题

C++ 解决八数码问题

十二月 27, 2018

关于八数码问题，网上搜索一下就能有详细说明，在此不做赘述。

简单点说就是将类似下图所示的状态

2 8 3
1 4
7 6 5

通过与空格进行交换，达到类似如下所示的状态

1 2 3
8 4
7 6 5

在这个算法里空格当做数字 0 处理。

算法整体思路

将每一个九宫格当做一个状态，每次移动一个数字就会生成一个新的状态，若新状态与最终状态相等，则表示解找到。

从初始状态开始，可构造一棵状态生成树，遍历这棵生成树找到目标状态即可。

注意：八数码问题不是始终有解的，只有初始状态的逆序数与终了状态的逆序数奇偶性相同才有解，否则无解，所以开始要做是否有解的判别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int getInversions(vector<int> num)
{// 求逆序数
    int count = 0;
    for (int i = 0; i < 9; i++)
    {
        if (num[i] == 0)
        {
            continue;
        }
        for (int j = i; j < 9; j++)
        {
            if (num[j] != 0 && num[i] > num[j])
            {
                count++;
            }
        }
    }
    return count;
}
bool hasSolution(vector<int> start, vector<int> end)
{// 判断逆序数奇偶性来决定是否有解
    int inverStart, inverEnd;
    inverStart = getInversions(start);
    inverEnd = getInversions(end);
    return (inverStart % 2 == inverEnd % 2);
}

宽度优先搜索（又称广度优先搜索），即 BFS

首先每一次的九宫格当做一个状态，即状态类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class state
{
  public:
    vector<int> num;
    int nowId, parentId;// 自身 id 及父状态 id，用于输出路径
    state(vector<int> num, int nowId, int parentId)
    {// 构造函数
        this->num = num;
        this->nowId = nowId;
        this->parentId = parentId;
    }
    bool operator==(const state &now) const
    {// 重载 == 运算符判断两个状态是否相等
        return isEqual(num, now.num);
    }
};
1
2
3
4
5
6
7
8
9
10
11
bool isEqual(vector<int> start, vector<int> end)
{
    for (int i = 0; i < 9; i++)
    {
        if (start[i] != end[i])
        {// 只要有一个数字不同即不相等
            return false;
        }
    }
    return true;
}

众所周知 BFS 算法需要借助一个队列实现：

1
2
3
queue<state> open;
vector<state> path;
map<vector<int>, bool> close;

open表即是状态队列，path表用于存储路径上的状态，close表用于判断一个状态是否被访问过。

BFS 算法函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int BFS(vector<int> start, vector<int> end)
{
    int id = 0, step = 0;
    vector<int> move = {-1, -3, 1, 3};// 代表数字分别向左、上、右、下移动
    open.push(state(start, id, id++));
    while (!open.empty())
    {// 当 open 表非空时取队列头元素进行判断，并将生成的子状态加入队列尾部
        state now = open.front();
        open.pop();
        path.push_back(now);
        close[now.num] = true;// 设置该状态已被访问
        if (isEqual(now.num, end))
        {
            return path.size();
        }
        int zeroL = zeroLocation(now.num);// 找到数字 0 所在的的位置
        int newLocation = 0;
        for (int i = 0; i < 4; i++)
        {
            newLocation = zeroL + move[i];
            if (newLocation > -1 && newLocation < 9 
            && !(newLocation == 2 && zeroL == 3) 
            && !(newLocation == 3 && zeroL == 2) 
            && !(newLocation == 5 && zeroL == 6) 
            && !(newLocation == 6 && zeroL == 5))
            {// 判断数字移动后是否越界
                swap(now.num[newLocation], now.num[zeroL]);// 对数字进行移动
                state newState = state(now.num, id++, now.nowId);
                swap(now.num[newLocation], now.num[zeroL]);
                if (isEqual(newState.num, end))
                {
                    path.push_back(newState);
                    return path.size();
                }
                if (!close.count(newState.num))
                {// 若该状态不在 close 表中，即未被访问过
                    open.push(newState);// 新状态入队列
                    step++;
                }
            }
        }
    }
}

完整源代码详见 GitHub

启发式搜索

启发式搜索 BFS 稍稍有些不同，主要在于启发式函数与启发式函数的选择。

启发式函数

其中 表示目标状态到当前状态的代价，用当前状态节点的深度表示。

表示当前状态到目标状态的估价，可以有很多选择，这里使用当前状态的位置与目标状态位置不同的数字个数表示。

这样每次就不必一次性扩展所有子节点，而是会尽量选择接近目标状态的节点去扩展。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int HX(vector<int> start, vector<int> end)
{
    int hX = 0;
    for (int i = 0; i < 9; i++)
    {
        if (start[i] != end[i])
        {
            hX++;
        }
    }
    return hX;
}
int FX(state &now)
{
    return now.hX + now.gX;
}

这次open表就无需使用队列来实现了

1
2
3
vector<state> open;
vector<state> path;
map<vector<int>, bool> close;

每次只需要从open表中取出 最小的状态节点进行子节点扩展即可。

启发式搜索主函数（大部分判断移动和扩展都与 BFS 算法相似）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int AStar(vector<int> start, vector<int> end)
{
    int id = 0;
    vector<int> move = {-3, -1, 3, 1};
    open.push_back(state(start, HX(start, end), 0, HX(start, end), id, id++));
    while (!open.empty())
    {
        auto min = min_element(open.begin(), open.end(), [](const state &x, const state &y)-> bool 
        {// 寻找 open 表中 f(x) 最小的状态
            return x.fX < y.fX;
        });
        state now = *min;
        open.erase(min);
        path.push_back(now);
        close[now.num] = true;
        if (isEqual(now.num, end))
        {
            return now.gX;
        }
        int zeroL = zeroLocation(now.num);
        int newLocation = 0;
        for (int i = 0; i < 4; i++)
        {
            newLocation = zeroL + move[i];
            if (newLocation > -1 && newLocation < 9 
            && !(newLocation == 2 && zeroL == 3) 
            && !(newLocation == 3 && zeroL == 2)
            && !(newLocation == 5 && zeroL == 6)
            && !(newLocation == 6 && zeroL == 5))
            {
                swap(now.num[newLocation], now.num[zeroL]);
                state newState = state(now.num, 0, now.gX + 1, HX(now.num, end), id++, now.nowId);
                swap(now.num[newLocation], now.num[zeroL]);
                newState.fX = FX(newState);
                if (isEqual(newState.num, end))
                {
                    path.push_back(newState);
                    return newState.gX;
                }
                if (!close.count(newState.num))
                {
                    open.push_back(newState);
                }
            }
        }
    }
}

完整源代码

  1. 1. 算法整体思路
  2. 2. 宽度优先搜索（又称广度优先搜索），即 BFS
  3. 3. 启发式搜索