使用搜索算法解决八数码问题

本文最后更新于：2022年10月25日凌晨

人工智能导论作业记录。

一、问题描述与分析

八数码问题就是在一个大小为3×3的九宫格上,放置8块编号为1-8的木块，九宫格中有一个空格，周围(上下左右)的木块可以和空格交换位置。对于问题，给定一个初始状态，目标状态是期望达到1-8顺序排列的序列，并且空格在右下角，问题的实质就是寻找一个合法的移动序列。

不是每一个给定的初始状态都存在解，在分析之前，引入线性代数中的几个概念：

逆序数：在一个排列中，如果一对数字的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中序的总数就称为这个排列的逆序数。
奇排列：逆序数为奇数的排列称为奇排列
偶排列：逆序数为偶数的排列称为偶排列

使用线性代数理论可以得知，对于任意目标状态，只有初始状态的逆序数和目标状态的逆序数的奇偶性相同才有解(逆序数计算不包括0的逆序数)。

证明：

∵八数码问题每一个步骤都可以视作 0 的移动， 0 的移动至多有四个可能的方向又∵ 0 是序列中最小的数，序列的奇偶性不会跟随 0 的移动而改变且对于其余数字而言，要么与 0 互换，要么跨过两个数字和 0 互换 ∴逆序数的改变只有变化为 0、 -2、 +2 这三种情况又∵奇数±偶数=奇数，偶数±偶数=偶数 ∴序列在变换过程中，它的奇偶性不会发生改变 ∴如果初始序列和目标序列不是同为奇排列或者偶排列，那么这个八数码问题就是无解的。

以图中所给状态为例，初始状态的逆序数t=0+6+5+1+2+1+1=16，目标状态的逆序数t'=0，故有解。

二、深度优先遍历搜索(DFS)

2.1算法介绍

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止，属于盲目搜索。以下图为例，DFS方法首先从根节点1开始，其最终得到的遍历顺序是“1-2-3-4-5-6-7-8-9-10-11-12”。（假定左分枝和右分枝中优先选择左分枝）

我们将其应用于八数码问题的解决。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。前文提到DFS遍历的树是已经存在的，我们只需要按照规定的遍历方法就能完成遍历，而对于八数码问题，没有已经存在的路径供我们遍历，需要我们从初始状态向下延伸（也就是上下左右移动）才能构造出类似的树。

以上图为例。在使用DFS进行搜索时，每个状态都会按照一定的顺序进行上下左右移动（在上图中是下、左、右、上的顺序），一次移动后会产生一个新的状态，然后以新状态为起点继续按约定的顺序（例如先向下）移动。终止的条件是找到解或者达到深度界限。那么如果按照图中下、左、右、上的顺序搜索后的结果将会是最左边的一条路一直是优先向下移动，如果不能向下则依次会是左、右、上的一种。

2.2实验代码

//初始状态压入队列
    D_open.push(new borad(NULL, start, 0, INT_MAX - 1));
    printf("DFS：\n");
    while (!D_open.empty()) {
        //弹出一个状态
        borad *cur = D_open.top();
           D_open.pop();
        //if (cur->depth == 5) {
        //    break;
        //}
        //与目标状态的距离，为0即到达目标状态
        if (hn(cur->status, target) == 0) {
            printf("到达目标状态\nclose表大小为%d\n目标状态深度为%d\n\n", close.size(), cur->depth);
            //printans(cur);
            break;
        }
        //存放int格式的状态
        int intstatus = status2int(cur->status);
        //出现重复状态
        if (close.count(intstatus)) {
            continue;
        }
        //加入close表，表示已访问过
        close.insert(intstatus);

        //获得0的坐标
        int zeroindex = getindex(cur->status, 0);
        for (int i = 0; i < 4; i++) {
            //新建节点，复制当前棋盘状态，深度+1
            borad *temp = new borad(cur, cur->status, cur->depth + 1, INT_MAX - 1);
            //0向四个方向移动
            if (swapnum(zeroindex, zeroindex + go[i], temp->status)) {
                //移动成功
                D_open.push(temp);
            }
            else {
                //移动失败
                delete(temp);
            }
        }
    }

2.3实验结果

如图所示，深度优先算法在解决八数码问题时有一个致命缺点，就是必须设置一个深度界限，否则，搜索会一直沿着纵深方向发展，会一直无法搜索到解路径。即使加了限制条件，搜索到了解路径，解路径也不一定是最优解路径。

