广度优先搜索解决欧拉回路时间复杂度_A*算法解决八数码问题

好久没写C++了，前几天本来想玩一玩NumCpp写个算法试试，结果我的windows系统笔记本用Cmake死活链接不了boost库（这里说明懂得编译原理实际上很重要），有点伤心。昨天把八数码问题的作业给补完了，结果一直跑不出结果来，以为是有bug或者是自己写的太慢。后面改了改一些核心代码降低了一些复杂度，而且单步调试走了一遍，发现没什么问题。换了测试样例以后才跑了出来……

封面：电影《昨日青空》

A*算法

A*算法是一种启发式搜索算法，启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。

我的理解，A*算法就是一个搜索最短路径的算法，相当于一个加强版的BFS。与BFS相比，它增加了先验知识对搜索的优先级进行调整，由于带有经验的指导可以使得搜索变得不那么随机。

算法核心公式

F = G + H

F - 决策的总代价
G - 从开始到决策时刻所花费的真实代价
H - 从决策时刻到目标的预估代价

其中G值是一个真实的代价，也就是从算法流程一开始到进行这个决策的时候，一共花费的代价。H值是一个预估的代价，这个是估计的结果，具体怎么估计是通过人的经验给的。最开始学到这个的时候我是觉得很惊讶的，觉得这个玩意比广搜要好很多，之前有和别人参加北大人工智能挑战赛（我主要就打了酱油），我想当时寻路应该用这个算法的。后来他们告诉我他们试过，效果不好…

在极端情况下，如果H是常量0，这个算法退化成广度优先搜索算法，即按照顺序的依次扩充每个节点。如果G是常量，这个算法退化成贪心算法，即每次扩充可以使下一次最优的节点。

每次进行决策的时候，A*算法选择遍历所有当前可能的决策，并执行使F最大的决策。

算法流程

其中的数据结构包括两个优先列表，Open表和Close表，其优先级按照节点的F值定义。还包括一颗树，用于纪录最佳路径的生成过程。

八数码问题

3×3九宫棋盘，放置数码为1 -8的8个棋牌，剩下一个空格，只能通过棋牌向空格的移动来改变棋盘的布局。要求：根据给定初始布局（即初始状态）和目标布局（即目标状态），如何移动棋牌才能从初始布局到达目标布局，找到合法的走步序列。

这个游戏有个大坑，实际上有些情况是无解的，就是无论你怎么调整，最后也不可能调整到目标状态，昨天我跑了十分钟也没跑出来的原因就是这个，判断是否有解的方法如下……

若两个状态展成的一维向量的 逆序奇偶性相同，则可相互到达，否则不可相互到达。

我自己还把代码从头到尾单步调试了一遍，确认了没有问题，价值观崩塌，我都觉得这个算法是坑人的了……事实证明在搞一个东西之前最好是把相关的知识了解一遍再着手做，否则可能会做很多无用功。

统计了一下上面那个样例的计算次数
G：经过了几次移动
H：距离当前状态与目标状态的不同值的个数
 
F = G+H：7次
F = G：34次
F = H：6次
 
//哈哈哈贪心的效果竟然比A*效果还要好

毕竟我们对一个启发式算法不能要求太高哈哈。

C++实现

这个代码实际上大部分是我一两个月前写的，现在回过头来改了改用的，其中有几个比较大的问题。

1. Open表和Close