商人過河問題

1、商人過河問題一、三名商人各帶一名隨從的情況1. 問題(略)2. 模型假設(shè) 當(dāng)一邊岸滿足隨從數(shù)大于商人數(shù)，但商人數(shù)為0時仍為一種安全狀 態(tài)； 小船至多可容納2人，且渡河時由隨從(或者商人)來劃船。3. 分析與建模商人過河需要一步一步實(shí)現(xiàn)，比如第一步：兩個仆人過河，第二步：一個 仆人駕船回來，第三步：又是兩個仆人過河，第四步：其中每一步都使當(dāng)前狀態(tài)發(fā)生變化，而且是從一種安全狀態(tài)變?yōu)榱硪环N安 全狀態(tài)。如果我們把每一種安全狀態(tài)看成一個點(diǎn)，又如果存在某種過河方式使 狀態(tài)“變到狀態(tài)幾 則在點(diǎn)和點(diǎn)b之間連一條邊，這樣我們把商人過河問題和 圖聯(lián)系起來，有可能用圖論方法來解決商人過河問題。建模步驟：首先要確定過

2、河過程中的所有安全狀態(tài)，我們用二元數(shù)組(刃 表示一個安全狀態(tài)(不管此岸還是彼岸)，其中x表示留在此岸的主人數(shù)，y表 示留在此岸的隨從數(shù)。兩岸各有十種安全狀態(tài)：(0,0),(0,1 ),(0,2),(0,3),(2,2),( 1,1 ),(3,0),(3,1 ),(3,2),(3,3)4在兩岸的安全狀態(tài)之間，如存在一種渡河方法能使一種狀態(tài)變?yōu)榱硪环N 安全狀態(tài)，則在這兩種狀態(tài)之間連一條邊。這樣，得到如下一個二部圖(圖1), 其中下方頂點(diǎn)表示此岸狀態(tài)，上方頂點(diǎn)表示彼岸狀態(tài)。我們的目的是要找出一 條從此岸(3,3)到彼岸(0.0)的最短路。觀察發(fā)現(xiàn)此岸的狀態(tài)(0,0), (3,0)和彼岸的狀態(tài)(0,3

3、), (3,3)都是孤立點(diǎn),在求最短路的過程中不涉及這些點(diǎn)，把它們刪去。兩岸的點(diǎn)用1,2,，16重 新標(biāo)號。(3,3)(3,2)(3,1)(3,0)(1,1) (2,2)(0,3)(0,2)(0,3)(0,0)O O OOOGO(3,3)(3,2)(3,1)(3,0)(1,1)(2,2)(0,3)(0,2)(0,3)(0,0)(圖1)4模型求解求最短路程的matlab程序如下：function route=sroute(G, opt)%求圖的最短路的Dijkstra算法程序，規(guī)定起點(diǎn)為1,頂點(diǎn)連續(xù)編號%G是給定圖的鄰接矩陣或弧表矩陣，程序能夠自動識別%當(dāng)。20 (或缺省)時求無向圖的最短路，當(dāng)

4、opt=l時求有向圖的最短路%d標(biāo)記最短距離%route是一個矩陣，第一行標(biāo)記頂點(diǎn)，第二行標(biāo)記1到該點(diǎn)的最短路，第三行標(biāo)記最短路上 該點(diǎn)的先驅(qū)頂點(diǎn)while 1%此循環(huán)自動識別或由弧表矩陣生成鄰接矩陣if G(l,l)=0A=G;breakelsee=Gn=max(e(:, 1) ;e(: 2);%頂點(diǎn)數(shù)DFsizeCe, 1);M=sum(e(:, 3);A=M*ones(n, n);%邊數(shù)%代表無窮大for k=l:mA(e(k, 1), e(k, 2)=e(k, 3);if opt=0A(e(k, 2),e(k, l)=e(k, 3);%形成無向圖的鄰接矩陣endendA=A-M*eye

5、(n)endbreakendpb (1: length (A)=0;pb (1) =1;%形成圖的鄰接矩陣indcxl=l; index2=ones(1, length(A);d (1: length (A)=M;d (1) =0; temp=l;%標(biāo)記距離while sum(pb)=2index二index；end%記錄前驅(qū)頂點(diǎn)index2(temp)=index;endroute=1:n;d;index2;在matlab的命令窗口輸入圖(1)的弧表矩陣e:e=l 2;1 4;1 10;3 4;3 6;3 10;5 6;5 8;7 14;7 16;9 8;9 12;11 12;11 14;

6、13 14;13 16;15 16;e=e, ones(17,1);%邊權(quán)都設(shè)為 1調(diào)用程序： route=sroute(e, 0)運(yùn)行結(jié)果：e =121141110134136131015615817141716198191211112111141131411316115161route =1234567891011 121314151601214310561871091211114163145811291411167這表示存在一條從1到16的長度為11的路：14 3 6 51211 14 7 16,此路對應(yīng)商人成功渡河的一個方案:(3,3)變?yōu)?3,1)變?yōu)?3,2)變?yōu)?3,0)變?yōu)?3

