圖搜索-野人過河案例.doc

昆明理工大學(xué)信息工程與自動化學(xué)院學(xué)生實驗報告（ 2011 2012 學(xué)年 第 1 學(xué)期 ）課程名稱：人工智能 開課實驗室：信自樓計算機(jī)機(jī)房444 2011 年12月22 日專業(yè)班級學(xué)號姓名成績實驗名稱圖搜索野人過河案例指導(dǎo)教師教師評語 教師簽名： 年 月 日一、上機(jī)目的及內(nèi)容題目：設(shè)有3個傳教士和3個野人來到河邊，打算乘一只船從右岸到左岸去。該船的負(fù)載能力為兩人。在任何時候，如果野人人數(shù)超過傳教士人數(shù)，野人 就會把傳教士吃掉。他們怎樣才能用這條船安全的把所有人都渡過河去? 二、實驗原理及基本技術(shù)路線圖（方框原理圖或程序流程圖） 實驗原理分析 先來看看問題的初始狀態(tài)和目標(biāo)狀態(tài)，假設(shè)和分為甲岸和乙岸： 初始狀態(tài)：甲岸，3野人，3牧師； 乙岸，0野人，0牧師； 船停在甲岸，船上有0個人； 目標(biāo)狀態(tài)：甲岸，0野人，0牧師； 乙岸，3野人，3牧師； 船停在乙岸，船上有0個人； 整個問題就抽象成了怎樣從初始狀態(tài)經(jīng)中間的一系列狀態(tài)達(dá)到目標(biāo)狀態(tài)。問題狀態(tài)的改變是通過劃船渡河來引發(fā)的，所以合理的渡河操作就成了通常所說的算符，根據(jù)題目要求，可以得出以下5個算符： 渡1野人、渡1牧師、渡1野人1牧師、渡2野人、渡2牧師算符知道以后，剩下的核心問題就是搜索方法了，本算法采用深度優(yōu)先搜索，通過一個getSolutionSteps ()函數(shù)找出下一步可以進(jìn)行的渡河操作中的最優(yōu)操作，如果沒有找到則返回其父節(jié)點，看看是否有其它兄弟節(jié)點可以擴(kuò)展，然后用steps.iterator ()函數(shù)遞規(guī)調(diào)用step.hasNext ()，一級一級的向后擴(kuò)展。 搜索中采用的一些規(guī)則如下： 1、渡船優(yōu)先規(guī)則：甲岸一次運走的人越多越好（即甲岸運多人優(yōu)先），同時野人優(yōu)先運走；乙岸一次運走的人越少越好（即乙岸運少人優(yōu)先），同時牧師優(yōu)先運走； 2、不能重復(fù)上次渡船操作（通過鏈表中前一操作比較），避免進(jìn)入死循環(huán); 3、任何時候河兩邊的野人和牧師數(shù)均分別大于等于0且小于等于3； 4、由于只是找出最優(yōu)解，所以當(dāng)找到某一算符（當(dāng)前最優(yōu)先的）滿足操作條件后，不再搜索其兄弟節(jié)點，而是直接載入鏈表。5、若擴(kuò)展某節(jié)點a的時候，沒有找到合適的子節(jié)點，則從鏈表中返回節(jié)點a的父節(jié)點b，從上次已經(jīng)選擇了的算符之后的算符中找最優(yōu)先的算符繼續(xù)擴(kuò)展b。傳教士和食人者問題的全部可能狀態(tài)狀 態(tài)m, c, b狀 態(tài)m, c, b狀 態(tài)m, c, b狀 態(tài) 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傳教士和食人者問題的狀態(tài)空間圖1野人1牧師右岸結(jié)束開始左岸1野人1牧師2野人2牧師程序設(shè)計思想三、所用儀器、材料（設(shè)備名稱、型號、規(guī)格等或使用軟件）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) /若新的嘗試仍然不成功，再繼續(xù)嘗試takenSteps.pop();to.transferMen(from, menList);/ 若所有步驟都不成功，則執(zhí)行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);/* * 結(jié)合兩個河岸，提供數(shù)據(jù)對象 */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;/* * 提供一個靜態(tài)方法反映某一時刻的狀態(tài) */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;/* * 提供一個靜態(tài)方法完成深度優(yōu)先算法 */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);五、實驗過程原始記錄( 測試數(shù)據(jù)、圖表、計算等) 程序運行結(jié)果： 六、實驗結(jié)果、分析和結(jié)論（誤差分析與數(shù)據(jù)處理、成果總結(jié)等。其中，繪