【vc++精品源码栏目提醒】:网学会员为广大网友收集整理了,【精品】人工智能实_八数码问题 - 其它资料,希望对大家有所帮助!
用 A算法解决八数码问题1 问题描述1.1 待解决问题的解释 八数码游戏(八数码问题)描述为:在 3×3 组成的九宫格棋盘上,摆有八个将牌,每一个将牌都刻有 1-8 八个数码中的某一个数码。
棋盘中留有一个空格,允许其周围的某一个将牌向空格移动,这样通过移动将牌就可以不断改变将牌的布局。
这种游戏求解的问题是:给定一种初始的将牌布局或结构(称初始状态)和一个目标的布局(称目标状态),问如何移动将牌,实现从初始状态到目标状态的转变。
1.2 问题的搜索形式描述(4 要素) 初始状态: 8 个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。
其中,状态空间中的任一种状态都可以作为初始状态。
后继函数: 通过移动空格(上、下、左、右)和周围的任一棋子一次,到达新的合法状态。
目标测试: 比较当前状态和目标状态的格局是否一致。
路径消耗: 每一步的耗散值为 1,因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。
1.3 解决
方案介绍(原理) 对于八数码问题的解决,首先要考虑是否有答案。
每一个状态可认为是一个 1×9 的矩阵,问题即通过矩阵的变换,是否可以变换为目标状态对应的矩阵?由数学知识可知,可计算这两个有序数列的逆序值,如果两者都是偶数或奇数,则可通过变换到达,否则,这两个状态不可达。
这样,就可以在具体解决问题之前判断出问题是否可解,从而可以避免不必要的搜索。
如果初始状态可以到达目标状态,那么采取什么样的方法呢?
常用的状态空间搜索有深度优先和广度优先。
广度优先是从初始状态一层一层向下找,直到找到目标为止。
深度优先是按照一定的顺序前查找完一个分支,再查找另一个分支,以至找到目标为止。
广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。
这在状态空间不大的情况下是很合适的算法,可是当状态空间十分大,且不预测的情况下就不可取了。
他的效率实在太低,甚至不可完成。
由于八数码
问题状态空间共有9个状态,对于八数码问题如果选定了初始状态和目标状态,有 9/2 个状态要搜索,考虑到时间和空间的限制,在这里采用 A算法作为搜索策略。
在这里就要用到启发式搜索 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。
这样可以省略大量无畏的搜索路径,提到了效率。
在启发式搜索中,对位置的估价是十分重要的。
采用了不同的估价可以有不同的效果。
启发中的估价是用估价函数表示的,如:fn gn hn 其中 fn 是节点 n 的估价函数,gn是在状态空间中从初始节点到 n 节点的实际代价,hn是从 n 到目标节点最佳路径的估计代价。
在此八数码问题中,显然 gn就是从初始状态变换到当前状态所移动的步数, 估计函数 fn我们就可采用当前状态各个数字牌不在目标状态未知的个数,即错位数。
2 算法介绍2.1 搜索算法一般介绍 不管哪种搜索,都统一用这样的形式表示:搜索的对象是一个图,它面向一个问题,不一定有明确的存储形式,但它里面的一个结点都有可能是一个解(可行解),搜索的目的有两个方面,或者求可行解,或者从可行解集中求最优解。
搜索算法可分为两大类:无信息的搜索算法和有信息的
搜索算法。
无信息的搜索又称盲目搜索,其特点是只要问题状态可以形式化表示,原则上就可用使用无信息的搜索,无信息搜索有如下常见的几种搜索策略:广度优先搜索、代价一致搜索、深度优先搜索、深度有限搜索、迭代深入优先搜索、双向搜索。
我们说 DFS 和 BFS 都是蛮力搜索,因为它们在搜索到一个结点时,在展开它的后续结点时,是对它们没有任何‘认识’的,它认为它的孩子们都是一样的‘优秀’,但事实并非如此,后续结点是有好有坏的。
好,就是说它离目标结点‘近’,如果优先处理它,就会更快的找到目标结点,从而整体上提高搜索性能。
为了改善上面的算法,我们需要对展开后续结点时对子结点有所了解,这里需要一个估值函数,估值函数就是评价函数,它用来评价子结点的好坏,因为准确评价是不可能的,所以称为估值。
这就是我们所谓的有信息搜索。
如果估值函数只考虑结点的某种性能上的价值,而不考虑深度,比较有名的就是有序搜索(Ordered-Search),它着重看好能否找出解,而不看解离起始结点的距离(深度)。
如果估值函数考虑了深度,或者是带权距离(从起始结点 ,那就是 A如果不考虑深度,就是说不要求最少步数,移动一步到目标结点的距离加权和)就相当于向后多展开一层结点,深度多算一层,如果要求最少步数,那就需要用 A。
简单的来说 A就是将估值函数分成两个部分,一个部分是路径价值,另一个部分是一般性启发价值,合在一起算估整个结点的价值, 考虑到八数码问题的特点,在