宝塔服务器面板,一键全能部署及管理,送你10850元礼包,点我领取

经典的八数码问题,这几天尝试了一些不同的做法,现在总结下。

1.广搜+哈希

这是最容易想到的一种做法,哈希的方法是康托展开,组合数学上有介绍。

广搜+哈希

2.双向广搜+哈希

双向广搜的复杂度大约是单向的一半,所以效率上会有不错的提高。

双向广搜+哈希

3.A*+哈希+曼哈顿距离

用到广搜,就可以想到能用经典的A*解决,用深度作为g(n),剩下的自然是启发函数了。对于八数码,启发函数可以用两种状态不同数字的数目。接下来就是A*的套路,A*的具体思想不再赘述,因为人工智能课本肯定比我讲的清楚。但是必须得注意到,A*需要满足两个条件:

1.h(n)>h'(n),h'(n)为从当前节点到目标点的实际的最优代价值。

2.每次扩展的节点的f值大于等于父节点的f值小。

自然,我们得验证下我们的启发函数,h验证比较简单不用说,由于g是深度,每次都会较父节点增1。再看h,认识上, 我们只需要将h看成真正的“八数码”,将空格看空。这里,就会发现,每移动一次,最多使得一个数字回归,或者说不在位减一个。 h最多减小1,而g认为是深度,每次会增加1。所以,f=g+h, 自然非递减,这样,满足了A*的两个条件,可以用A*了!

A*+哈希+曼哈顿距离

4.IDA*+曼哈顿距离

因为要用到IDA*搜索,所以我们搜索之前先判断一下是否有解。

判断的方法是学习一个大神的: 判断八数码问题是否有解 

IDA*比起BFS的好处是空间复杂度极低,同时因为有剪枝,比起BFS降低了盲目性;比起A*的好处是不用去维护一个堆。

IDA*+曼哈顿距离