2.4实验总结

缺点：如果目标节点不在搜索进入的分支上，而该分支又是一个无穷分支,就得不到解,因此该算法是不完备的。
优点：如果目标节点在搜索进入的分支上，则可以较快得到解。

三、广度优先遍历搜索(BFS)

3.1算法介绍

广度优先搜索算法（英语：Breadth-First-Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。BFS是一种盲目搜索法，目的是系统地展开并检查图中的所有节点，以找寻结果。

BFS会先访问根节点的所有邻居节点，然后再依次访问邻居节点的邻居节点，直到所有节点都访问完毕。在具体的实现中，使用open和closed两个表，open是一个队列，每次对open进行一次出队操作（并放入closed中），并将其邻居节点进行入队操作。直到队列为空时即完成了所有节点的遍历。closed表在遍历树时其实没有用，因为子节点只能从父节点到达。但在进行图的遍历时，一个节点可能会由多个节点到达，所以此时为了防止重复遍历应该每次都检查下一个节点是否已经在closed中了。依旧以下图为例，BFS方法首先从根节点1开始，其最终得到的遍历顺序是“1-2-7-8-3-6-9-12-4-5-10-11”。可以看出来BFS进行遍历时是一层一层的搜索的。

在应用BFS算法进行八数码问题搜索时需要open和closed两个表。首先将初始状态加入open队列，然后进行出队操作并放入closed中，对出队的状态进行扩展（所谓扩展也就是找出其上下左右移动后的状态），将扩展出的状态加入队列，然后继续循环出队-扩展-入队的操作，直到找到解为止。在上图这个例子中，红圈里的数字是遍历顺序。当找到解时一直往前找父节点即可找出求解的移动路线。

3.2实验代码

//初始状态压入队列
    B_open.push(new borad(NULL, start, 0, INT_MAX - 1));
    printf("BFS：\n");
    while (!B_open.empty()) {
        //弹出一个状态
        borad* cur = B_open.front();
        B_open.pop();
        //与目标状态的距离，为0即到达目标状态
        if (hn(cur->status, target) == 0) {
            printf("到达目标状态\nclose表大小为%d\n目标状态深度为%d\n\n", close.size(), cur->depth);
            //printans(cur);
            break;
        }
        //存放int格式的状态
        int intstatus = status2int(cur->status);
        //出现重复状态
        if (close.count(intstatus)) {
            continue;
        }
        //加入close表，表示已访问过
        close.insert(intstatus);

        //获得0的坐标
        int zeroindex = getindex(cur->status, 0);
        for (int i = 0; i < 4; i++) {
            //新建节点，复制当前棋盘状态，深度+1
            borad* temp = new borad(cur, cur->status, cur->depth + 1, INT_MAX - 1);
            //0向四个方向移动
            if (swapnum(zeroindex, zeroindex + go[i], temp->status)) {
                //移动成功
                B_open.push(temp);
            }
            else {
                //移动失败
                delete(temp);
            }
        }
    }
    //清空close表
    close.clear();

3.3实验结果

如图所示，广度优先算法成功找到了深度为22的最优解，但是close表是DFS中深度46312产生的大小为47788的close表的两倍多，由于𝐵𝐹𝑆算法进行的是盲目的搜索，没有考虑代价，而且利用了空间换取时间的策略，故空间也相对会有更大的复杂度。

3.4实验总结

缺点：当目标节点距离初始节点较远时会产生许多无用的节点，搜索效率低，只能适用于到达目标结点步数较少的情况。
优点：只要问题有解，则总可以得到解，而且是最短路径的解。

四、A*算法实现八数码问题

4.1算法介绍

**A*搜索算法**（A* search algorithm）是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法，也是许多其他问题的常用启发式算法。该算法综合了最良优先搜索和Dijkstra算法的优点：在进行启发式搜索提高算法效率的同时，可以保证找到一条最优路径（基于评估函数）。

在A*算法中，一个结点位置的好坏用估价函数来对它进行评估：

