《人工智能》之课程实验

估价函数f(n) = g(n) + h(n) 其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。 设g(n)为已经移动的步数。在move函数中，每次移动加1即可。 设h(n)为此状态与目标状态中相异数字的个数。由a_start_h函数求得：

open表与close表的维护 open表：可以简单认为是一个未搜索节点的表 close表：可以简单认为是一个已完成搜索的节点的表（即已经将下一个状态放入open表内） 规则一：对于新添加的节点S（open表和close表中均没有这个状态），S直接添加到open表中。 规则二：对于已经添加的节点S（open表或者close表中已经有这个状态），若在open表中，与原来的状态S_0的f(n)比较，取最小的一个。若在close表中，那就分成两种情况：第一种，close表中的该状态S_0的f(n)大于S的，不做修改；第二种S_0的f(n)小于S的,那就要需要将close表中S_0的f(n)更新，同时将该状态移入到open表中。 规则三：下一个搜索节点的选择问题，选取open表中f(n)的值最小的状态作为下一个待搜索节点 规则四：每次需要将带搜索的节点下一个所有的状态按照规则一、二更新open表，close表，搜索完该节点后，移到close表中。

无解情况 将九宫格变成线性后，计算初始状态和目标状态的奇偶性是否一致，一致有解，否则无解。