圖搜索-野人過(guò)河案例.doc

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