7、,1)變?yōu)?1,1) 變?yōu)?2,2)變?yōu)?0,2)變?yōu)?0,3)變?yōu)?0,1)變?yōu)?1,1)變?yōu)?0,0)即：兩個仆人過河，一個仆人回來；有兩個仆人過河，一個仆人回來；兩 個主人過河，一主一仆回來；有兩個主人過河，一個仆人回來；兩個仆人過河, 一個仆人回來；最后兩個仆人過河。這樣，商人安全過河。若把剛才的最短路上的邊權(quán)全部改大，如取2或3,重新運(yùn)行程序，得到同 樣的結(jié)果，但實(shí)際上還有另外一種安全渡河狀態(tài)：(3, 3)變?yōu)?2, 2)變?yōu)?3, 2)變?yōu)?3, 0)變?yōu)?3,1)變?yōu)?1,1)變?yōu)?2, 2)變?yōu)?0, 2)變?yōu)?0, 3)變?yōu)?0,1)變?yōu)?0, 2)變?yōu)?0, 0)5.圖解法

8、將十種安全狀態(tài)的點(diǎn)在直角坐標(biāo)系中標(biāo)出，如下圖(0,0), (0,1), (0,2), (0,3), (2,2), (1,1), (3,0), (3,1), (3,2), (3,3) (實(shí)線表示才此岸開往彼岸，虛線表示才彼岸開往此岸)Sti圖中4到右給出了商人安全渡河的一條路徑。二、四名商人各帶一名隨從1問題：四名商人各帶一名隨從時，就附加說明條件才能實(shí)現(xiàn)安全渡河。2.原模型求解改編程序重新運(yùn)行，或用遞歸的方法程序運(yùn)行，結(jié)果運(yùn)行出現(xiàn)錯誤或死機(jī), 這說明模型無解，即四名商人各帶一名隨從在原條件下無安全狀態(tài)渡河。所以我們需附加一定的條件，使模型有解。由第一問中的條件可知：商人 渡河的限制條件是在任何

9、一邊岸商人數(shù)一定要比隨從數(shù)多且小船最多只能載2 人，而安全狀態(tài)(即商人數(shù)比隨從數(shù)多)是最其本的前提條件，因此我們考慮 更改小船的容量來實(shí)現(xiàn)安全渡河。3.新模型及求解當(dāng)小船的容量為5或大于5時，顯然一種安全渡河方式為：先4名隨從渡 河，1名隨從回來；隨后4名商人與回來的那名隨從一起渡河。當(dāng)小船容量為4 時，一種渡河方案為：先4名隨從渡河，1名隨從回來；再3名商人渡河，1名 商人和1名隨從回來；最后2名商人和2名隨從一起渡河?，F(xiàn)在我們考慮小船容量為3時的情況：（在這我們用圖解法來完成） 9步渡河方案（如圖所示）：01234圖即：第一步先三名隨從過河，一名隨從回來；再兩名商人過河，一名商人 和一名隨從回來；再三名商人過河，一名隨從回來；再三名隨從過河，一名隨 從回來；最后兩名隨從過河。 11步度河方案（如圖所示）:01234x圖即：第一步先一名商人和一名隨從過河，一名商人回來；再三名隨從過河, 一名隨從回來；再三名商人過河，一名商人和一名隨從回來；再兩名商人過河, 一名隨從回來；最后