\[ f{}'\left ( n \right )=g{}'\left ( n \right )+h{}'\left ( n \right ) \]

这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值(也称为最小耗费或最小代价)，h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的，因而实际上使用的是如下估价函数：

\[ f\left ( n \right )=g\left ( n \right )+h\left ( n \right ) \]

这个公式遵循以下特性：

如果g(n)为0，即只计算任意顶点n到目标的评估函数h(n)，而不计算起点到顶点n的距离，则算法转化为使用贪心策略的最良优先搜索，速度最快，但可能得不出最优解；
如果h(n)不大于顶点n到目标顶点的实际距离，则一定可以求出最优解，而且h(n)越小，需要计算的节点越多，算法效率越低，常见的评估函数有——欧几里得距离、曼哈顿距离、切比雪夫距离；
如果h(n)为0，即只需求出起点到任意顶点n的最短路径g(n)，而不计算任何评估函数h(n)，则转化为单源最短路径问题，即Dijkstra算法，此时需要计算最多的顶点；

其中，g(n)是从初始结点到节点n的实际代价，h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。用f(n)作为f'(n)的近似，也即用g(n)代替g'(n)，h(n)代替h'(n)。这样必须满足两个条件：

g(n)≥g'(n)(大多数情况下都是满足的，可以不用考虑)，且f必须保持单调递增；
h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)≤h'(n)。（可以证明应用这样的估价函数可以找到最短路径）

4.2实验代码

//初始状态压入队列
    printf("A* Fn=Gn+Hn：\n");
    while (!A_open.empty()) {
        //弹出一个状态
        borad* cur = A_open.top();
        A_open.pop();
        //hn=Fn-depth为与目标状态的曼哈顿距离，为0即到达目标状态
        if (cur->Fn - cur->depth == 0) {
            printf("到达目标状态\nclose表大小为%d\n目标状态深度为%d\n\n", close.size(), cur->depth);
            //printans(cur);
            break;
        }
        //存放int格式的状态
        int intstatus = status2int(cur->status);
        //出现重复状态
        if (close.count(intstatus)) {
            continue;
        }
        //加入close表，表示已访问过
        close.insert(intstatus);
        //获得0的坐标
        int zeroindex = getindex(cur->status, 0);
        for (int i = 0; i < 4; i++) {
            //新建节点，复制当前棋盘状态，深度+1
            borad* temp = new borad(cur, cur->status, cur->depth + 1, 0);
            //0向四个方向移动
            if (swapnum(zeroindex, zeroindex + go[i], temp->status)) {
                //移动成功
                //计算启发函数值，并更新节点
                temp->Fn = temp->depth + hn(temp->status, target);
                //加入A_open表
                A_open.push(temp);
            }
            else {
                //移动失败
                delete(temp);
            }
        }
    }
    //清空close表
    close.clear();

4.3实验结果

如图所示，A*搜索算法在解决八数码问题时取得了最优的结果，无论是时间复杂度还是空间复杂度都得到了极大的优化。但是𝐴∗算法作为一种预测算法，不能保证解为最优解。

4.4实验总结

优点：A*算法在绝大多数的情况下，在性能方面都远远优与DFS和BFS。算法的主要运行性能，取决于估价函数f的选取。
缺点：由于算法本身的特点，因此根据估价函数找到的解路径不一定是最优解路径。

五、效率比较及优缺点

5.1概念

首先给出几个用来进行效率比价的变量：

深度(D)：从初始节点到达目标的路径深度；
时间(T)：搜索程序运行的时间,单位毫秒(ms)；
状态数(N)：整个过程中生成的状态总数；
外显率(P)：搜索工程中,从初始节点向目标节点进行搜索的区域的宽度。

其中时间使用C标准库函数 clock_t clock(void) 计算获得，返回三个算法程序执行起，处理器时钟所使用的时间。为了获取 CPU 所使用的秒数，必须除以 CLOCKS_PER_SEC。而外显率定义为以下公式计算获得：

\[ P=\frac{D}{N},P\in \left( 0,1\right] \]

5.2 实验数据分析

数据说明：

环境为Windows系统，语言为C++，使用clock()函数输出算法时间；
目标状态1 2 3 4 5 6 7 8 0；
由于运行时间受电脑影响很大，具有一定的随机性，因而每个状态执行3次,取平均数作为最终结果时间。

以下为题目所给初始状态产生的数据：

	深度D	时间T	状态数N	外显率P
DFS	46312	0.295000	47788	0.969113
BFS	22	0.793000	102868	0.000213
A*	22	0.005000	503	0.043737

以下为随机初始状态产生的数据：

状态数N	DFS	BFS	A*
1	37809	60897	1114
2	13571	129921	1289
3	39006	36948	926
4	56982	38459	182
5	101524	23754	610
6	62529	85828	1175
7	119230	43684	750
8	72091	129811	2492
9	68716	40819	393
10	128887	159858	6852

