百度网站联盟,wordpress页面修改,苏州网站制作计划,石家庄网站建设机构From: http://blog.sina.com.cn/s/blog_4ed8b87701011c6x.html 这个问题其实可以简单表述成#xff0c;3*3的格子装了1至8#xff0c;8个数字#xff0c;数字是随机分布于各个格子中#xff0c;问是否可以利用空格的格子#xff0c;移动装有数字的格子最终达到某种序列3*3的格子装了1至88个数字数字是随机分布于各个格子中问是否可以利用空格的格子移动装有数字的格子最终达到某种序列比如像常见的拼图游戏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求和这里ij
针对图1其目标FEnd0其初始FBegin12f(1)1 f(2)9 f(3)3 f(4)4 f(5)8 f(6)2 f(7)7 f(8)5其奇偶性相同故有解。利用F函数可以解决所有n为奇数的情况。比如n3,因为移动空格只有2种方式在同行中移动不改变F值在不同行中移动F值2-2或不变,故初始和末态的状态不会发生改变。
问题隐含的人工智能原理
在数学上我们虽然完美解决了问题是否存在解决方案的问题但是实际上我们需要实现这个方案的具体内容即在存在解的情况下如何移动最少的步数使其达到目标状态。人工智能的启发式搜索算法在这里派上了用场。所谓的启发式搜索就是对于许多应用过程可以找到领域特有的知识来指导搜索过程以提高工作效率而这些知识称为启发式知识。我们先给出状态空间搜索的概念状态空间搜索就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程就是在解一个问题时找到一条解题的过程可以从求解的开始到问题的结果。由于求解问题的过程中分枝有很多主要是求解过程中求解条件的不确定性不完备性造成的使得求解的路径很多这就构成了一个图我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支再查找另一个分支以至找到目标为止。这两种算法在数据结构书中都有描述可以参看这些书得到更详细的解释。前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法可是当状态空间十分大且不预测的情况下就不可取了。他的效率实在太低甚至不可完成。在这里就要用到启发式搜索了。启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估得到最好的位置再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径提到了效率。在启发式搜索中对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。启发中的估价是用估价函数表示的如f(n) g(n) h(n)其中f(n)是节点n的估价函数g(n)实在状态空间中从初始节点到n节点的实际代价h(n)是从n到目标节点最佳路径的估计代价。
对于这个九宫格游戏我们采用如下的评价函数f(n) d(n) h(n)其中d(n)为当前状态从初始状态开始移动的步数h(n)计算当前状态与目标状态相比错位的个数。搜索过程总是往f(n)最小的分枝方向进行以便快速达到最终状态。
