大家好，又见面了，我是你们的朋友全栈君。
基于搜索策略的八数码问题求解
大作业题目：
基于搜索策略的八数码问题求解
大作业目的：
加深对搜索策略的理解，尤其是对启发式搜索的基本原理的理解，使学生能够通过编程实现图搜索的基本方法和启发式搜索算法，并能够解决一些应用问题。
大作业要求：
使用盲目搜索中的宽度优先搜索算法或者使用启发式搜索中的全局择优搜索或A*算法。每人提交一份大作业报告，该报告包括设计、实现、测试、实验对比结果分析、结论、个人体会与总结，具体见格式要求。大作业程序需验收通过。
大作业提交内容：课程大作业纸质报告1份；将课程大作业电子报告和课程大作业程序及代码压缩包提交至网络教学综合平台。
大作业提交截止时间：以网络教学综合平台中的截止时间为准。
对任意的八数码问题，给出求解结果。例如：对于如下具体八数码问题：
通过设计启发函数，编程实现求解过程，如果问题有解，给出数码移动过程，否则，报告问题无解。
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. 试分析在所有可能的初始状态和目标状态之间最长的最小移动步骤数是多少？
作者水平有限，如有问题，欢迎留言交流
PS:笔者一开始觉得第一个太麻烦，要写三个算法。而且当时对全局择优算法和A*算法的差别并没有太明显的认知，后来知道了，虽然在选择扩展OPEN结点时，全局择优和A*都是选择Open表中F值小的那一个，但是A*有一个查重过程（即查找即将扩展的结点是否在open表或者closed表中已经存在过），全局择优算法并无这个查重过程。这个查重过程的意义在于，同一个状态序列可能通过多个路径到达的，在F=G+H这个启发函数中，G是结点拓展深度，H是当前序列到目标序列的评估函数，所以对于同样的排列，H肯定是相同的，只是G不同罢了。所以在全局择优算法中，closed表中可能有两个结点的序列state相同，但是f不同，但是A*算法中closed表不会存在两个结点的state序列相同。
A*算法是对启发式算法A算法的一种改进，启发式算法，就是给每一种子状态一个F=G+H的函数评估，取F值小的（到目标路径代价最小的路径值）的一种情况进行拓展。这里的F是单调函数
启发式算法是对盲目搜索策略算法的一种改进，能够大幅提高搜索效率，但是关键在于启发式函数的选择，这一点跟剪枝法中剪枝函数的选择有些类似的思想。
介绍A算法，需要引入两个重要概念，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来代表，需要输出路径时进行解压操作即可了。（别问我怎么想到的，我是站在巨人的肩膀上知道的）
那么，讲到这，结构体定义很好写了（不过这个不是完全体，后面会遇到具体问题，进一步完善）
顺手推舟，将一维数字的解压函数和返回F值的函数写出来：
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的大小，因此需要重载 “<“和“==”符号，于是对结构体的写法进一步改进
接下来，写检查是否有解的函数：（按照大作业的要求，就是检查，初始序列和目标序列在逆序数的奇偶性上，是否同奇同偶。
接下来，是对4个启发式函数的定义和写法。 启发式函数的参数在考虑的时候，因为这个h值只跟状态序列的排列有关，与路径无关，所以形参自然是int state，int target
接下来写主函数 open表 的运行过程，根据伪代码的算法：
接下来是int run(const int& st,const int&ed)的具体代码（这个传递参数为什么是const int&,另一篇blog中会讲述）
接下来是寻找路径的函数，采取后序遍历的方法
补上input和output的写法
因为要比较效率，就要比较代码的运行时间，在main函数中定义即可
在这里还有一个问题需要探讨一下，就是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）函数
然后把原来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文件
function.h文件
function.cpp文件
main.cpp文件
运行例子：
注意，有的例子的搜索解的过程比较多，运行时间可能较长，请耐心等待
—————————————————————————————- 近期有同学因为交作业来看了一下我之前写的这篇分析，提醒我居然还写过一个这个东西。 现在来看，其实还有很多不足，体现在： 1. 排版功底太差，有些逻辑化的表述用图表的形式可能更简洁明了一些
2. 对open表采取map形式储存，表述有些对新手不友好，没有解释清楚，状态点对应的F值其实是map的key值，而map的value值，其实是整个结构体Snode的值（Snode因为是新定义的结构体，所以说比较大小，要重写方法）
3. 对每个功能函数的参数选择问题，没有做详细的设计解释。
4. 对Snode的作用，没有做详细的介绍，其实这里的Snode功能有点类似java里面类的功能了。