深度D	DFS	BFS	A*
1	36756	20	20
2	13268	24	24
3	37943	19	19
4	55007	19	19
5	95102	18	20
6	60172	22	22
7	108378	20	20
8	69118	24	24
9	66096	20	20
10	113307	25	27

时间T	DFS	BFS	A*
1	0.226	0.444	0.011
2	0.079	1.026	0.012
3	0.231	0.277	0.01
4	0.347	0.291	0.002
5	0.675	0.176	0.006
6	0.372	0.665	0.011
7	0.749	0.321	0.007
8	0.429	0.997	0.024
9	0.439	0.302	0.003
10	0.796	1.367	0.068

外显率P	DFS	BFS	A*
1	0.000972	0.000328	0.017953
2	0.000978	0.000185	0.018619
3	0.000973	0.000514	0.020518
4	0.000965	0.000494	0.104396
5	0.000937	0.000758	0.032787
6	0.000962	0.000256	0.018723
7	0.000909	0.000458	0.026667
8	0.000959	0.000185	0.009631
9	0.000962	0.00049	0.050891
10	0.000879	0.000156	0.00394

5.3研究结论

通过研究，可得结论如下：

DFS搜索效率受深度影响很大，由于深度界限设置得很大，故搜索结点冗余多、速度慢；
BFS找到的一定是最优解，但是在算法效率上，不一定比DFS好，且远远不如A*算法，同时BFS在搜索深度较深时，产生的冗余结点较多；
A*算法在效率上相对最优，时间和空间上都比DFS和BFS更优，但缺点是，找到的解不一定是最优解。

六、参考文献

[1]付宏杰,王雪莹,周健,周孙静,朱珠,张俊余.八数码问题解法效率比较及改进研究[J].软件导刊,2016,15(09):41-45.

[2]StuartJ.Russell,PeterNorvig. 人工智能:一种现代的方法(第3版)[J]. 计算机教育, 2011(15):68-68.

[3]Thomas,H.Cormen,Charles,E.Leiserson,Ronald,L.Rivest,Clifford,Stein,殷建平,徐云,王刚,刘晓光,苏明,邹恒明,王宏志. 算法导论(原书第3版)[J]. 计算机教育(10期):51-51.

七、完整代码

#include <queue>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <time.h>
#include <math.h>
#include <climits>
using namespace std;

struct borad {
    int status[9];//status[0]到status[8]表示3X3的矩阵，0表示空格
    int depth;//深度
    int Fn;//启发函数值，Fn = depth + hn即深度加曼哈顿距离
    borad* pre;//父指针，指向移动前的棋盘状态
    borad() : pre(0), status(), depth(0), Fn(INT_MAX - 1) {
        for (int j = 0; j < 9; j++) {
            status[j] = j;
        }
    }
    borad(borad* x, int i[9], int y, int z) : pre(x), depth(y), Fn(z) {
        for (int j = 0; j < 9; j++) {
            status[j] = i[j];
        }
    }
};

//优先队列自定义排序规则，升序
struct cmp {
    bool operator() (const borad* a, const borad* b) {
        return a->Fn > b->Fn;
    }
};

bool swapnum(int a, int b, int* status);//交换元素
int getindex(int* status, int num);//获得元素在棋盘上的一维坐标
void print(int* status);//打印棋盘
int hn(int* status, int* target);//当前状态与目标状态的曼哈顿距离
void printans(borad* cur);//打印解法，回溯
int status2int(int* status);//棋盘状态转为int格式
int reversesum(int* status);//计算逆序数之和
int* randstatus(int* target);//获得随机初始状态

