关于八数码问题，网上搜索一下就能有详细说明，在此不做赘述。
简单点说就是将类似下图所示的状态
通过与空格进行交换，达到类似如下所示的状态
在这个算法里空格当做数字 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;
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())
{
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);
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))
{
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
{
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);
}
}
}
}
}
|
完整源代码