以下几个算法都是以实现8数码问题为背景的.
8数码问题的描述如下:
目标:
1 2 3
8 0 4
7 6 5
初始状态任意.其中'0'代表一个空格,每次移动只能是空格的'上','下','左','右'移动.
很容易我们会想到,这样的一个图,可能出现9!个状态,但是其中有一半的状态是我们不希望看到的,也就是无解的状态.很容易证明当我们把上面的状态表示成一个序列以后,不论空格做出什么样的移动,之后得到的序列(不考虑'0')的逆序数的性质是不变的.也就是说,如果原来是奇数,移动以后的逆序数依然是个奇数.考虑到目标状态的逆序数是个偶数,所以只有9!/2的状态才可以达到目标.
首先放个广度优先的算法.
思想:
while(队列不空)
{
取队列的头节点;
if(该节点不是目标,)
{
扩展,并把其未被访问的子节点加入队列的尾部;
}
}
广度优先算法的特点是可以找到最优解.但是空间和时间消耗都比较大.其他的慢慢放上来,包括有: 深度优先,A*算法,IDA*,迭代深度优先等等.
广度优先算法的程序见我的文集.
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。