昆明理工大學信息工程與自動化學院學生實驗報告（ 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);五、實驗過程原始記錄( 測試數據、圖表、計算等) 程序運行結果： 六、實驗結果、分析和結論（誤差分析與數據處理、成果總結等。其中，繪