基于A星算法的小动物过河问题研究.doc

基于A*算法的小动物过河问题研究摘要：A*算法是一种常见的启发式搜索算法使用A*算法能够快速在状态空间中搜索到W题比较好的解决方案本文通过对A*算法的分析，使用A*算法搜索 一个益智类游戏——六个小动物过河的解决方案，并从中找到最优解关键字:A*算法；代价；启发式搜索1.概述A*的算法己经广泛的运用于游戏路径寻找的算法中A*算法能够在复杂的 带权图类型数据结构中搜索出两个节点的路径相对于盲□搜索算法，A*算法 加入了启发式信息，算法可以利用这些信息优先搜索最冇可能得到解或者最冇可 能得到最优解的节点以加快算法的搜索过程，一旦得到一个解，算法返回这个解 A*算法的启发式信息提高搜索算法的响应速度，适用于各种对问题的解耍求不 商，而对反应速度要求高的应用，例如游戏巾在有障碍物的地图上游戏NPC的 移动路径自动选择，八数码问题求解等等但是，A*算法由于使用了启发式信 息來引导搜索过程，而且只要搜索到M题的一个解就停止，所以可能会错过问题 的最优解木文主耍利用A*算法来寻找一个益智类小游戏的答案，使用状态空 间法和隐式阁搜索的方式，搜索状态转移过程并找到问题的一个解2.问题描述所谓六个小动物过河问题是这样一种游戏：六个小动物，分别是大狮子、大 狼、大老虎、和他们的幼崽小狮子、小狼、小老虎乘船过河。

岸边只有一只船、 船中至多可以装载W只动物（可以有一只动物单独划船过河），并且过河的途中 需要其中一只动物驾驶船只三只大的动物之间不怀好意，从要看到其他大动物 不在幼崽身边就吃棹它们的幼崽，例如大狼如果发现大狮子不在小狮子身边，就 吃掉小狮子六只动物大狮子、大狼、大老虎都会划船，小动物中只宥小狮子会 划船，小狼和小老虎不会划船丌始时船和六只动物处于河流的同一边，动物过 河的过程中船只可以来冋摆渡，并且只有船和动物在一边，动物才可以划船过河 现在寻找一种过河方案，使得六只动物能够安全过河，即不发生大动物吃掉其他 动物幼崽的情况2.1待解决问题建模对上述问题进行状态空问建模，其中六个动物和船只的位置只有两种状态分 别为在河的一边和另一边问题的初始条件START代表六个小动物和船只都在 河流的一边，W题的终止状态END时六只动物和船只都在河流的另一•边问题 的中间状态STATE代表的是游戏开始后六只动物和船的位置在游戏过程中的状 态问题求解就是寻找一系列的状态（START〉STATE1〉STATE2〉..〉END）,其 中要求各个中问状态STATE1、STATE2......中所有的小动物都是安全的。

2.2问题的搜索形式描述使用七个状态标志位来描述问题的状态空1X1,分别为X=（BigLion、LittleLion、 BogWolf、LittleWolf、BigTiger、LittleTiger、Ship）这些标志分别只能取两个离 散的值，0或者1,其中0表示对应的事物在河流的一边，1表示在河流的另一 边问题的初始状态为（0、0、0、0、0、0、0），问题的目标状态是（1、1、1、1、1、1、1）状态发生转移的条件是小动物所在的一边有船且有乘船过河的动 物中至少宥一只动物能够划船，例如（0、0、0、0、0、0、0）能够转移到（1、 1、0,、0、0、0、1）,代表的实际意义是大狮子和小狮子乘船过河，过河后船在 河的另一边，而从（0、0、0、0、0、0、0）是不能够转移到（0、0、0、1、0、 1、1）的，这种转移的实际意义是小狼和小老虎划船过河，这显然不满足问题的 设定状态合法性条件是幼崽身边宥其他的大动物时，它的身边一定耍宥G己对 应的大动物在旁边保护，例如（1、0、1、0、0、0、1）是一个不合法的状态， 代表的意义是大狮子和大狼不在小狮子、小狼身边，大老虎会将他们吃掉求解 问题的过程就是在状态转移条件和状态合法性条件的限制K搜索一个从初始状 态到目标状态的序列，最1•通过这个状态序列来得到小动物的行动方案。

