图搜索-野人过河案例.doc

昆明理工大学信息工程与自动化学院学生实验报告（ 2011 2012 学年 第 1 学期 ）课程名称：人工智能 开课实验室：信自楼计算机机房444 2011 年12月22 日专业班级学号姓名成绩实验名称图搜索野人过河案例指导教师教师评语 教师签名： 年 月 日一、上机目的及内容题目：设有3个传教士和3个野人来到河边，打算乘一只船从右岸到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，野人 就会把传教士吃掉。他们怎样才能用这条船安全的把所有人都渡过河去? 二、实验原理及基本技术路线图（方框原理图或程序流程图） 实验原理分析 先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸： 初始状态：甲岸，3野人，3牧师； 乙岸，0野人，0牧师； 船停在甲岸，船上有0个人； 目标状态：甲岸，0野人，0牧师； 乙岸，3野人，3牧师； 船停在乙岸，船上有0个人； 整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符： 渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师算符知道以后，剩下的核心问题就是搜索方法了，本算法采用深度优先搜索，通过一个getSolutionSteps ()函数找出下一步可以进行的渡河操作中的最优操作，如果没有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用steps.iterator ()函数递规调用step.hasNext ()，一级一级的向后扩展。 搜索中采用的一些规则如下： 1、渡船优先规则：甲岸一次运走的人越多越好（即甲岸运多人优先），同时野人优先运走；乙岸一次运走的人越少越好（即乙岸运少人优先），同时牧师优先运走； 2、不能重复上次渡船操作（通过链表中前一操作比较），避免进入死循环; 3、任何时候河两边的野人和牧师数均分别大于等于0且小于等于3； 4、由于只是找出最优解，所以当找到某一算符（当前最优先的）满足操作条件后，不再搜索其兄弟节点，而是直接载入链表。5、若扩展某节点a的时候，没有找到合适的子节点，则从链表中返回节点a的父节点b，从上次已经选择了的算符之后的算符中找最优先的算符继续扩展b。传教士和食人者问题的全部可能状态状 态m, c, b状 态m, c, b状 态m, c, b状 态 m, c, bS03,3,1S81,3,1S163,3,0S241,3,0S13,2,1S91,2,1S173,2,0S251,2,0S23,1,1S101,1,1S183,1,0S261,1,0S33,0,1S111,0,1S193,0,0S271,0,0S42,3,1S120,3,1S202,3,0S280,3,0S52,2,1S130,2,1S212,2,0S290,2,0S62,1,1S140,1,1S222,1,0S300,1,0S72,0,1S150,0,1S232,0,0S310,0,0021111010320220321311020S0S17S2111011002S1S2200111013310120S290210S30S140119300S5221S10S12031S24110S1831002S13000传教士和食人者问题的状态空间图1野人1牧师右岸结束开始左岸1野人1牧师2野人2牧师程序设计思想三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及eclipse软件四、实验方法、步骤（或：程序代码或操作过程）问题中的传教士、野人和船都是非常简单的物件，所以就简单地用单字符字符串“m”、“c” 和 “v”来代表。 import java.util.*;import java.io.*;public class MACPS public class SolutionNotFoundException extends RuntimeException static final Object MISSIONARY = m, / m指代传教士CANNIBAL = c, / c指代野人BOAT = v; / v指代船private int boat_max_load, boat_min_load = 1; private RiverScene firstScene, finalScene;private Collection getSolutionSteps(Stack takenSteps) RiverScene lastScene = (RiverScene) takenSteps.peek();if (lastScene.equals(finalScene)return takenSteps;RiverScene newStep = lastScene.deepCopy();int start = boat_max_load, stop = boat_min_load - 1, step = -1;RiverSide from = newStep.lside, to = newStep.rside;if (to.hasBoat() start = boat_min_load;stop = boat_max_load + 1;step = 1;from = newStep.rside;to = newStep.lside;for (int nPassenger = start; nPassenger != stop; nPassenger += step) Collection menCombs = new HashSet(Cbinations(from.getMenList(), nPassenger);nextComb: for (Iterator comb = menCombs.iterator(); comb.hasNext();) Collection menList = (Collection) comb.next();try from.transferMen(to, menList);for (Iterator i = takenSteps.iterator(); i.hasNext();)if (i.next().equals(newStep) to.transferMen(from, menList);continue nextComb;takenSteps.push(newStep);return getSolutionSteps(takenSteps); catch (SecurityException e) / 若运送不成功，则尝试另外的一个组合 catch (SolutionNotFoundException e) /若新的尝试仍然不成功，再继续尝试takenSteps.pop();to.transferMen(from, menList);/ 若所有步骤都不成功，则执行throw new SolutionNotFoundException();public Collection getSolutionSteps(int nMissionary, int nCannibal,int boatCapacity) if (nMissionary 0 | nCannibal 0 | boatCapacity 0 & mCount cCount;public void transferMen(RiverSide destination, Collection menList) for (Iterator i = menList.iterator(); i.hasNext();)destination.men.add(men.remove(men.indexOf(i.next();if (fatal() | destination.fatal() destination.transferMen(this, menList);throw new SecurityException();private void _transferBoat(RiverSide destination) destination.boat.add(boat.remove(0);/* * 结合两个河岸，提供数据对象 */class RiverScene implements Serializable RiverSide lside, rside; public RiverScene(RiverSide lside, RiverSide rside) this.lside = lside.deepCopy();this.rside = rside.deepCopy();public RiverScene deepCopy() return (RiverScene) Copy.deepCopy(this);public boolean equals(Object otherScene) RiverScene other = (RiverScene) otherScene;return lside.equals(other.lside) & rside.equals(other.rside);public String toString() return Left Side:t + lside + n + Right Side:t + rside;/* * 提供一个静态方法反映某一时刻的状态 */class Combinatorics public static Collection combinations(Collection items, int r) if (r = 0) return Collections.nCopies(1, new ArrayList();List copy = new ArrayList(items), result = new ArrayList();for (int i = 0; i copy.size(); +i) Collection subCombs = combinations(copy.subList(i + 1, copy.size(), r - 1);for (Iterator iter = subCombs.iterator(); iter.hasNext();)List subComb = new ArrayList(copy.subList(i, i + 1);subComb.addAll(List) iter.next();result.add(subComb);return result;/* * 提供一个静态方法完成深度优先算法 */class Copy public static Object deepCopy(Object o) try ByteArrayOutputStream baos = new ByteArrayOutputStream();ObjectOutputStream oos = new ObjectOutputStream(baos);oos.writeObject(o);oos.close();ObjectInputStream ois = new ObjectInputStream(new ByteArrayInputStream(baos.toByteArray();return ois.readObject(); catch (Exception e) throw new RuntimeException(e);五、实验过程原始记录( 测试数据、图表、计算等) 程序运行结果： 六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