人工智能"/>
八数码问题——人工智能
实验二 八数码问题
一、实验目的
本实验课程是计算机、智能、物联网等专业学生的一门专业课程，通过实验，帮助学生更好地掌握人工智能相关概念、技术、原理、应用等；通过实验提高学生编写实验报告、总结实验结果的能力；使学生对智能程序、智能算法等有比较深入的认识。
1.掌握人工智能中涉及的相关概念、算法。
2.熟悉人工智能中的知识表示方法；
3.熟悉盲目搜索和启发式搜索算法的应用；
4.掌握问题表示、求解及编程实现。
5.掌握不同搜索策略的设计思想、步骤、性能。
二、基本要求
1.实验前，复习《人工智能》课程中的有关内容。
2.准备好实验数据。
3.编程要独立完成，程序应加适当的注释。
4.完成实验报告。
三、实验软件
使用C或C++（Visual studio）（不限制语言使用）。
四、实验内容：
1.在图1，33的方格棋盘上，摆放着1到8这八个数码，有1个方格是空。
图1
2.如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态（图1左）到目标状态（图1右）。
3.可自行设计初始状态。目标状态为数字从小到大按顺时针排列。
4.分别用广度优先搜索策略、深度优先搜索策略和启发式搜索算法（A算法）求解八数码问题；分析估价函数对启发式搜索算法的影响；探究各个搜索算法的特点。
五、实验程序组成：
（1）状态表示的数据结构：
初始状态记录在二维数组chess[3][3]中，后续每种变化记录在数组open[500][3][3]中，其中第一个参数表变化
（2）状态扩展规则的表示
初始状态记录在数组open[500][3][3]中
（3）使用的函数作用：
void init2(); //输入初始状态
void init(); //其他参数调整到初始状态
void show(int); //展示open[int]状态的图
int upmove(int,int); //状态图中的0向上移
int downmove(int,int); //状态图中的0向下移
int leftmove(int,int); //状态图中的0向左移
int rightmove(int, int); //状态图中的0向右移
bool check(int); //检查open[int]状态是否为最终态
void BFS(); //利用BFS算法求解
void DFS(); //利用DFS算法求解
int apprise(int); //估价函数
void A(); //利用A*算法求解
（4）实验中的部分代码
//BFS算法
void chessboard::BFS() { //默认排序：左上右下time = 0;time++;//开始利用算法求解int had = 0; //正在遍历的节点while (had<500) {//判断当前状态是否是最终态for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (!check(had))goto gg;else goto QWQ;gg://左移if (leftmove(had, time) == 1) {time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d1;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;break;d1:;}}//上移if (upmove(had, time) == 1) {time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d2;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;break;d2:;}} //右移if (rightmove(had, time) == 1){time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d3;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;break;d3:;}}//下移if (downmove(had, time) == 1){time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d4;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;break;d4:;}}had++;}
QWQ:for (int k = 0; k <= had; k++) {cout << "成功找到解决路径，如下:" << endl;cout << "第"<<k<<"步：" << endl;show(k);cout << endl;}
}
//DFS算法
void chessboard::DFS() {time = 0;time++;//开始利用算法求解int now = 0;while (now <= 500) {//判断当前状态是否终态for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (!check(now))goto gg;else goto QAQ;
gg: //记得上下左右重新排序在DFS中if (assit[now]<5) {int deep = assit[now]; //下移if (downmove(now, time) == 1) {time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d4;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;goto d41;d4:;}//重新排序for (int k = time; k > now + 1; k--)for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[k][i][m] = open[k - 1][i][m];for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++) {open[now + 1][i][m] = open[time][i][m];open[time][i][m] = 0;}//修改到assist数组assit[time - 1] = deep + 1;for (int i = time; i > now + 1; i--)assit[i] = assit[i - 1];assit[now + 1] = assit[time];assit[time] = 0;d41:;}//右移if (rightmove(now, time) == 1) {time++;time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d3;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;goto d31;d3:;}//重新排序for (int k = time; k > now + 1; k--)for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[k][i][m] = open[k - 1][i][m];for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++) {open[now + 1][i][m] = open[time][i][m];open[time][i][m] = 0;}//修改到assist数组assit[time - 1] = deep + 1;for (int i = time; i > now + 1; i--)assit[i] = assit[i - 1];assit[now + 1] = assit[time];assit[time] = 0;d31:;}//上移if (upmove(now, time) == 1) {time++;time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d2;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;goto d21;d2:;}//重新排序for (int k = time; k > now + 1; k--)for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[k][i][m] = open[k - 1][i][m];for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++) {open[now + 1][i][m] = open[time][i][m];open[time][i][m] = 0;}//修改到assist数组assit[time - 1] = deep + 1;for (int i = time; i > now + 1; i--)assit[i] = assit[i - 1];assit[now + 1] = assit[time];assit[time] = 0;d21:;}//左移if (leftmove(now, time) == 1) {time++;time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d1;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;goto d11;d1:;}//重新排序for (int k = time; k > now + 1; k--)for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[k][i][m] = open[k - 1][i][m];for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++) {open[now + 1][i][m] = open[time][i][m];open[time][i][m] = 0;}//修改到assist数组assit[time - 1] = deep + 1;for (int i = time; i > now + 1; i--)assit[i] = assit[i - 1];assit[now + 1] = assit[time];assit[time] = 0;d11:;}}now++;}
QAQ:cout << "成功找到解决路径，如下:" << endl;for (int k = 0; k <= now; k++) {cout << "第" << k << "步：" << endl;show(k);cout << endl;}
}
//A*算法
void chessboard::A() {time = 0;time++;//开始利用算法求解int had = 0;while (had < 500) {int m[4];for (int t = 0; t < 4; t++)m[t] = -1;//判断是否终态for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (!check(had))goto gg;else goto QWQ;gg://左移if (leftmove(had, time) == 1) {time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d1;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;goto d11;d1:;}//若新节点拓展成功，则计算其估价函数值m[0] = apprise(time - 1);d11:;}//上移if (upmove(had, time) == 1) {time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d2;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;goto d22;d2:;}//若新节点拓展成功，则计算其估价函数值m[1] = apprise(time - 1);d22:;}//右移if (rightmove(had, time) == 1) {time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d3;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;goto d33;d3:;}//若新节点拓展成功，则计算其估价函数值m[2] = apprise(time - 1);d33:;}//下移if (downmove(had, time) == 1) {time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d4;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;goto d44;d4:;}//若新节点拓展成功，则计算其估价函数值m[3] = apprise(time - 1);d44:;}had++;//根据估价函数值对新加入的节点进行排序int sum = 0;for (int i = 0; i < 4; i++)if (m[i]!= 1) sum++;int* n = new int[sum];int t = 0;for (int i = 0; i < 4; i++, t++)if (m[i] != 1) n[t] = m[i];//开始对open表新增排序for(int a=0;a<sum-1;a++)for(int b=a+1;b<sum;b++)if (n[a] > n[b]) {int change = n[b];n[b] = n[a];n[a] = change;for(int i=0;i<3;i++)for (int m = 0; m < 3; m++) {change = open[time - sum + a][i][m];open[time - sum + a][i][m] = open[time - sum + b][i][m];open[time - sum + b][i][m] = change;} }}
QWQ:for (int k = 0; k <= had; k++) {cout << "成功找到解决路径，如下:" << endl;cout << "第" << k << "步：" << endl;show(k);cout << endl;}}
2、思考并解答以下问题
（1）你所采用的估价函数f(n) = g(n) + h(n)中，g(n)和h(n)的主要作用是什么？
答：g(n)与h(n)的主要作用的：寻找不在正确为值的数的个数
（2）结合本实验举例说明不同启发策略对实验的效果有何影响？（可列出图表说明）
答:不同的启发策略导致搜索的open次序的不同，会影响效率
（3）若问题的初始状态是随机产生的，你的实验程序应该如何改进？（如图形属性的设置、图形队列存入文件等）添加代码，根据实际需要添加其他辅助函数。
答：程序本身的初始状态就是初始态由用户输入。
六，实验结果分析：
初始状态：
DFS寻址：
BFS寻址：
A*寻址:
总结：
实验写了很久，有以下几点瑕疵想说明：①open表的数组存储的状态上限是500，可能遇到某些情况寻址状态大于500导致无法完成寻址。②DFS算法中我对open输入的数据本质上还是BFS的形式输入，只是在逐个检查排序时候替换成了DFS的形式，可能会导致open表中的多余状态过多。③A*算法的估价函数只是简单的以不符合终止态的个数来表示，更准确的应该可以使用曼哈顿估价函数。
附上完整代码：
#include<iostream>
using namespace std;class chessboard {
private:int chess[3][3]; //状态初始图int referencechess[3][3]; //最终参考状态int open[500][3][3]; //状态备选表int assit[500]; //DFS搜索辅助数组int time; //搜索计次
public:void init2();void init();void show(int);int upmove(int,int);int downmove(int,int);int leftmove(int,int);int rightmove(int, int);bool check(int);void BFS();void DFS();int apprise(int); //估价函数void A();};void chessboard::init2() {cout << "请输入0~8的八数码" << endl;for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)cin >> chess[i][m];
}void chessboard::init() {referencechess[0][0] = 1;referencechess[0][1] = 2;referencechess[0][2] = 3;referencechess[1][0] = 8;referencechess[1][1] = 0;referencechess[1][2] = 4;referencechess[2][0] = 7;referencechess[2][1] = 6;referencechess[2][2] = 5;for (int i = 0; i < 500; i++)for (int m = 0; m < 3; m++)for (int k = 0; k < 3; k++) {open[i][m][k] = 0;}for (int i = 0; i < 500; i++)assit[i] = 0;time = 0;//首状态导入open表中for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++) open[time][i][m] = chess[i][m];}void chessboard::show(int k) {for (int i = 0; i < 3; i++) {for (int m = 0; m < 3; m++)cout << open[k][i][m] << " ";cout << endl;}
}int chessboard::downmove(int had,int will) {int i = 0, m = 0;for (i=0; i < 3; i++)for (m=0; m < 3; m++) {if (open[had][i][m] == 0)goto QAQ;}
QAQ:if (i == 2)return 0;for (int a = 0; a < 3; a++)for (int b = 0; b < 3; b++)open[will][a][b] = open[had][a][b];int subsititute;subsititute = open[will][i][m];open[will][i][m] = open[will][i + 1][m];open[will][i + 1][m] = subsititute;return 1;
}int chessboard::upmove(int had, int will) {int i = 0, m = 0;for (i=0; i < 3; i++)for (m=0; m < 3; m++) {if (open[had][i][m] == 0)goto QAQ;}
QAQ:if (i == 0)return 0;for (int a = 0; a < 3; a++)for (int b = 0; b < 3; b++)open[will][a][b] = open[had][a][b];int subsititute;subsititute = open[will][i][m];open[will][i][m] = open[will][i -1][m];open[will][i - 1][m] = subsititute;return 1;
}int chessboard::leftmove(int had, int will) {int i = 0, m = 0;for (i=0; i < 3; i++)for (m = 0; m < 3; m++) {if (open[had][i][m] == 0)goto QAQ;}
QAQ:if (m == 0)return 0;for (int a = 0; a < 3; a++)for (int b = 0; b < 3; b++)open[will][a][b] = open[had][a][b];int subsititute;subsititute = open[will][i][m];open[will][i][m] = open[will][i][m - 1];open[will][i][m - 1] = subsititute;return 1;
}int chessboard::rightmove(int had, int will) {int i = 0, m = 0;for (i=0; i < 3; i++)for (m=0; m < 3; m++) {if (open[had][i][m] == 0)goto QAQ;}
QAQ:if (m == 2)return 0;for (int a = 0; a < 3; a++)for (int b = 0; b < 3; b++)open[will][a][b] = open[had][a][b];int subsititute;subsititute = open[will][i][m];open[will][i][m] = open[will][i][m + 1];open[will][i][m + 1] = subsititute;return 1;
}bool chessboard::check(int had) { //检查当前图是否为是最终状态for (int i=0;i<3;i++)for (int m = 0; m < 3; m++)if (open[had][i][m] != referencechess[i][m])goto QAQ;return true; //返回相同，1
QAQ:return false; //返回不同，0
}void chessboard::BFS() { //默认排序：左上右下time = 0;time++;//开始利用算法求解int had = 0; //正在遍历的节点while (had<500) {//判断当前状态是否是最终态for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (!check(had))goto gg;else goto QWQ;gg://左移if (leftmove(had, time) == 1) {time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d1;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;break;d1:;}}//上移if (upmove(had, time) == 1) {time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d2;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;break;d2:;}} //右移if (rightmove(had, time) == 1){time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d3;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;break;d3:;}}//下移if (downmove(had, time) == 1){time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d4;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;break;d4:;}}had++;}
QWQ:for (int k = 0; k <= had; k++) {cout << "成功找到解决路径，如下:" << endl;cout << "第"<<k<<"步：" << endl;show(k);cout << endl;}
}void chessboard::DFS() {time = 0;time++;//开始利用算法求解int now = 0;while (now <= 500) {//判断当前状态是否终态for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (!check(now))goto gg;else goto QAQ;
gg: //记得上下左右重新排序在DFS中if (assit[now]<5) {int deep = assit[now]; //下移if (downmove(now, time) == 1) {time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d4;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;goto d41;d4:;}//重新排序for (int k = time; k > now + 1; k--)for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[k][i][m] = open[k - 1][i][m];for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++) {open[now + 1][i][m] = open[time][i][m];open[time][i][m] = 0;}//修改到assist数组assit[time - 1] = deep + 1;for (int i = time; i > now + 1; i--)assit[i] = assit[i - 1];assit[now + 1] = assit[time];assit[time] = 0;d41:;}//右移if (rightmove(now, time) == 1) {time++;time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d3;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;goto d31;d3:;}//重新排序for (int k = time; k > now + 1; k--)for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[k][i][m] = open[k - 1][i][m];for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++) {open[now + 1][i][m] = open[time][i][m];open[time][i][m] = 0;}//修改到assist数组assit[time - 1] = deep + 1;for (int i = time; i > now + 1; i--)assit[i] = assit[i - 1];assit[now + 1] = assit[time];assit[time] = 0;d31:;}//上移if (upmove(now, time) == 1) {time++;time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d2;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;goto d21;d2:;}//重新排序for (int k = time; k > now + 1; k--)for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[k][i][m] = open[k - 1][i][m];for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++) {open[now + 1][i][m] = open[time][i][m];open[time][i][m] = 0;}//修改到assist数组assit[time - 1] = deep + 1;for (int i = time; i > now + 1; i--)assit[i] = assit[i - 1];assit[now + 1] = assit[time];assit[time] = 0;d21:;}//左移if (leftmove(now, time) == 1) {time++;time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d1;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;goto d11;d1:;}//重新排序for (int k = time; k > now + 1; k--)for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[k][i][m] = open[k - 1][i][m];for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++) {open[now + 1][i][m] = open[time][i][m];open[time][i][m] = 0;}//修改到assist数组assit[time - 1] = deep + 1;for (int i = time; i > now + 1; i--)assit[i] = assit[i - 1];assit[now + 1] = assit[time];assit[time] = 0;d11:;}}now++;}
QAQ:cout << "成功找到解决路径，如下:" << endl;for (int k = 0; k <= now; k++) {cout << "第" << k << "步：" << endl;show(k);cout << endl;}
}int chessboard::apprise(int had) {int sum = 0;for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[had][i][m] != referencechess[i][m])sum++;return sum;
}void chessboard::A() {time = 0;time++;//开始利用算法求解int had = 0;while (had < 500) {int m[4];for (int t = 0; t < 4; t++)m[t] = -1;//判断是否终态for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (!check(had))goto gg;else goto QWQ;gg://左移if (leftmove(had, time) == 1) {time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d1;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;goto d11;d1:;}//若新节点拓展成功，则计算其估价函数值m[0] = apprise(time - 1);d11:;}//上移if (upmove(had, time) == 1) {time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d2;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;goto d22;d2:;}//若新节点拓展成功，则计算其估价函数值m[1] = apprise(time - 1);d22:;}//右移if (rightmove(had, time) == 1) {time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d3;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;goto d33;d3:;}//若新节点拓展成功，则计算其估价函数值m[2] = apprise(time - 1);d33:;}//下移if (downmove(had, time) == 1) {time++;//与之前做对比for (int k = 0; k < time - 1; k++) {for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)if (open[time - 1][i][m] != open[k][i][m]) {goto d4;}for (int i = 0; i < 3; i++)for (int m = 0; m < 3; m++)open[time - 1][i][m] = 0;time--;goto d44;d4:;}//若新节点拓展成功，则计算其估价函数值m[3] = apprise(time - 1);d44:;}had++;//根据估价函数值对新加入的节点进行排序int sum = 0;for (int i = 0; i < 4; i++)if (m[i]!= 1) sum++;int* n = new int[sum];int t = 0;for (int i = 0; i < 4; i++, t++)if (m[i] != 1) n[t] = m[i];//开始对open表新增排序for(int a=0;a<sum-1;a++)for(int b=a+1;b<sum;b++)if (n[a] > n[b]) {int change = n[b];n[b] = n[a];n[a] = change;for(int i=0;i<3;i++)for (int m = 0; m < 3; m++) {change = open[time - sum + a][i][m];open[time - sum + a][i][m] = open[time - sum + b][i][m];open[time - sum + b][i][m] = change;} }}
QWQ:for (int k = 0; k <= had; k++) {cout << "成功找到解决路径，如下:" << endl;cout << "第" << k << "步：" << endl;show(k);cout << endl;}}void main() {chessboard a;a.init2();while (true) {cout << "请输入序号选择功能:" << endl;cout << "0.修改初始状态 1.DFS寻址 2.BFS寻址 3.A*算法寻址 4.退出" << endl;cout << "请输入序号：";int z;cin >> z;switch (z) {case 0: {system("cls"); a.init2(); break; }case 1: {system("cls"); a.init(); a.DFS(); break; }case 2: {system("cls"); a.init(); a.BFS(); break; }case 3: {system("cls"); a.init(); a.A(); break; }case 4: {system("cls"); exit(0); }}int r;cout << endl << "按下任意键+回车键继续";cin >> r;system("cls");cout << "初始状态为：" << endl;a.show(0);cout << endl;}
}
更多推荐
八数码问题——人工智能
发布评论