问题的求解实际上就是在状态空间中找到一条路径可以从初始状态到目标 状态，这个寻找的过程就是状态空间搜索经分析六个动物过河问题的搜索策略 共有：1.广度优先搜索；2.深度优先搜索；3.有界深度优先搜索；4.最好优先搜索；5.局部择优搜索，等等常用的状态空间搜索有深度优先和广度优先广度优先 是从初始状态一层一层A下找，直到找到0标为止深度优先是按照一定的顺序 前杳找完一个分支，再杳找另一个分支，以至找到目标为止由于宥些条件卜状 态空间有可能是无限的，每一个状态空间分支空间都可能不能在冇限的时间内穷 尽，所以一般会设置一个最大的搜索深度，控制搜索及时从一个分支返冋 启发式搜索就是对每一个搜索的位置进行评估，得到最好的位置，再从这个位置 进行搜索直到H标这样吋以省略人量无谓的搜索路径，提高了效率上述几个 方中广度优先搜索法是可采纳的，宥界深度优先搜索法是不完备的，最好优先和 局部择优搜索法是启发式搜索法下而讨论A*算法搜索3算法介绍3.1A*搜索算法般介绍A*算法实际是一种启发式搜索，所谓启发式搜索，就是利用一个估价函数 评佔每次的决策的价值，决定先尝试哪一种方案，这样可以极大的优化普通的广 度优先搜索。

一般來说，对于某个特定的W题，从起始状态START到0标状态 的最小代价固定的从一个状态过渡到另一个状态的代价是根裾实际问题定义的， 例如在阁的最短路径搜索问题中，代价可以定义为经过的边长度的和，在本问题 中代价定义为从游戏开始到某特定状态小动物划船的次数用估价函数f （A） 佔计从初始状态START经过某中间状态A到□标状态END的最小代价如果 搜索过程已经尝试着从START沿着某条转移路线移动到了状态A，那么我们认 为按照这种方案行动所花费的最小代价为从初始状态START到中间状态A的已 经花费的代价g（A）加上从状态A到状态END估计花费的最小代价h（A）公式表示为：f(A) = g(A) + h(A)其中h(A)小于等于A到口标状态的实际代价如此，无论搜索展开到哪一中间 状态A,都能用上述公式算出一个估价值f(A),每一次决策后，将各个待扩展的 中间状态的估价值放在一起排序，然G挑出待扩展中估价值最小的状态，也就是 是最有可能以最小代价达到目标状态的中间态，进行扩展产生中间节点如此以 往，直到对象移动到目的地，或所有方案都尝试过却没有找到一条通向目的地的 路径则结束3.2A*搜索算法的伪代码在算法的描述中将状态的空间中的状态看作搜索树中的节点。

首先定义两个 表，open表用于存放已经生成，且已用启发式函数进行过估计或评价，但尚未 产生它们的后继节点的那些结点，这些结点也称未考察结点；closed表用于存放已经生成，且已考察过的结点设SO为初态，Sg为口标状态 具体过程如下：(1) 把SO放入open表，记为f=h,令closed为空表2) 重复下列过程，直至找到目标结点为止若open为空表，则失败3) 选取open表中未设置过的具有最小f值的结点为最佳节点，并放入closed 表中4) 若最佳节点不是目标节点，则扩展之，产生后继节点5) 对每个f继结点进行卜*列过程：建立从该•继结点返回最佳节点的指针; 计算g (后继结点)=g (最佳节点)+k (最佳节点，后继结点)；Ss:如果该后 继节点eopen,则称此节点为old,并把它添加至最佳节点的后继节点中，比较 新旧路挽代价如果g (后继节点)

