九宫格的问题-Read.doc

九宫格的问题
姓名:施少敏学号:20721173 联系电话:********** 邮件:shishaomin724@
问题介绍
这个问题其实可以简单表述成,3*3的格子装了1至8,8个数字,数字是随机分布于各个格子中,问是否可以利用空格的格子,移动装有数字的格子最终达到某种序列?比如像常见的拼图游戏,8个图格,然后利用空白格移动图片格子使其成为一幅完整的图案。
如图1所示
图1 随机打乱的数字图格和目标状态
问题隐含的数学原理
这个问题其实涉及到数学中群论。目标状态问题可以归结为一个置换群的问题,一个任意的状态A最终如果能够达到目标状态F,那么我们可以说置换群的个数为1,如果只有50%的可能性,那么这个置换群的个数就是2了。置换群内部的状态可以互相转换,但是却不可能有A群中的状态转向B群中的状态互相转换的情形发生。九宫格的问题其实是一个奇偶置换群的实例,该群无论如何置换奇偶性都不变,所以如果开局和目标的奇偶性相同,就一定有解(因为经过有限次的置换一定循环),如果奇偶性不同,一定无解。
n*n的方格中放入1,2,3,…,n-1及一个空格,在任何一种状态A下,
定义:f(i)=k,表示i放在第k个格子中,k按照从左至右,从上到下排序;
定义:g(i,j)=1,如果(f(i)-f(j))(i-j)<0;否则为0;
定义:F(A)=∑ g(i,j),对所有i,j求和;
针对图1,其目标F(End)=0,其初始F(Begin)=12,其奇偶性相同,故有解。利用F函数可以解决所有n为奇数的情况。比如n=3, 因为移动空格只有2种方式:在同行中移动不改变F值,在不同行中移动F值+2,-2或不变,故初始和末态的状态不会发生改变。
问题隐含的人工智能原理
在数学上,我们虽然完美解决了问题是否存在解决方案的问题,但是实际上,我们需要实现这个方案的具体内容,即在存在解的情况下,如何移动最少的步数使其达到目标状态。人工智能的启发式搜索算法在这里派上了用场。所谓的启发式搜索就是对于许多应用过程,可以找到领域特有的知识来指导搜索过程,以提高工作效率,而这些知识称为启发式知识。
我们先给出状态空间搜索的概念,状态空间搜索,就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程,就是在解一个问题时,找到一条解题的过程可以从求解的开始到问题的结果。由于求解问题的过程中分枝有很多,主要是求解过程中求解条件的不确定性,不完备性造成的,使得求解的路径很多这就构成了一个图,我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找,直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支,再查找另一个分支,以至找到目标为止。这两种算法在数据结构书中都有描述,可以参看这些书得到更详细的解释。前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法,可是当状态空间十分大,且不预测的情况下就不可取了。他的效率实在太低,甚至不可完成。在这里就要用到启发式搜索了。启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索