对比A*算法和BFS算法解决八数码问题（C++）
程序员文章站
2024-01-08 13:26:52
...
代码实现参考博客:https://blog.csdn.net/lishang6257/article/details/79732420
一、A*算法
A*算法是一种启发式图搜索算法。对于通用图搜索过程进行如下限制，即为A*算法。
定义评估函数 f*(n)=g*(n)+h*(n)
其中，g*(n)表示从初始节点到当前节点的最短路径的代价，而对于同一问题h*(n)可以有多种设计方法，而不同的启发函数会对搜索的效率产生比较明显的影响。在本文中，对于常规A*算法使用不在目标位置的数码的数量作为h*(n)的定义方法。BFS（广度优先搜索方法）实际上是一种最差的A*算法，认为h*(n)=0。还可以以各个数码与目标位置距离的总和定义启发函数h*(n)。
二、八数码问题
在一个3*3的九宫格棋盘上，摆放有8个刻有数码1~8的将牌。棋盘中有一个空位没有放置将牌，可以通过将与空格相邻的将牌移动到空格上的方式改变八个将牌的位置和顺序。八数码问题就是要求给出将棋盘布局从初始状态转变为目标状态的步骤。（15数码、63数码问题等等都与此类似）
示例如下：
三、C++代码实现及详细注释
#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#define maxState 10000
#define N 3
using namespace std;
bool isEqual(int a[N][N][maxState], int b[N][N], int n)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (a[i][j][n] != b[i][j])
return false;
}
}
return true;
}
bool isEqual(int a[N][N], int b[N][N]) //检查两矩阵是否完全一致
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (a[i][j] != b[i][j])
return false;
}
}
return true;
}
int evalute(int state[N][N], int target[N][N]) //估价函数h-计算不在位的将牌个数
{
int num = 0; //num表示当前矩阵state中不在目标位置上的将牌个数
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
if (state[i][j] != target[i][j])
num++; //统计num
}
return num; //返回估价
}
void findBrack(int a[N][N], int x, int y)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (a[i][j] == 0)
{
x = i;
y = j;
return;
}
}
}
}
bool move(int a[N][N], int b[N][N], int dir)
{
//1 up 2 down 3 left 4 right
int x = 0, y = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
b[i][j] = a[i][j]; //将原矩阵复制以进行移动操作
if (a[i][j] == 0)
{
x = i;
y = j; //标记空格位置
}
}
}
if (x == 0 && dir == 1)
return false; //四条if语句排除四种不可能的移动方向
if (x == N - 1 && dir == 2)
return false; //返回false意指此种移动方式不可行，回到调用函数重新选择移动方向
if (y == 0 && dir == 3)
return false;
if (y == N - 1 && dir == 4)
return false;
if (dir == 1) //按照传入的dir将空格往相应的方向移动
{
b[x - 1][y] = 0;
b[x][y] = a[x - 1][y];
}
else if (dir == 2)
{
b[x + 1][y] = 0;
b[x][y] = a[x + 1][y];
}
else if (dir == 3)
{
b[x][y - 1] = 0;
b[x][y] = a[x][y - 1];
}
else if (dir == 4)
{
b[x][y + 1] = 0;
b[x][y] = a[x][y + 1];
}
else
return false;
return true; //移动空格成功返回true
}
void statecpy(int a[N][N][maxState], int b[N][N], int n)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
a[i][j][n] = b[i][j]; //将移动完的新矩阵复制到close表中，n可以表示第n步搜索结果
}
}
}
void getState(int a[N][N][maxState], int b[N][N], int n)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
b[i][j] = a[i][j][n];
}
}
}
void statecpy(int a[N][N], int b[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
a[i][j] = b[i][j]; //复制当前矩阵start
}
}
int checkAdd(int a[N][N][maxState], int b[N][N], int n)
{
for (int i = 0; i < n; i++)
{
if (isEqual(a, b, i))
return i; //若两矩阵相同则返回对应矩阵的编号
}
return -1;
}
int Astar(int a[N][N][maxState], int start[N][N], int target[N][N], int path[maxState])
{
bool visited[maxState] = {false}; //true表示矩阵已被遍历
int fitness[maxState] = {0};
int passLen[maxState] = {0};
int curpos[N][N];
statecpy(curpos, start);
int id = 0, Curid = 0;
fitness[id] = evalute(curpos, target);
statecpy(a, start, id++);
while (!isEqual(curpos, target)) //只要当前矩阵序列curpos与目标矩阵target不相同即执行while循环
{
for (int i = 1; i < 5; i++) //向四周找方向
{
int tmp[N][N] = {0};
if (move(curpos, tmp, i)) //依次按照上下左右顺序尝试移动空格
{
int state = checkAdd(a, tmp, id);
if (state == -1) //不添加到close表中
{
path[id] = Curid; //走到当前第id个节点实际已经走过的路径的花费
passLen[id] = passLen[Curid] + 1;
fitness[id] = evalute(tmp, target) + passLen[id]; //总花费估价
statecpy(a, tmp, id++); //将处理得到的新矩阵编号为id复制到open表中a中保存
}
else //添加到close表中
{
int len = passLen[Curid] + 1, fit = evalute(tmp, target) + len; //修改估价函数
if (fit < fitness[state])
{
path[state] = Curid;
passLen[state] = len;
fitness[state] = fit;
visited[state] = false;
} //若所得结果小于预期花费则修改多余部分的估价值，并将未遍历过的矩阵标记为false
}
}
}
visited[Curid] = true; //第curid个矩阵已被遍历过
int minCur = -1;
for (int i = 0; i < id; i++) //从open表中(visited值为false)寻找总估价函数fitness值最小的矩阵作为下一个带搜索节点
if (!visited[i] && (minCur == -1 || fitness[i] < fitness[minCur]))
minCur = i;
Curid = minCur; //Curid现在表示被选作下一个扩展节点的矩阵的编号
getState(a, curpos, Curid); //将被选中的矩阵复制给curpos
if (id == maxState)
return -1; //如果已经搜索节点数达到设定的maxState，则认为目标矩阵不可达，返回-1
}
return Curid; //已求得目标矩阵，返回最终矩阵的编号
}
int BFS(int a[N][N][maxState], int start[N][N], int target[N][N], int path[maxState])
{
bool visited[maxState] = {false}; //true表示矩阵已被遍历
int fitness[maxState] = {0};
int passLen[maxState] = {0};
int curpos[N][N];
statecpy(curpos, start);
int id = 0, Curid = 0;
//fitness[id] = evalute(curpos, target);
statecpy(a, start, id++);
while (!isEqual(curpos, target)) //只要当前矩阵序列curpos与目标矩阵target不相同即执行while循环
{
for (int i = 1; i < 5; i++) //向四周找方向
{
int tmp[N][N] = {0};
if (move(curpos, tmp, i)) //依次按照上下左右顺序尝试移动空格
{
int state = checkAdd(a, tmp, id);
if (state == -1) //不添加到close表中
{
path[id] = Curid; //走到当前第id个节点实际已经走过的路径的花费
passLen[id] = passLen[Curid] + 1;
fitness[id] = passLen[id]; //总花费估价
statecpy(a, tmp, id++); //将处理得到的新矩阵编号为id复制到open表中a中保存
}
else //添加到close表中
{
int len = passLen[Curid] + 1, fit = len; //修改估价函数
if (fit < fitness[state])
{
path[state] = Curid;
passLen[state] = len;
fitness[state] = fit;
visited[state] = false;
} //若所得结果小于预期花费则修改多余部分的估价值，并将未遍历过的矩阵标记为false
}
}
}
visited[Curid] = true; //第curid个矩阵已被遍历过
int minCur = -1;
for (int i = 0; i < id; i++) //从open表中(visited值为false)寻找总估价函数fitness值最小的矩阵作为下一个带搜索节点
if (!visited[i] && (minCur == -1 || fitness[i] < fitness[minCur]))
minCur = i;
Curid = minCur; //Curid现在表示被选作下一个扩展节点的矩阵的编号
getState(a, curpos, Curid); //将被选中的矩阵复制给curpos
if (id == maxState)
return -1; //如果已经搜索节点数达到设定的maxState，则认为目标矩阵不可达，返回-1
}
return Curid; //已求得目标矩阵，返回最终矩阵的编号
}
void show(int a[N][N][maxState], int n)
{
cout << "-------------------------------\n";
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cout << a[i][j][n] << " ";
}
cout << endl;
}
cout << "-------------------------------\n";
}
int calDe(int a[N][N])
{
int sum = 0;
for (int i = 0; i < N * N; i++)
{
for (int j = i + 1; j < N * N; j++)
{
int m, n, c, d;
m = i / N;
n = i % N;
c = j / N;
d = j % N;
if (a[c][d] == 0)
continue;
if (a[m][n] > a[c][d])
sum++;
}
}
return sum;
}
void autoGenerate(int a[N][N])
{
int maxMove = 50; //设置步数上限
srand((unsigned)time(NULL)); //生成随机数种子
int tmp[N][N];
while (maxMove--)
{ //随机移动空格五十步可以保证初始状态的矩阵序列不相同
int dir = rand() % 4 + 1; //dir取值范围1~4，代表空格移动的四个方向
if (move(a, tmp, dir))
statecpy(a, tmp); //打乱原目标矩阵的顺序以构造初始矩阵
}
}
void results_op(int res, int path[maxState], int a[N][N][maxState])
{
int shortest[maxState] = {0}, j = 0;
while (res != 0)
{
shortest[j++] = res;
res = path[res];
}
cout << "第 0 步" << endl;
show(a, 0);
for (int i = j - 1; i >= 0; i--)
{
cout << "第 " << j - i << " 步\n";
show(a, shortest[i]);
}
}
int main()
{
int a[N][N][maxState] = {0}; //存储每个节点矩阵，最多可存储maxState个
int start[N][N] = {1, 2, 3, 8, 0, 4, 7, 6, 5}; //指明八个数码元素的值及目标状态（将空格值认为0，则实际上是九个数码）
autoGenerate(start); //调用此函数随机打乱原矩阵顺序生成不确定的矩阵序列
int target[N][N] = {1, 2, 3, 8, 0, 4, 7, 6, 5}; //目标矩阵序列
int start_demo[N][N] = {0}, target_demo[N][N] = {0};
statecpy(start_demo, start);
statecpy(target_demo, target);
if (!(calDe(start) % 2 == calDe(target) % 2))
{
cout << "在此初始状态及目标序列情况下，无解\n";
system("pause");
return 0;
}
int path[maxState] = {0};
cout << "使用以不在目标位置的将牌个数的A*算法处理如下：" << endl;
int res = Astar(a, start, target, path);
if (res == -1)
{ //认为目标矩阵不可达
cout << "此次搜索已经搜索超过" << maxState << "个节点，认为目标矩阵不可达\n";
system("pause");
return 0;
}
results_op(res, path, a);
//下面进行BFS搜索，因为需要借用path数组，所以将其初始化为全零数组
for (int i = 0; i < maxState; i++)
{
path[0] = 0;
}
cout << "\n仅使用路径花费作为启发函数的A*算法(BFS)处理结果如下：" << endl;
res = BFS(a, start_demo, target_demo, path);
if (res == -1)
{ //认为目标矩阵不可达
cout << "此次搜索已经搜索超过" << maxState << "个节点，认为目标矩阵不可达\n";
system("pause");
exit(0);
}
results_op(res, path, a);
cout << endl;
system("pause");
return 0;
}
实验结果对比
(因为矩阵的初始状态是随机生成的,所以下面放了两种情况,一种是两种算法都能在有限步数内到达目标状态的情形,另一种是碰巧BFS搜索节点数超过预设值而找不到解的情形)
下面是A*算法能使用较少步骤找到解而BFS搜索节点数量超出预设值的情形
四、总结
此代码通过使用常规A*算法和BFS方法对初始状态相同的矩阵进行处理，对比发现常规BFS方法相比于A*算法更容易出现搜索节点数量过多的问题。对于启发函数的选取,启发性信息越强则搜索范围越小,需要遍历搜索的节点也越少,搜索效率会大大提高,但却不能保证一定能得到最优解;反之,启发性信息越弱,所需搜索的节点就越多,这样的搜索效率就会降低,但这样更可能保证获得最优解.
如果将h*(n)定义为当前节点中每个数码与其目标位置的距离总和,启发性效果会更好,所需搜索的节点数也会减少.