6) 计算f值7) GO LOOP3.3本问题中A*算法的设定动物过河问题求解，就是力求找到一条从初始节点到目标T点的最短路径 对于搜索过程中的某个中间状态A, g(A)定义为从游戏开始到当前状态已经滑动 小船的次数，h(A)定义为还没冇过河的动物的过河的只数显然这满足A*算法 的定义另外在状态搜索的过程中，为了避免在个状态之间的无限循环从而导致 算法在得不到解时无法正常退出每次扩展一个新的节点都会通过父指针向上回 溯，比较将要扩展的状态和其祖先状态是否和同，如果发现正在扩展的节点的状 态与其某个机先节点相同则不扩展该节点4. 算法实现4.1实验环境与问题规模(1) 实验环境：Windows7;(2) 实验编程工具 java MyEclipse8.5;(3) 问题规模算法规模小，最大搜索深度不超过404.2主要数据结构状态节点Node类型，具有level、parent、state三个属性其中level表示当 前节点与初始节点之间的M次数目，也就是已经花费的代价；parent为指向节点 上一个状态的指针，用于搜索到0标状态以后从0标状态回溯到初始状态丼得到 最终结果；state为表示动物和船状态的数组，七个字符的字符数组表示。

Open表和Close表用Node类型实例化Java的LinkedList泛型链表容器利 用容器的添加、查找、删除等功能来实现对Open表和Close表的管理4.3实验结果经测试，程序运行良好，并且提供命令行和图形界血两种界血求解过程结 果如下：Steph小狼、大狼从河的左边划船到河的心边，此时河的左边有:小虎、大 虎、小狮了、大狮了，此时河的右边有:小狼、大狼；Step2：大狼从河的巾边划船到河的左边，此吋河的左边有:小虎、大虎、大 狼、小狮子、大狮子，此时河的右边有:小狼；Step4：小虎、小狮子从河的左边划船到河的右边，此吋河的左边有:大虎、 大狼、大狮子，此时河的心边有:小虎、小狼、小狮子；Step5：小狮了从河的由边划船到河的左边:，此时河的左边有:大虎、大狼、小狮子、大狮子，此时河的右边有:小虎、小狼；Step6：大虎、大狼从河的左边划船到河的右边，此时河的左边有:小狮子、大狮子，此吋河的右边有:小虎、大虎、小狼、大狼；Step7：小虎、大虎从河的由边划船到河的左边，此时河的左边有:小虎、大 虎、小狮了、大狮了，此时河的右边有:小狼、大狼；Step8：小狮子、大狮子从河的左边划船到河的右边，此吋河的左边有:小虎、 大虎，此时河的右边有:小狼、大狼、小狮子、大狮子；Step9：小狼、大狼从河的由边划船到河的左边，此吋河的左边有:小虎、大 虎、小狼、大狼，此时河的心边有:小狮子、大狮子；StepIO：大虎、大狼从河的左边划船到河的右边，此时河的左边有:小虎、小 狼，此吋河的右边有:大虎、大狼、小狮子、大狮子；Stepll：小狮子从河的由边划船到河的左边:，此时河的左边有:小虎、小狼、 小狮子，此吋河的右边有:大虎、大狼、大狮子；Step 12：小虎、小狮子从河的左边划船到河的A边，此时河的左边有:小狼， 此时河的右边有:小虎、大虎、大狼、小狮了、大狮了；Stepl3：大狼从河的由边划船到河的左边:，此时河的左边有:小狼、大狼，此 时河的右边有:小虎、大虎、小狮子、大狮子；Stepl4：小狼、大狼从河的左边划船到河的右边，此吋河的左边没有动物，此时河的心边有:小虎、大虎、小狼、大狼、小狮子、大狮子。

此外为了更好地展示搜索fli的问题的解，我制作了兵有动画效果的图形界面, 运行示意图如下：4.4实验结果分析由于解决问题规模本身比较小，算法的执行儿乎感觉不到时问通过在程序 中插入打印信息发现算法优先搜索Y最优解所在的这条路径，符合扁发式搜索算 法执行过程随后去启发式信息，将算法退化为盲目搜索，算法执行时间明。