大家好，又见面了，我是你们的朋友全栈君。
基于搜索策略的八数码问题求解
大作业题目：
基于搜索策略的八数码问题求解
大作业目的：
加深对搜索策略的理解，尤其是对启发式搜索的基本原理的理解，使学生能够通过编程实现图搜索的基本方法和启发式搜索算法，并能够解决一些应用问题。
大作业要求：
使用盲目搜索中的宽度优先搜索算法或者使用启发式搜索中的全局择优搜索或A*算法。每人提交一份大作业报告，该报告包括设计、实现、测试、实验对比结果分析、结论、个人体会与总结，具体见格式要求。大作业程序需验收通过。
大作业提交内容：课程大作业纸质报告1份；将课程大作业电子报告和课程大作业程序及代码压缩包提交至网络教学综合平台。
大作业提交截止时间：以网络教学综合平台中的截止时间为准。
对任意的八数码问题，给出求解结果。例如：对于如下具体八数码问题：
1 | 3 | 2 | 1 | 2 | 3 | |||
|---|---|---|---|---|---|---|---|---|
4 | 5 | ⇨ | 8 | 4 | ||||
6 | 7 | 8 | 7 | 6 | 5 | |||
通过设计启发函数，编程实现求解过程，如果问题有解，给出数码移动过程，否则，报告问题无解。
250 123
873 804
641 765
求解步骤：
步骤一.设计八数码格局的隐式存储的节点结构：
将表示棋局的状态用如下向量表示：
A＝(X0，X1 ，X2 ，X3 ，X4 ，X5 ， X6 ， X7 ，X8)
约束条件： Xi{0，1 ，2，3，4，5，6，7，8}
XiXj，当ij时。
初始状态： S0 ＝（1，3，2，4，0，5，6，7，8）
目标状态： Sg ＝（1，2，3，8，0，4，7，6，5）
步骤二.计算两个节点之间的可达性。
（1） 可以通过限定时间阈值或步骤阈值，判定两个节点之间的可达性。
（2）通过计算八数码节点的逆序数判断。如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。计算八数码节点的逆序数时将代表空格的0去除，如初始状态排列为
（1，3，2，4，5，6，7，8） 逆序数为：0 1 0 0 0 0 0 0=1即为奇排列
目标状态排列为（1，2，3，8，4，7，6，5） 逆序数为：0 0 0 4 0 2 1 0=7即为奇排列，具有同奇或同偶排列的八数码才能移动可达，否则不可达。
步骤三. 设计估计函数与启发函数，估计函数f(n)定义为：f(n)＝d(n)＋h(n) 其中，d(n)表示节点深度。
启发函数h(n)可参考如下定义方法：
（1）启发函数h(n)定义为当前节点与目标节点差异的度量：即当前节点与目标节点格局相比，位置不符的数字个数。
（2）启发函数h(n)定义为当前节点与目标节点距离的度量：当前节点与目标节点格局相比，位置不符的数字移动到目标节点中对应位置的最短距离之和。
启发函数可参考如下定义方法：
（3）启发函数h(n)定义为每一对逆序数字乘以一个倍数。
（4）为克服了仅计算数字逆序数字数目策略的局限，启发函数h(n)定义为位置不符数字个数的总和与3倍数字逆序数目相加。
步骤四 .选择并设计搜索算法(至少选择1个)
（1）使用盲目搜索中的宽度优先搜索算法。
（2）使用启发式搜索中的全局择优搜索算法。
（3）使用A*算法。
步骤五 设计输入输出
输入：初始节点，目标节点 格式：1 3 2 4 0 5 6 7 8
1 2 3 8 0 4 7 6 5
可采取以下三种方式输入：命令行、文件start.txt、GUI输入。
输出：如果无解在屏幕输出”目标状态不可达”
如果有解请在屏幕输出”最少移动n步到达目标状态”，n为最少移动的步骤数，并记录从初始状态到目标状态的每一步中间状态，并将这些状态保存至result.txt文件中。
以上过程可采取以下三种方式输出：命令行、文件result.txt、GUI输出。
步骤六 编写代码，调试程序。
至少给出5组初始节点和目标节点对，并记录程序运算结果。节点对要包括以下三种情况：不可达；最少移动步骤数≥10；最少移动步骤数≤6
拓展实验：（可任选1个完成）
1.记录步骤四中3个搜索算法的执行时间，并比较3者的效率。
2.在启发式搜索中，分别采用步骤三中启发式函数(1)(2)(3)(4)，并比较四者的效率，思考如何进一步改进启发式函数。
3. 试分析在所有可能的初始状态和目标状态之间最长的最小移动步骤数是多少？
我准备采用A*算法来解决这个问题，拓展实验选的是2
作者水平有限，如有问题，欢迎留言交流
PS:笔者一开始觉得第一个太麻烦，要写三个算法。而且当时对全局择优算法和A*算法的差别并没有太明显的认知，后来知道了，虽然在选择扩展OPEN结点时，全局择优和A*都是选择Open表中F值小的那一个，但是A*有一个查重过程（即查找即将扩展的结点是否在open表或者closed表中已经存在过），全局择优算法并无这个查重过程。这个查重过程的意义在于，同一个状态序列可能通过多个路径到达的，在F=G H这个启发函数中，G是结点拓展深度，H是当前序列到目标序列的评估函数，所以对于同样的排列，H肯定是相同的，只是G不同罢了。所以在全局择优算法中，closed表中可能有两个结点的序列state相同，但是f不同，但是A*算法中closed表不会存在两个结点的state序列相同。
一、知识准备
1.1何为A *算法
A*算法是对启发式算法A算法的一种改进，启发式算法，就是给每一种子状态一个F=G H的函数评估，取F值小的（到目标路径代价最小的路径值）的一种情况进行拓展。这里的F是单调函数
启发式算法是对盲目搜索策略算法的一种改进，能够大幅提高搜索效率，但是关键在于启发式函数的选择，这一点跟剪枝法中剪枝函数的选择有些类似的思想。
介绍A算法，需要引入两个重要概念，open表和close表
1.2何为open、close表？
open表：记录已经生成但未扩展的状态，open表中状态的排列顺序至关重要，默认先从表头选择状态扩展
close表：记录已经扩展过的状态（应该还包含路径）
根据书上的定义，在深度优先和广度优先的遍历中，也引入了open表和close表，在不同的搜索策略中，open表的结构是不同的。在深度优先中，open表是一个先进后出的堆栈（说白了，就是对子状态按生成次序排列后，插入到open表头，与编译原理里面LL 算法中的预测分析法的堆栈结构还有所不同，后者是先生成的结点先进栈，这个是先生成一个次序，将次序放入表头）
在A*算法中，open表是按照f值由小到大排序的表，比较特殊。
二、编程思路：
我不喜欢直接贴上代码，因为学习代码就是一个学习思路的过程，编程重在思考，学习别人的思路和思考问题的方式。
2.1 根据要求解的问题特征、定义一个新的基础元素结构体
首先这个A*问题是一个比较复杂的算法实现问题，应该定义一个新的结构体来作为基础元素
基础元素应该包含一个3*3的矩阵（八数码的排列形式），而且这个矩阵还要能查到它的前驱路径，对于前驱这个概念，学过数据结构的应该都不陌生，二叉树就有父节点、子节点的概念，所以对基础元素的定义里面，应该也有child parent结点这些元素，好了，现在可以确定三个因素了：3*3矩阵、child结点、parent结点。还有一点就是启发函数F=G H的因素，上文也提到了，对于相同的状态序列，它的H值肯定相同，G值可能有所不同（主要是通过不路径到达的，路径深度不同），那么也应该包含G和H这两个元素，F值要不要包含进去呢？因为F=G H，我认为结构体冗余，F最好不要加进去。现在一个状态序列由：3*3的矩阵序列、child、parent、G、H这5个因素唯一确定了，其中child和parent代表了它的路径存储信息，应该也是要求中请求的。
题目中要求输出从初始状态到目标状态的路径过程（实际上就是一个动态规划问题），在初始结构体定义中，child和parent是寻找路径时候要用到的，这个问题是从初始状态到目标状态的路径，如果最后我们输出最佳路径的时候，还是从初始状态开始找，找它的child结点，那肯定会有许多无用查找，因为有很多child结点最终不会生成目标状态。因此，输出最佳路径的时候，应该从生成的最后路径往前倒推，后序遍历得到结果（与动态规划的问题不谋而合）。这样在搜索过程中，只需要用到parent结点就可以了，child结点就失去了它存在的意义，故舍弃（因为我要解决的问题，不关心哪个路径是哪个路径的child,指关心哪个路径是哪个路径的pre,如果一个八数码问题有解，这个解的路径的起始点和终止点是已经确定的）
继续深入，在二叉树的学习中，child值应该是唯一确定的，它不应该是指一个结点的data值，而是它的下标（即唯一标识确定的），那么在我们已经定义的四个元素里面，3*3矩阵、G、H、parent可以唯一标识一个结点吗？（这个问题类似于数据库中的候选码的定义问题）显然，parent是指向它的父的标识值，这个标识值如果是这四个元素组合值（3*3，G，H，pre)确实可以唯一确定，但显然有些复杂了。不如对每一个生成的结点，都给它从0，1，2，3，4……这样编个序号，这样pre值指向的是序号编码，也达到了唯一标识的作用。于是再引入一个新的元素，current,current的值是在新的基础元素放进open时，依次 1，作为序号，parent指向的是该路径的父节点的序号。
这样初始结构体就应该有：3*3的矩阵序列（数字0-8排列，0代表空格）、G、H、current、parent。
再看看这样的定义，满足搜索路径是满足了，那能不能满足open和closed表的存储过程呢？在新结点的生成过程中，肯定有空格（在八数码问题中用0代表）移动这一过程，这个结构体中，G、H、Current、parent都可以用int值，3*3是一个二维数组，为了方便作为传递参数，满足耦合性，可以用一个一维的数字序列来代表二维数组，之后进行解压即可，即：
1 2 3
4 5 6
7 0 9 可以用123456709来代表，需要输出路径时进行解压操作即可了。（别问我怎么想到的，我是站在巨人的肩膀上知道的）
2.2 代码函数编辑
那么，讲到这，结构体定义很好写了（不过这个不是完全体，后面会遇到具体问题，进一步完善）
代码语言：javascript复制Struct Snode{
int state;//3*3的矩阵的一维数组表示
int g; //遍历深度g值
int h; //启发函数H值
int cur; //当前结点的编号
int pre; //当前结点的前驱结点的编号
Snode(const int state,int g,int h,int cur,int pre):state(state),g(g),h(h),cur(cur),pre(pre){};
//对产生的新结构体的便捷赋初始值，与对类的初始化函数类似，是个小技巧
};顺手推舟，将一维数字的解压函数和返回F值的函数写出来：
代码语言：javascript复制typedef int Arc[4][4];
void state_toArc( int state,Arc arc)
{
for(int i=3;i>=1;i--)
for(int j=3;j>=1;j )
{
arc[i][j]=state;
state/=10;
}
}
int F(const Snode&node)//为什么传递参数变量前选const ,建议百度一下
{
return node.g node.h;
}typedef让int [4][4]变成一个新的变量名，也是处理二维数组作为形式参数的一个便捷方法，同学们可以学习一下。
解决完基础的元素结构体的定义，那么接下来对这个基础元素的所有操作都在open和closed表上进行，那么接下来就是对open和closed表的定义了。在a*算法中，open表是按照f值（>0)从小到大排列,这不禁让人联想到STL容器中map,map是一个pair数据类型的容器，有<key,value>值，并且按照key值从小到大排列，于是用map来存储open,close也可以使用map
attention:map中明确定义，一个key值只能对应一个value值，但是在open表中，不同的Snode可能它们的f值相同，于是采用multimap来解决这个问题。
考虑到后面有对open表的元素查重问题，即查找open表中的value值是否与生成结点相同，在map中查找value值，可以通过建立key-value的一一对应的value-key表（即把value值作为key值）来解决这个问题，map中直接查找key值要方便的多。但是由于value是一个Snode类型，在map的value-key查询key值时，需要比较大小，即比较Snode的大小，因此需要重载 “<“和“==”符号，于是对结构体的写法进一步改进
代码语言：javascript复制struct Snode{
int state;//一维数字表示二维数组
int g; //g值
int h; //h值
int cur; //当前状态的序号值
int pre; //当前状态的前驱序号值
Snode(int state,int g,int h,int cur,int pre):state(state),g(g),h(h),cur(cur),pre(pre){};
bool operator <(const Snode&e) const{ state<e.state;}
bool operator ==(const Snode&e) const{ return （state==e.state);}
//success(cur,tar)代表当前序列与目标序列相同
};接下来，写检查是否有解的函数：（按照大作业的要求，就是检查，初始序列和目标序列在逆序数的奇偶性上，是否同奇同偶。
代码语言：javascript复制bool checkvalid(int cur, int tar) {
int cur_n = 0, tar_n = 0;
board curr, tarr;
state_toArc(cur, curr);
state_toArc(tar, tarr);
/*如果硬要在3*3矩阵上遍历比较一个结点和对多个结点的相对关系（可能是值大小的关系，也可能是位置的相对关系）
对于for循环中i与j标的取值有点讲究
(1).
通常i 和 j 对应的是矩阵的row 和 clumn值，这是一般的逻辑，本函数要找当前元素后面和前面的元素，那么这段代码就会写成
for(int i=1;i<=3;i )
for(int j=1;j<=3;j )
/*接下来对每一个元素cur[i][j]、tar[i][j]，寻找它后面的所有元素要考虑它本身的位置，比如[2,2] 和[2,3]情况下，
显然它下一个位置分别是[2,3] 和[3,1],那么对i 的取值就不同,这种分类讨论显然太烦琐了
(2).
在这种情况下，通常遍历时，i取0-8的范围，就是位置值，j取i 1,意思是下一个位置的元素的位置值
那么就写成了下面的函数情况。
那么位置值0-8怎么映射成矩阵中的下标位置对（x,y)呢？
其实这个的实质就是，我给你一个一维的下标值位置值，你能不能找出对应下标位置值在矩阵中的位置
|3 2 1| 如图矩阵，3 2 1 4 5 6 7 8 9元素对应的位置值是0 1 2 3 4 5 6 7 8，我们检索的时候，
|4 5 6| row=位置值/n,clumn=位置值%n
|7 8 9|
*/
for(int i = 0; i < 9;i )
{
for (int j = i 1; j < 9; j )//找第i 1个元素后面所有的非0元素，如果元素比它小，那就对应逆序数 1
{
if (curr[j / 3 1][j % 3 1] != 0 && (curr[i / 3 1][i % 3 1] > curr[j / 3 1][j % 3 1])) cur_n ;
if (tarr[j / 3 1][j % 3 1] != 0 && (tarr[i / 3 1][i % 3 1] > tarr[j / 3 1][j % 3 1])) tar_n ;
}
}
// 一维数组实现，不需要预先把所有的值赋给数组，而是在比较过程中代入，但也需要比较访问读取具体位置处的值
/*
int c[9],t[9];
for(int i=0;i<9;i )
{
c[i]=cur;t[i]=tar;
if (c[i] != 0 && i != 0)
{
for (int j = i - 1; j >= 0; j--)
if (c[j] > c[i]) cur_n ;
}
if (t[i] != 0 && i != 0)
{
for (int j = i - 1; j >= 0; j--)
if (t[j] > t[i]) tar_n ;
}
}
*/
return (cur_n & 1) == (tar_n & 1);
}接下来，是对4个启发式函数的定义和写法。 启发式函数的参数在考虑的时候，因为这个h值只跟状态序列的排列有关，与路径无关，所以形参自然是int state，int target
代码语言：javascript复制//启发函数1
int H1(int curState,int tarState)
{
//找当前状态与目标状态的位置不同的非0数字个数
int num = 0;
for (int i = 0; i < 9; i ) {
if ((curState % 10 != 0) && (curState % 10 != tarState % 10)) num;
curState /= 10;
tarState /= 10;
}
return num;
}
//启发函数2
int H2(int curState, int tarState) {
//找当前状态要移动到目标的最短路径，返回所有状态的最短路径之和
int num = 0;
//求位置移动的算法，时间复杂度过高，甚至要n^4
/*
board curr,tarr;
state_toArc(cur,curr);
state_toArc(tar,tarr);
for(int i=1;i<=3;i )
for (int j = 1; j <= 3; j ) {
if (curr[i][j] == tarr[i][j]) continue;
else {
int tmpi, tmpj;
for (tmpi = 1; tmpi <= 3; tmpj ) {
for (tmpj = 1; tmpj <= 3; tmpj )
if (tarr[tmpi][tmpj] == curr[i][j]) break;
}
num = abs(tmpi-i) abs(tmpj-j);
}
}
*/
//引入一种新的数组，这个数组的下标值代表的是元素（即key值代表的是value),value值代表的是位置值。
int cu[9], ta[9];
for (int i = 8; i >= 0; i--) {
cu[curState % 10] = ta[tarState % 10] = i;
curState /= 10;
tarState /= 10;
}
//含义是，数字1-8的状态序列到目的序列，它们不同的位置值之差，cu[i] i代表是哪个数字，值代表的是它的位置值0-8。
//位置值之间的移动的最小步骤不是简单相减，而是要根据它在矩阵上的结构特点，比如位置值0和3，实际上移动过去只需要一步
//位置值0-8在3*3矩阵上具体的(x,y)的反映上面已经讲过，位置移动值应该是 |xc-xt| |yc-yt|
for (int i = 1; i <= 8; i ) {
num = abs(cu[i] / 3 - ta[i] / 3) abs(cu[i] % 3 - ta[i] % 3);
}
return num;
}
//启发函数3
int H3(int curState)
{ //返回逆序数目*3
int num=0;
board curr;
state_toArc(curState, curr);
for (int i = 0; i < 9; i ) {
for (int j = i 1; j < 9; j )
{
if ((curr[i / 3 1][i % 3 1] != 0) && (curr[j / 3 1][j % 3 1] != 0) && (curr[i / 3 1][i % 3 1] > curr[j / 3 1][j % 3 1]))
num;
}
}
return num * 3;
}
//启发函数4
int H4(int curState, int tarState) {
//综合H1与H3
return H1(curState, tarState) H3(curState);
}接下来写主函数 open表 的运行过程，根据伪代码的算法：
代码语言：javascript复制begin:
检查目标状态到状态序列是否可达，可达继续操作
open=[Snode(start)] ,closed=[] //将初始结点放到open表中
while(open!=[] ) //当open表不为空时，执行循环
{
将open表的第一个结点n出栈，
if n.state= 目标.state, then return (success)
记录结点n的路径
移动结点n的空格部分，生成结点n的子节点
对n的子节点的状态序列state
case: 出现在open表中过
if 子结点的f值<open表中的结点f值，
then 将原来open表中的Snode删除，记录新生成的子节点的路径和f值，放入open表中
case: 在closed表中出现过
if 子节点的f值<closde 表中的结点f值
then 将原来的closed表中的Snode删除，记录记录新生成的子节点的路径和f值，放入open
表中
case: 未在open表和closed表中出现过
then ,将新的结点放入open表中
}
return failure;
end;接下来是int run(const int& st,const int&ed)的具体代码（这个传递参数为什么是const int&,另一篇blog中会讲述）
代码语言：javascript复制int run(const int&st, const int &ed) {
if (!checkvalid(st, ed)) return -1;//检测是否可达，这样可以提高运行效率
//清理上一次程序运行时产生的数据。
open_key.clear();
open_value.clear();
closed.clear();
path.clear();
/*将初始结点放入open表中*/
int index = 0;//递增的序号值，唯一标识，便于查询pre路径
Snode start(st, 0, H2(st, ed), index , -1);//初始化初始结点start的值,其前驱路径的标号是-1，代表不存在
open_key.insert(make_pair<int, Snode>(int(H2(st, ed)), Snode(start)));//将初始结点放入open_key表中
open_value.insert(make_pair<Snode, int>(Snode(start), int(H2(st, ed))));//将初始结点放入open_value表中
/*cout << open_key.begin()->first; 这里是查错查bug时设的断点查询，同学们也可以学习一下这种纠错方法
if (success(target, target)) cout << "1" << endl;*/
/*对后续结点进行启发式搜索*/
while (open_key.size())
{
Snode mixNode = open_key.begin()->second;//取出open的第一个元素(该元素也是f值最小的结点)进行扩展
open_key.erase(open_key.begin()); //从open表中清除
open_value.erase(open_value.lower_bound(mixNode)); //从open表中清除
closed.insert(make_pair<int, bool>(int(mixNode.state), bool(true))); //将序列放入closed表中，具体的结构值放入path中
path.push_back(mixNode);//将结点的具体结构放入path中
//如果是已经到达目标路径，返回最短路径值step
if (success(mixNode.state, ed)) {
//cout << "1" << endl;
return mixNode.g;
}
//cout << mixNode.state << endl;
//outPut(mixNode.state);
/*对取出的结点进行移动操作，生成新的子节点。*/
//寻找空格的位置
int cx = -1, cy = -1;
board tmp;
int tmps;
state_toArc(mixNode.state, tmp);
//cx，cy代表空格的坐标[cx,cy]
for (int i = 1; i <= 3; i ) {
if (cx != -1) break;
for (int j = 1; j <= 3; j ) {
if (tmp[i][j] == 0)
{
cx = i;
cy = j;
break;
}
}
}
//移动生成子结点
for (int k = 0; k < 4; k ) {
int nx = cx move_x[k];
int ny = cy move_y[k];
if (nx >= 1 && nx <= 3 && ny >= 1 && ny <= 3)//保证移动后的空格不越界
{
swap(tmp[cx][cy], tmp[nx][ny]);//将原来空格和移动后的空格应在的位置的元素，交换顺序
tmps = arc_toState(tmp); //提取出新生成的状态序列state值
swap(tmp[cx][cy], tmp[nx][ny]);//还原序列，用于空格其他方向的移动
/*对新生成的子节点进行判定，是否入open表中*/
Snode newNode(tmps, mixNode.g 1, H2(tmps, ed), index , mixNode.cur);//初始化新生成的子节点
//新生成的子节点的state是tmps,深度是父节点mixNode的深度 1,h用判定函数h（x)求得,序列号按序 1，父节点序列号是mixNode的序列号cur
int newF = F(newNode);//保存新结点的F值
//查找新生成结点的state是否在closed表中
if (!closed.count(tmps))//如果不在closed表中，执行以下操作
{
//查找新生成结点的state是否在open表中
/*因为open表的两个元素并没有直接表示state值的选项，所以count函数不能用，查找元素的时候，就要自己重写一个查找算法
/按照传统的查找，必然是遍历每个元素，看open表中是否有元素的state值跟新结点的state值相同，这时候搜索效率就有点大，这就体现出来双map表的优势了
/双map表，key-value,value-key，在查找元素的时候，不用遍历，直接利用low_bound()函数找value-key表中的的first值value
/在value-key表中，first值value的从小到大的排列顺序是新类型Snode的比较大小的过程，在定义的时候已经定义，若Snode a==Snode b,必然是它们俩的序列值state值相同，<号也是state值相比较的
*/
map<Snode, int>::iterator it_v = open_value.lower_bound(newNode);
//itv指针指向state值>=newNode的迭代器元素，如果该元素的first值恰好=newNode,说明newNode的序列值state在open表中存在，这就是查找的办法了。
map<int, Snode>::iterator it_k;//创建指向key-value表迭代器的指针it_k
//如果在open表中
if (it_v != open_value.end() && it_v->first == newNode) {
//如果新生成的结点是相对于原open表中结点的最优解
if (newF < F(it_v->first)) {
for (it_k = open_key.lower_bound(F(it_v->first)); it_k != open_key.upper_bound(F(it_v->first)); it_k)
if (it_k->second == newNode) break;
//删除原有open表中结点
open_key.erase(it_k);
open_value.erase(it_v);
//将新结点加入open表中
open_key.insert(make_pair<int, Snode>(int(newF), Snode(newNode)));
open_value.insert(make_pair<Snode, int>(Snode(newNode), int(newF)));
}
//不是最优解，放弃新生成的结点
}
//既不在open表中，也不在closed表中
else {
//将新结点加入open表中
open_key.insert(make_pair<int, Snode>(int(newF), Snode(newNode)));
open_value.insert(make_pair<Snode, int>(Snode(newNode), int(newF)));
}
}
else if (closed.count(tmps)) //如果在closed表中，执行以下操作
{
//不用判断是否在open表中，因为想先入closed表必须先入open表，想插入一个结点到open表时，如果它已经在closed表中，是不会把它放到open表里的
//查找到closed表里的具体结构path中保存的旧Snode，比较f值，看是否新结点是更优解
int locate;
for (locate = 0; locate < path.size(); locate ) {
if (path[locate] == newNode) break;//Snode类型的==号代表state值相同
}
//如果是更优解
if (newF < F(path[locate]) && (path[locate].state == tmps)) {
//将原closed表中的元素删除，将新结点放入open表中。新结点的路径在新结点初始化时就已经保存，新结点的f值在加入open表时进行保存
closed.erase(closed.lower_bound(newNode.state));
path.erase(path.begin() locate);
//将新结点加入open表中
open_key.insert(make_pair<int, Snode>(int(newF), Snode(newNode)));
open_value.insert(make_pair<Snode, int>(Snode(newNode), int(newF)));
}
//如果不是更优解，舍弃新生成的结点newNode
}
/*对新生成的子节点进行判定，是否入open表中的判定结束*/
}
}/*对移动生成的新结点的整个操作结束*/
}
//函数走到这里，代表open表为空，则无解，返回步骤-1
return -1;//这个位置一定要写对，我一开始就写错了……
}接下来是寻找路径的函数，采取后序遍历的方法
代码语言：javascript复制//要从后向前找到最优解的路径，采取的是后序遍历，那必然传递参数有pre,有step(第几步），由于查找时是查找path上的路径，path是依次进栈的方法加入元素
//故pre元素必定在子元素的前面
void findPath(int pre, int size, int step) {
if (step == -1) {
return;
}
else if (step == 0) {
cout << "Step-->" << step << endl;
cout << endl;
outPut(path[size].state);
cout << endl;
return;
}
for (int i = size; i >= 0; i--) {
//找到path中原结点的pre结点，递归调用函数，输出结果
if (path[i].cur == pre) findPath(path[i].pre, i, step - 1);
}
cout << "Step--> " << step << endl;
cout << endl;
outPut(path[size].state);
cout << endl;
}补上input和output的写法
代码语言：javascript复制void inPut(board s) {
for (int i = 1; i <= 3; i ) {
for (int j = 1; j <= 3; j ) {
cin >> s[i][j];
}
}
}
void outPut(const int &e) {
board tmp;
state_toArc(e, tmp);
for (int i = 1; i <= 3; i) {
for (int j = 1; j <= 3; j)
cout << tmp[i][j] << " ";
puts("");
}
}因为要比较效率，就要比较代码的运行时间，在main函数中定义即可
代码语言：javascript复制int main() {
double time = 0;
double counts = 0;
LARGE_INTEGER nFreq;
LARGE_INTEGER nBeginTime;
LARGE_INTEGER nEndTime;
QueryPerformanceFrequency(&nFreq);
QueryPerformanceCounter(&nBeginTime);//开始计时
board st, ed;
freopen ("1.txt", "r ",stdin);
inPut(st);
inPut(ed);
int step = run(arc_toState(st), arc_toState(ed));
if (step != -1)
{
cout << "有解，最短路径是" << step << endl;
findPath((path.end()-1)->pre,path.size()-1,step);
}
else {
cout << "不可达" << endl;
}
QueryPerformanceCounter(&nEndTime);//停止计时
time = (double)(nEndTime.QuadPart - nBeginTime.QuadPart) / (double)nFreq.QuadPart;//计算程序执行时间单位为s
cout << "程序执行时间：" << time * 1000 << "ms" << endl;
return 0;
}在这里还有一个问题需要探讨一下，就是visuall c 的分区问题。
1.一开始笔者把这些代码都写到了一个.cpp文件里面，但是感觉有些凌乱，就分成了global.h来存放全局变量及声明，function.h来存放功能函数的声明，function.cpp来存放功能函数体，main.cpp来存放主函数调用
2.这样一来，开始报错，首先是全局变量的问题，因为全局变量被多个.h .cpp引用（如move_x,move_y)，就存在了重复定义的问题，关于这种情况，我的另一篇blog中给出了解决方案（其实也是visuall studio官方的解决方案）
3.另外一个就是，在function.cpp中对vector变量path操作以后, 在main.cpp中调用path,想查询path的结构，结果提示我 vector的iterator无法找到，在我刚接触vector的时候，也出现过这种现象，不过那次是我误把vector.end()当成了最后一个变量，在这个工程中，就是误把path.end()->pre当成了path最后一个变量的pre值，实际上应该是(path.end()-1)->才是最后一个函数. 但显然我这次逻辑并没有出错。
我心想应该是跨.cpp文件下全局变量的作用域的问题吧，于是我把原来的findPath((path.end()-1)->pre,path.size()-1,step);的语句重新定义为一个isOk(int step）函数
代码语言：javascript复制void isOk(int step) {
findPath((path.end() - 1)->pre, path.size() - 1, step);
}然后把原来main.cpp中的findPath((path.end()-1)->pre,path.size()-1,step);的语句换成了isOk(step)语句。 提示错误的信息就消失了。其实我这个操作的本质，就是把对path的访问，放到function.cpp中进行，访问的是function.cpp中的path,而并非是main.cpp中的path,虽然最后的操作函数都在function.cpp中，但是调用的path参数的领域有所不同。
如何选择不同的启发函数？
在run函数中，把含有H1（H2,H3,H4)（int ,int)的函数都替换掉就可以了
下面给出完整的代码
采取的输入流是读取文件，读者自行在工程下创建.txt文件即可，注意不要把.txt放到
这里，而是放到：
就是第一个图的A_star文件夹下。
global.h文件
代码语言：javascript复制#pragma once
#include <iostream> // C 的IO输入输出
#include <vector> // 存储open表的数据结构
#include <map> // 存储closed表的数据结构
using namespace std;
//对于可能被多个.h,.cpp执行的声明不用特殊处理
typedef int board[4][4];//将二维数组的定义重定义为Arc
struct Snode {
int state;//一维数字表示状态序列
int g; //路径深度
int h; //启发函数的评估值
int cur; //状态的序号标号
int pre; //状态的父节点标号
Snode(int state, int g, int h, int cur, int pre) :state(state), g(g), h(h), cur(cur), pre(pre) {}
bool operator <(const Snode&e)const {
return(state < e.state);
}
bool operator ==(const Snode&e)const {
return (state==e.state); //即state值相同
}
};
//对于可能被多个.h .cpp执行的变量需要特殊处理，不然连接器报错
static int move_x[] = { -1,0,1,0 }; //左移动是-1,右移动是 1
static int move_y[] = { 0,1,0,-1 }; //上移动是1,下移动是-1
static multimap<int, Snode> open_key;//open表
static map<Snode, int> open_value; //open表的value-key反表，便于查找元素
static map <int, bool> closed; //closed表
static vector <Snode> path; //保存closed表的具体结构路径function.h文件
代码语言：javascript复制#pragma once
#include"global.h"
bool success(const int &e, const int&s); //检查是否到达目标路径
bool checkvalid(const int& cur, const int& tar); //检查是否有解
int H1(int curState, int tarState); //启发函数1
int H2(int curState, int tarState); //启发函数2
int H3(int curState); //启发函数3
int H4(int curState, int tarState); //启发函数4
int F(const Snode &e); //返回状态的F值
int arc_toState(const board &se); //二维数组转换为一维数字
void state_toArc(int e, board se); //一维数字转换为二维数组
void inPut(board s); //输入初始序列和目标序列
void outPut(const int &e); //输出状态的state值的矩阵形式
void findPath(int pre, int size, int step); //找到最优解的路径
int run(const int&st, const int &ed); //运行A*函数算法主体
void isOk(int step); //当算法运行完毕，检查function.cpp文件
代码语言：javascript复制#include"global.h"
#include"function.h"
//一维数字转换为二维数组
void state_toArc(int e, board se)
{
for (int i = 3; i >= 1; i--)
for (int j = 3; j >= 1; j--)
{
se[i][j] = e % 10;
e /= 10;
}//写for循环不加{}biss嗷
}
//将二维数组转换为一维数字
int arc_toState(const board &se) {//注意e 一定要加上&,不然不能改变e的值
int e = 0;
for (int i = 1; i <= 3; i)
for (int j = 1; j <= 3; j)
e = e * 10 se[i][j];
return e;
}
//返回Snode的F值
int F(const Snode &e) {
return e.g e.h;
}
bool success(const int& cur, const int &tar) {
return(H1(cur, tar) == 0);
}
bool checkvalid(const int& cur, const int& tar) {
int cur_n = 0, tar_n = 0;
board curr, tarr;
state_toArc(cur, curr);
state_toArc(tar, tarr);
/*如果硬要在3*3矩阵上遍历比较一个结点和对多个结点的相对关系（可能是值大小的关系，也可能是位置的相对关系）
对于for循环中i与j标的取值有点讲究
(1).
通常i 和 j 对应的是矩阵的row 和 clumn值，这是一般的逻辑，本函数要找当前元素后面和前面的元素，那么这段代码就会写成
/*for(int i=1;i<=3;i )
for(int j=1;j<=3;j )
/*接下来对每一个元素cur[i][j]、tar[i][j]，寻找它后面的所有元素要考虑它本身的位置，比如[2,2] 和[2,3]情况下，
显然它下一个位置分别是[2,3] 和[3,1],那么对i 的取值就不同,这种分类讨论显然太烦琐了
(2).
在这种情况下，通常遍历时，i取0-8的范围，就是位置值，j取i 1,意思是下一个位置的元素的位置值
那么就写成了下面的函数情况。
那么位置值0-8怎么映射成矩阵中的下标位置对（x,y)呢？
/*其实这个的实质就是，我给你一个一维的下标值位置值，你能不能找出对应下标位置值在矩阵中的位置
|3 2 1| 如图矩阵，3 2 1 4 5 6 7 8 9元素对应的位置值是1 2 3 4 5 6 7 8 9，我们检索的时候，
|4 5 6| row=位置值/n,cloumn=位置值%n
|7 8 9|
*/
for (int i = 0; i < 9; i )
{
for (int j = 0; j < i; j )//找第i 1个元素后面所有的非0元素，如果元素比它小，那就对应逆序数 1
{
if ((curr[i / 3 1][i % 3 1] != 0) && (curr[j / 3 1][j % 3 1] != 0) && (curr[i / 3 1][i % 3 1] < curr[j / 3 1][j % 3 1])) cur_n ;
if ((tarr[i / 3 1][i % 3 1] != 0) && (tarr[j / 3 1][j % 3 1] != 0) && (tarr[i / 3 1][i % 3 1] < tarr[j / 3 1][j % 3 1])) tar_n ;
}
}
// 一维数组实现，不需要预先把所有的值赋给数组，而是在比较过程中代入，但也需要比较访问读取具体位置处的值
/*
int c[9],t[9];
for(int i=0;i<9;i )
{
c[i]=cur;t[i]=tar;
if (c[i] != 0 && i != 0)
{
for (int j = i - 1; j >= 0; j--)
if (c[j] > c[i]) cur_n ;
}
if (t[i] != 0 && i != 0)
{
for (int j = i - 1; j >= 0; j--)
if (t[j] > t[i]) tar_n ;
}
}
*/
return (cur_n & 1) == (tar_n & 1);
}
//启发函数1
int H1(int curState, int tarState)
{
//找当前状态与目标状态的位置不同的非0数字个数
int num = 0;
for (int i = 0; i < 9; i ) {
if ((curState % 10 != tarState % 10)) num;
curState /= 10;
tarState /= 10;
}
return num;
}
//启发函数2
int H2(int curState, int tarState) {
//找当前状态要移动到目标的最短路径，返回所有状态的最短路径之和
int num = 0;
//求位置移动的算法，时间复杂度过高，甚至要n^4
/*
Arc curr,tarr;
state_toArc(cur,curr);
state_toArc(tar,tarr);
for(int i=1;i<=3;i )
for (int j = 1; j <= 3; j ) {
if (curr[i][j] == tarr[i][j]) continue;
else {
int tmpi, tmpj;
for (tmpi = 1; tmpi <= 3; tmpj ) {
for (tmpj = 1; tmpj <= 3; tmpj )
if (tarr[tmpi][tmpj] == curr[i][j]) break;
}
num = abs(tmpi-i) abs(tmpj-j);
}
}
*/
//引入一种新的数组，这个数组的下标值代表的是元素（即key值代表的是value),value值代表的是位置值。
int cu[9], ta[9];
int cur = curState, tar = tarState;
for (int i = 8; i >= 0; i--) {
cu[cur % 10] = ta[tar % 10] = i;
cur /= 10;
tar /= 10;
}
//含义是，数字1-8的状态序列到目的序列，它们不同的位置值之差，cu[i] i代表是哪个数字，值代表的是它的位置值0-8。
//位置值之间的移动的最小步骤不是简单相减，而是要根据它在矩阵上的结构特点，比如位置值0和3，实际上移动过去只需要一步
//位置值0-8在3*3矩阵上具体的(x,y)的反映上面已经讲过，位置移动值应该是 |xc-xt| |yc-yt|
for (int i = 1; i <= 8; i ) {
num = abs(cu[i] / 3 - ta[i] / 3) abs(cu[i] % 3 - ta[i] % 3);
}
return num;
}
//启发函数3
int H3(int curState)
{ //返回逆序数目*3
int num = 0;
board curr;
state_toArc(curState, curr);
for (int i = 0; i < 9; i ) {
for (int j = i 1; j < 9; j )
{
if ((curr[i / 3 1][i % 3 1] != 0) && (curr[j / 3 1][j % 3 1] != 0) && (curr[i / 3 1][i % 3 1] > curr[j / 3 1][j % 3 1]))
num;
}
}
return num * 3;
}
//启发函数4
int H4(int curState, int tarState) {
//综合H1与H3
return (H1(curState, tarState) H3(curState));
}
//运行open算法，返回值取最短路径的step值
//运行open算法，返回值取最短路径的step值
int run(const int&st, const int &ed) {
if (!checkvalid(st, ed)) return -1;//检测是否可达，这样可以提高运行效率
//清理上一次程序运行时产生的数据。
open_key.clear();
open_value.clear();
closed.clear();
path.clear();
/*将初始结点放入open表中*/
int index = 0;//递增的序号值，唯一标识，便于查询pre路径
Snode start(st, 0, H2(st, ed), index , -1);//初始化初始结点start的值,其前驱路径的标号是-1，代表不存在
open_key.insert(make_pair<int, Snode>(int(H2(st, ed)), Snode(start)));//将初始结点放入open_key表中
open_value.insert(make_pair<Snode, int>(Snode(start), int(H2(st, ed))));//将初始结点放入open_value表中
//cout << open_key.begin()->first;
//if (success(target, target)) cout << "1" << endl;
/*对后续结点进行启发式搜索*/
while (open_key.size())
{
Snode mixNode = open_key.begin()->second;//取出open的第一个元素(该元素也是f值最小的结点)进行扩展
open_key.erase(open_key.begin()); //从open表中清除
open_value.erase(open_value.lower_bound(mixNode)); //从open表中清除
closed.insert(make_pair<int, bool>(int(mixNode.state), bool(true))); //将序列放入closed表中，具体的结构值放入path中
path.push_back(mixNode);//将结点的具体结构放入path中
//如果是已经到达目标路径，返回最短路径值step
if (success(mixNode.state, ed)) {
//cout << "1" << endl;
return mixNode.g;
}
//cout << mixNode.state << endl;
//outPut(mixNode.state);
/*对取出的结点进行移动操作，生成新的子节点。*/
//寻找空格的位置
int cx = -1, cy = -1;
board tmp;
int tmps;
state_toArc(mixNode.state, tmp);
//cx，cy代表空格的坐标[cx,cy]
for (int i = 1; i <= 3; i ) {
if (cx != -1) break;
for (int j = 1; j <= 3; j ) {
if (tmp[i][j] == 0)
{
cx = i;
cy = j;
break;
}
}
}
//移动生成子结点
for (int k = 0; k < 4; k ) {
int nx = cx move_x[k];
int ny = cy move_y[k];
if (nx >= 1 && nx <= 3 && ny >= 1 && ny <= 3)//保证移动后的空格不越界
{
swap(tmp[cx][cy], tmp[nx][ny]);//将原来空格和移动后的空格应在的位置的元素，交换顺序
tmps = arc_toState(tmp); //提取出新生成的状态序列state值
swap(tmp[cx][cy], tmp[nx][ny]);//还原序列，用于空格其他方向的移动
/*对新生成的子节点进行判定，是否入open表中*/
Snode newNode(tmps, mixNode.g 1, H2(tmps, ed), index , mixNode.cur);//初始化新生成的子节点
//新生成的子节点的state是tmps,深度是父节点mixNode的深度 1,h用判定函数h（x)求得,序列号按序 1，父节点序列号是mixNode的序列号cur
int newF = F(newNode);//保存新结点的F值
//查找新生成结点的state是否在closed表中
if (!closed.count(tmps))//如果不在closed表中，执行以下操作
{
//查找新生成结点的state是否在open表中
/*因为open表的两个元素并没有直接表示state值的选项，所以count函数不能用，查找元素的时候，就要自己重写一个查找算法
/按照传统的查找，必然是遍历每个元素，看open表中是否有元素的state值跟新结点的state值相同，这时候搜索效率就有点大，这就体现出来双map表的优势了
/双map表，key-value,value-key，在查找元素的时候，不用遍历，直接利用low_bound()函数找value-key表中的的first值value
/在value-key表中，first值value的从小到大的排列顺序是新类型Snode的比较大小的过程，在定义的时候已经定义，若Snode a==Snode b,必然是它们俩的序列值state值相同，<号也是state值相比较的
*/
map<Snode, int>::iterator it_v = open_value.lower_bound(newNode);
//itv指针指向state值>=newNode的迭代器元素，如果该元素的first值恰好=newNode,说明newNode的序列值state在open表中存在，这就是查找的办法了。
map<int, Snode>::iterator it_k;//创建指向key-value表迭代器的指针it_k
//如果在open表中
if (it_v != open_value.end() && it_v->first == newNode) {
//如果新生成的结点是相对于原open表中结点的最优解
if (newF < F(it_v->first)) {
for (it_k = open_key.lower_bound(F(it_v->first)); it_k != open_key.upper_bound(F(it_v->first)); it_k)
if (it_k->second == newNode) break;
//删除原有open表中结点
open_key.erase(it_k);
open_value.erase(it_v);
//将新结点加入open表中
open_key.insert(make_pair<int, Snode>(int(newF), Snode(newNode)));
open_value.insert(make_pair<Snode, int>(Snode(newNode), int(newF)));
}
//不是最优解，放弃新生成的结点
}
//既不在open表中，也不在closed表中
else {
//将新结点加入open表中
open_key.insert(make_pair<int, Snode>(int(newF), Snode(newNode)));
open_value.insert(make_pair<Snode, int>(Snode(newNode), int(newF)));
}
}
else if (closed.count(tmps)) //如果在closed表中，执行以下操作
{
//不用判断是否在open表中，因为想先入closed表必须先入open表，想插入一个结点到open表时，如果它已经在closed表中，是不会把它放到open表里的
//查找到closed表里的具体结构path中保存的旧Snode，比较f值，看是否新结点是更优解
int locate;
for (locate = 0; locate < path.size(); locate ) {
if (path[locate] == newNode) break;//Snode类型的==号代表state值相同
}
//如果是更优解
if (newF < F(path[locate]) && (path[locate].state == tmps)) {
//将原closed表中的元素删除，将新结点放入open表中。新结点的路径在新结点初始化时就已经保存，新结点的f值在加入open表时进行保存
closed.erase(closed.lower_bound(newNode.state));
path.erase(path.begin() locate);
//将新结点加入open表中
open_key.insert(make_pair<int, Snode>(int(newF), Snode(newNode)));
open_value.insert(make_pair<Snode, int>(Snode(newNode), int(newF)));
}
//如果不是更优解，舍弃新生成的结点newNode
}
/*对新生成的子节点进行判定，是否入open表中的判定结束*/
}
}/*对移动生成的新结点的整个操作结束*/
}
//函数走到这里，代表open表为空，则无解，返回步骤-1
return -1;
}
void inPut(board s) {
for (int i = 1; i <= 3; i ) {
for (int j = 1; j <= 3; j ) {
cin >> s[i][j];
}
}
}
void outPut(const int &e) {
board tmp;
state_toArc(e, tmp);
for (int i = 1; i <= 3; i) {
for (int j = 1; j <= 3; j)
cout << tmp[i][j] << " ";
puts("");
}
}
//要从后向前找到最优解的路径，采取的是后序遍历，那必然传递参数有pre,有step(第几步），由于查找时是查找path上的路径，path是依次进栈的方法加入元素
//故pre元素必定在子元素的前面
void findPath(int pre, int size, int step) {
if (step == -1) {
return;
}
else if (step == 0) {
cout << "Step-->" << step << endl;
cout << endl;
outPut(path[size].state);
cout << endl;
return;
}
for (int i = size; i >= 0; i--) {
//找到path中原结点的pre结点，递归调用函数，输出结果
if (path[i].cur == pre) findPath(path[i].pre, i, step - 1);
}
cout << "Step--> " << step << endl;
cout << endl;
outPut(path[size].state);
cout << endl;
}
//非要写个这个调用函数，而不是直接在main函数中调用，是因为在main函数中，它提示我path的iterator越界，我也不知道为什么，可能跟这个变量跨cpp文件有关吧
void isOk(int step) {
findPath((path.end() - 1)->pre, path.size() - 1, step);
}main.cpp文件
代码语言：javascript复制#include"windows.h"
#include"global.h"
#include"function.h"
//将一维数字转换为二维数组
int main() {
double time = 0;
double counts = 0;
LARGE_INTEGER nFreq;
LARGE_INTEGER nBeginTime;
LARGE_INTEGER nEndTime;
QueryPerformanceFrequency(&nFreq);
QueryPerformanceCounter(&nBeginTime);//开始计时
board st, ed;
freopen ("1.txt", "r ",stdin);
inPut(st);
inPut(ed);
int step = run(arc_toState(st), arc_toState(ed));
if (step != -1)
{
cout << "有解，最短路径是" << step << endl;
isOk(step);
}
else {
cout << "不可达" << endl;
}
QueryPerformanceCounter(&nEndTime);//停止计时
time = (double)(nEndTime.QuadPart - nBeginTime.QuadPart) / (double)nFreq.QuadPart;//计算程序执行时间单位为s
cout << "程序执行时间：" << time * 1000 << "ms" << endl;
return 0;
}运行例子：
注意，有的例子的搜索解的过程比较多，运行时间可能较长，请耐心等待
—————————————————————————————- 近期有同学因为交作业来看了一下我之前写的这篇分析，提醒我居然还写过一个这个东西。 现在来看，其实还有很多不足，体现在： 1. 排版功底太差，有些逻辑化的表述用图表的形式可能更简洁明了一些
2. 对open表采取map形式储存，表述有些对新手不友好，没有解释清楚，状态点对应的F值其实是map的key值，而map的value值，其实是整个结构体Snode的值（Snode因为是新定义的结构体，所以说比较大小，要重写方法）
3. 对每个功能函数的参数选择问题，没有做详细的设计解释。
4. 对Snode的作用，没有做详细的介绍，其实这里的Snode功能有点类似java里面类的功能了。
以后有时间，我再修改一下吧哈哈哈哈，暂时就想到这么几个修改点。
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/158194.html原文链接：https://javaforall.cn