int main() {
    clock_t start_t, end_t;
    double total_t;
    int go[4] = { -1,1,-3,3 };//四个移动方向
    int start[9] = { 1,8,7,3,0,5,4,6,2 };//初始状态
    int target[9] = { 1,2,3,4,5,6,7,8,0 };//目标状态
    //int* start;//随机初始状态
    //生成随机初始状态
    //start = randstatus(target);
    stack<borad*> D_open;//DFS的open表，使用栈，深度大的在表头
    queue<borad*> B_open;//BFS的open表，使用队列，深度小的在表头
    priority_queue<borad*, vector<borad*>, cmp> A_open;//A*的open表，使用优先队列，启发函数值小的元素在表头
    unordered_set<int> close;//close表，存放已访问过的状态，元素为状态的int格式
    //例：{ 1,2,3,8,0,4,7,6,5 }==》123804765(int)
    //{ 0,1,3,8,2,4,7,6,5 }==》13824765(int)


    A_open.push(new borad(NULL, start, 0, INT_MAX - 1));
    borad* temp = A_open.top();
    printf("初始状态：");
    print(temp->status);
    printf("目标状态：");
    print(target);

    start_t = clock();
    //--------------------------------------------start-A*-------- Fn=Gn+Hn -----------------------------//
    //初始状态压入队列
    printf("A* Fn=Gn+Hn：\n");
    while (!A_open.empty()) {
        //弹出一个状态
        borad* cur = A_open.top();
        A_open.pop();
        //hn=Fn-depth为与目标状态的曼哈顿距离，为0即到达目标状态
        if (cur->Fn - cur->depth == 0) {
            printf("到达目标状态\nclose表大小为%ld\n目标状态深度为%d\n", close.size(), cur->depth);
            //printans(cur);
            break;
        }
        //存放int格式的状态
        int intstatus = status2int(cur->status);
        //出现重复状态
        if (close.count(intstatus)) {
            continue;
        }
        //加入close表，表示已访问过
        close.insert(intstatus);
        //获得0的坐标
        int zeroindex = getindex(cur->status, 0);
        for (int i = 0; i < 4; i++) {
            //新建节点，复制当前棋盘状态，深度+1
            borad* temp = new borad(cur, cur->status, cur->depth + 1, 0);
            //0向四个方向移动
            if (swapnum(zeroindex, zeroindex + go[i], temp->status)) {
                //移动成功
                //计算启发函数值，并更新节点
                temp->Fn = temp->depth + hn(temp->status, target);
                //加入A_open表
                A_open.push(temp);
            }
            else {
                //移动失败
                delete(temp);
            }
        }
    }
    //清空close表
    close.clear();
    //--------------------------------------------end-A*--------- Fn=Gn+Hn -------------------------//
    end_t = clock();
    //清空A_open
    while (!A_open.empty()) {
        A_open.pop();
    }
    total_t = ((double)end_t - (double)start_t) / CLOCKS_PER_SEC;
    printf("总时间：%f\n\n\n", total_t);
    start_t = clock();
    //--------------------------------------------start-BFS------------------------------------------//
    //初始状态压入队列
    B_open.push(new borad(NULL, start, 0, INT_MAX - 1));
    printf("BFS：\n");
    while (!B_open.empty()) {
        //弹出一个状态
        borad* cur = B_open.front();
        B_open.pop();
        //与目标状态的距离，为0即到达目标状态
        if (hn(cur->status, target) == 0) {
            printf("到达目标状态\nclose表大小为%ld\n目标状态深度为%d\n", close.size(), cur->depth);
            //printans(cur);
            break;
        }
        //存放int格式的状态
        int intstatus = status2int(cur->status);
        //出现重复状态
        if (close.count(intstatus)) {
            continue;
        }
        //加入close表，表示已访问过
        close.insert(intstatus);

        //获得0的坐标
        int zeroindex = getindex(cur->status, 0);
        for (int i = 0; i < 4; i++) {
            //新建节点，复制当前棋盘状态，深度+1
            borad* temp = new borad(cur, cur->status, cur->depth + 1, INT_MAX - 1);
            //0向四个方向移动
            if (swapnum(zeroindex, zeroindex + go[i], temp->status)) {
                //移动成功
                B_open.push(temp);
            }
            else {
                //移动失败
                delete(temp);
            }
        }
    }
    //清空close表
    close.clear();
    //--------------------------------------------end-BFS------------------------------------------//
    end_t = clock();
    total_t = ((double)end_t - (double)start_t) / CLOCKS_PER_SEC;
    printf("总时间：%f\n\n\n", total_t);
    start_t = clock();
    //--------------------------------------------start-DFS------------------------------------------//
    //初始状态压入队列
    D_open.push(new borad(NULL, start, 0, INT_MAX - 1));
    printf("DFS：\n");
    while (!D_open.empty()) {
        //弹出一个状态
        borad* cur = D_open.top();
        D_open.pop();
        //if (cur->depth == 5) {
        //    break;
        //}
        //与目标状态的距离，为0即到达目标状态
        if (hn(cur->status, target) == 0) {
            printf("到达目标状态\nclose表大小为%ld\n目标状态深度为%d\n", close.size(), cur->depth);
            //printans(cur);
            break;
        }
        //存放int格式的状态
        int intstatus = status2int(cur->status);
        //出现重复状态
        if (close.count(intstatus)) {
            continue;
        }
        //加入close表，表示已访问过
        close.insert(intstatus);

        //获得0的坐标
        int zeroindex = getindex(cur->status, 0);
        for (int i = 0; i < 4; i++) {
            //新建节点，复制当前棋盘状态，深度+1
            borad* temp = new borad(cur, cur->status, cur->depth + 1, INT_MAX - 1);
            //0向四个方向移动
            if (swapnum(zeroindex, zeroindex + go[i], temp->status)) {
                //移动成功
                D_open.push(temp);
            }
            else {
                //移动失败
                delete(temp);
            }
        }
    }
    //--------------------------------------------end-DFS------------------------------------------//
    end_t = clock();
    total_t = ((double)end_t - (double)start_t) / CLOCKS_PER_SEC;
    printf("总时间：%f\n", total_t);
    //delete(start);
    return 0;
}

