八数码盲目搜素的两种方法

这段时间。。。一直在训练,天天被大佬虐,也没时间和心情写一点垃圾的东西。

课文资料

八数码问题其实可以A*之类的强力(玄学)搜索方法用估计函数解决。但是蒻还没学会A*,所以就先对应两道八数码问题写两种盲目搜索的方式。

其实八数码问题就相当于一个bfs的最短路问题,只不过现在bfs的时候我们需要把一个九宫格的数字映射成一个结点(而且不会和其他状态相同)。这就需要介绍一个康托展开的东西了:康托展开

其实这个东西就相当于当前排列,在所有的全排列中是第几小,从而完成映射(hash).然后按照这个定义就可以写出hash部分的代码了。

然后来看个题。

hdu 1043 Eight(逆向bfs+康托展开+打表)

这道题目是多组数据,而且需要我们打印路径,而如果我们对于每一个输入都进行一次bfs的话就会发现tle了。这是因为这道题目的目标状态是固定的,其实我们从一个状态到目标状态的过程中是会经历很多重复的状态。也就是对于一个起始状态a我们可以搞出他到终点的最少步数,但是输入b状态的时候你有可能重复经历一次这个状态的查询,所以逆向bfs,找出所有状态到目标状态的最短路(因为我们在这个过程中可以记录状态的前驱状态,然后递归回去就可以了)。

 

其实这道题目太特殊了,因为他给出了目标状态。所以才可以这样搞。

hoj 1868 八数码

如果给出目标状态和起始状态,然后询问的话,就不能逆向搞了。我们可以双向搜索。个人理解就是把起点终点都压入队列。如果一个状态被两个方向都找到过,那么就找到最短路啦。注意标记好两个两个方向的不同标记,另外其实八数码可以快速判断是否有解。

方法就是若两个状态的逆序同奇偶,则有解,否则无解。不考虑空格

证明:把八数码看成一维的话,左右移动空格并不会影响逆序。上下移动空格,这就是一个数向前或者向后跳两格,所以逆序要么增加2要么不变。所以同奇偶是保证有解的充要条件。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注