//打印棋盘
void print(int* status) {
    for (int i = 0; i < 9; i++) {
        if (i % 3 == 0) {
            printf("\n");
        }
        printf("%d ", status[i]);

    }
    printf("\n\n");
}

//获得元素在棋盘上的一维坐标
int getindex(int* status, int num) {
    for (int i = 0; i < 9; i++) {
        if (status[i] == num) {
            return i;
        }
    }
    return -1;
}

//交换元素
bool swapnum(int a, int b, int* status) {
    if (b >= 0 && b <= 8 && (a / 3 == b / 3 || a % 3 == b % 3)) {
        swap(status[a], status[b]);
        return true;
    }
    else {
        return false;
    }
}

//当前状态与目标状态的曼哈顿距离
int hn(int* status, int* target) {
    //获得当前状态与目标状态的二维x，y坐标
    int x, y, xt, yt, it, h = 0;
    for (int i = 0; i < 9; i++) {
        x = i % 3;
        y = i / 3;
        it = getindex(target, status[i]);
        xt = it % 3;
        yt = it / 3;
        h += abs(x - xt) + abs(y - yt);
    }
    return h;
}

//打印解法，回溯
void printans(borad* cur) {
    vector<string> ans;
    while (cur) {
        ans.push_back(to_string(cur->status[0]) + to_string(cur->status[1]) + to_string(cur->status[2]) + "\n"
            + to_string(cur->status[3]) + to_string(cur->status[4]) + to_string(cur->status[5]) + "\n"
            + to_string(cur->status[6]) + to_string(cur->status[7]) + to_string(cur->status[8]));
        cur = cur->pre;
    }
    for (int i = ans.size() - 1; i >= 0; i--) {
        printf("%s\n ↓\n", ans[i].c_str());
    }
    printf("END\n\n");
}

//棋盘状态转为int格式
int status2int(int* status) {
    int res = 0;
    for (int i = 0, j = 8; i < 9; i++, j--) {
        res += status[i] * pow(10, j);
    }
    return res;
}

//计算逆序数之和
int reversesum(int* status) {
    int sum = 0;
    for (int i = 0; i < 9; i++) {
        if (status[i] != 0) {
            for (int j = 0; j < i; j++) {
                if (status[j] > status[i]) {
                    sum++;
                }
            }
        }
    }
    return sum;
}

//获得随机初始状态
int* randstatus(int* target) {
    int* start = new int[9]();
    unordered_map<int, int> nums;//记录已添加的数
    srand((int)time(0));
    int element, sum1, sum2;
    sum2 = reversesum(target);
    //根据初始状态与目标状态的逆序数之和（sum1、sum2）是否相等，判断初始状态是否有解，不相等（即无解）则重新生成初始状态
    do {
        for (int i = 0; i < 9; i++) {
            element = rand() % 9;
            while (nums[element]) {
                element = rand() % 9;
            }
            nums[element]++;
            start[i] = element;
        }
        //清空记录
        nums.clear();
        //计算逆序数之和
        sum1 = reversesum(start);
    } while (sum1 % 2 != sum2 % 2);
    return start;
}

#人工智能

使用搜索算法解决八数码问题

http://enderfga.cn/2021/10/19/8puzzle/

作者

Enderfga

发布于

2021年10月19日

许可协议

typora+picgo+coding高效写作上一篇

Texlive+VScode 下一篇