matlab求解夫妻過河問題畢業(yè)論文

1、<p>　　論文題目: matlab求解夫妻過河問題</p><p><b>　　摘要</b></p><p>　　渡河問題.始于公元8 世紀(jì)，至今它仍是一個(gè)邏輯難題，許多數(shù)學(xué)建模教材上已經(jīng)提到.這個(gè)問題指的是：有不同的對象或生物，他們其中一些相互不共存，逐步地讓一小群體從河的一岸到另一岸，經(jīng)過有限步后，該群體全部從一岸達(dá)到另一岸，并且要求沒有任何損失．在渡

2、河問題的夫妻過河問題中我們發(fā)現(xiàn)狀態(tài)轉(zhuǎn)移問題有時(shí)不一定有解，有時(shí)的解又不一定有規(guī)律，本文對于夫妻過河問題利用圖解法和matlab編寫程序求解5對、6對夫妻過河是否有解，并推廣到對夫妻與船的運(yùn)載能力對于能否安全渡河時(shí)它們之間的關(guān)系。</p><p>　　關(guān)鍵詞：多步?jīng)Q策 matlab 數(shù)學(xué)模型 渡河問題</p><p>　　Problem of couples

3、0;across the river</p><p>　　Abstract: the problem of crossing the river. In the 8th century, it still is a logical problem, many mathematical modeling teaching material has been mentioned. The ques

4、tion is: have different objects or creatures, they lack some mutual coexistence, gradually to a small group from one bank to another bank of the river, after finite steps, the group all from one side to the other shore,

5、and requires no losses. In crossing the river problem of couples across the river, we found that state transiti</p><p>　　Keywords: Multistep decision Matlab Mathematical model Problem of crossing the r

6、iver</p><p><b>　　目 錄</b></p><p><b>　　1 引言1</b></p><p>　　2 文獻(xiàn)綜述1</p><p>　　2.1 國內(nèi)外研究現(xiàn)狀1</p><p>　　2.2 國內(nèi)外研究現(xiàn)狀評價(jià)2</p>&l

7、t;p>　　2.3 問題提出2</p><p>　　3 模型假設(shè)2</p><p>　　4 符號(hào)說明2</p><p>　　5 重述3、4對夫妻過河問題的解3</p><p>　　5.1 3對夫妻過河的解3</p><p>　　5.2 4對夫妻過河的解3</p><p&

8、gt;　　6 五對夫妻過河模型4</p><p>　　6.1 模型構(gòu)成4</p><p>　　6.2 模型建立4</p><p>　　6.3 模型求解4</p><p>　　6.31 Matlab編程求解4</p><p>　　6.32 圖解法7</p><p>　　7 六對

9、夫妻過河模型8</p><p>　　7.1 模型構(gòu)成8</p><p>　　7.2 模型求解9</p><p>　　8 n對夫妻過河情況10</p><p><b>　　8.1 求解10</b></p><p><b>　　8.2 驗(yàn)證11</b></p

10、><p>　　9 總結(jié)與展望12</p><p><b>　　9.1 總結(jié)12</b></p><p>　　9.2后續(xù)研究工作展望13</p><p><b>　　參考文獻(xiàn)14</b></p><p><b>　　附 錄15</b></p

11、><p><b>　　1 引言</b></p><p>　　這是一個(gè)古老的阿拉伯?dāng)?shù)學(xué)問題。有3對夫妻要過河，船最多可載2人，約束條件是根據(jù)阿拉伯法律，任一女子不得在其丈夫不在場的情況下與其他男子在一起，問此時(shí)這3對夫妻能否過河？如果是4對夫妻過河，其他條件不變的情況下，夫妻能否過河？就這一問題我們發(fā)現(xiàn)狀態(tài)轉(zhuǎn)移問題有時(shí)不一定有解，有時(shí)的解又不一定有規(guī)律（當(dāng)4對夫妻過河，其他

12、條件不變的情況下，夫妻能否過河？我們發(fā)現(xiàn)此問題是無解的），但是當(dāng)我們改變條件船最多可載3人時(shí)有解.</p><p>　　就其數(shù)學(xué)建模思想來說, 一般采用將該問題轉(zhuǎn)化為一個(gè)多步?jīng)Q策模型, 模型求解的方法大多為圖解法然而一旦問題的條件 (例如丈夫、妻子或者小船上每次渡河人數(shù)等) 發(fā)生變化, 圖解法求解猶如大海撈針!很難奏效. 因此計(jì)算機(jī)編程求解模型的方法就顯得非常重要了.該題求解編程的難點(diǎn)在于允許狀態(tài)與決策這兩個(gè)方面

13、的處理與實(shí)現(xiàn).</p><p>　　此問題中利用的多目標(biāo)決策方法是從20世紀(jì)70年代中期發(fā)展起來的一種決策分析方法.決策分析是在系統(tǒng)規(guī)劃、設(shè)計(jì)和制造等階段為解決當(dāng)前或未來可能發(fā)生的問題，在若干可選的方案中選擇和決定最佳方案的一種分析過程.在社會(huì)經(jīng)濟(jì)系統(tǒng)的研究控制過程中我們所面臨的系統(tǒng)決策問題常常是多目標(biāo)的，例如我們在研究生產(chǎn)過程的組織決策時(shí)，既要考慮生產(chǎn)系統(tǒng)的產(chǎn)量最大，又要使產(chǎn)品質(zhì)量高，生產(chǎn)成本低等。這些目標(biāo)之間

14、相互作用和矛盾，使決策過程相當(dāng)復(fù)雜使決策者常常很難輕易作出決策.這類具有多個(gè)目標(biāo)的決策總是就是多目標(biāo)決策. 多目標(biāo)決策方法現(xiàn)已廣泛地應(yīng)用于工藝過程、工藝設(shè)計(jì)、配方配比、水資源利用、能源、環(huán)境、人口、教育、經(jīng)濟(jì)管理等領(lǐng)域.</p><p><b>　　2 文獻(xiàn)綜述</b></p><p>　　2.1國內(nèi)外研究現(xiàn)狀</p><p>　　渡河問題有不

15、同的版本，從目前參閱的文獻(xiàn)資料中了解的信息來看文獻(xiàn)[1]、[5]、[6]的商人和隨從渡河問題利用通過遍歷狀態(tài)空間樹來搜索可行的渡河方案、建立多步?jīng)Q策模型、計(jì)算機(jī)編程等方法解決,文獻(xiàn)[3]、[4]的傳教士和食人族難題仿照整數(shù)( 二元) 規(guī)劃的圖示方法、用矩陣表示與迭代算法等方法解決，文獻(xiàn)[5]軍官渡河問題和人與機(jī)器渡河問題利用Dijkstra算法,文獻(xiàn)[13]的人、貓、雞、米過河問題利用計(jì)算機(jī)C語言編程求解，文獻(xiàn)[6]、[15]的人、狼、

16、羊、菜過河問題利用多為向量的方法解決.但是解決方法是類似的,都是要找到允許狀態(tài)和允許決策.</p><p>　　2.2國內(nèi)外研究現(xiàn)狀評價(jià)</p><p>　　綜上所述，渡河問題至今仍是一個(gè)邏輯難題.國內(nèi)外對于過河問題的研究很多，但是不是很全面，由于渡河問題的種類很多，盡管研究方法大體相同，但是他的解卻是有很多種，或者有的問題根本無解，就夫妻過河問題而言當(dāng)4對夫妻過河，船只能載2人時(shí)問題無解

17、.本文在夫妻過河問題的基礎(chǔ)上從3對、4對夫妻研究至5對、6對，并推至n對夫妻過河情況，利用圖解法和matlab編程解決.</p><p><b>　　2.3 問題提出</b></p><p>　　問題1：若船最多能載3人，5對夫妻能否過河？六對夫妻呢？如果不可以那么船最多能載幾人才可以？</p><p>　　問題2：n對夫妻要過河，船最多能載m

18、人，n和m有怎樣的關(guān)系？</p><p>　　任務(wù)：用matlab編寫程序求問題1的解，并用已有程序驗(yàn)證問題2.</p><p><b>　　3 模型假設(shè)</b></p><p>　　1.不考慮過河環(huán)境因素的影響情況；</p><p>　　2.夫妻過河只能依靠小船；</p><p>　　3.每個(gè)男

19、人和女人都會(huì)劃船；</p><p><b>　　4 符號(hào)說明</b></p><p><b>　　表示渡河的夫妻對數(shù)</b></p><p>　　表示第k次渡河前此岸丈夫的人數(shù)</p><p>　　表示第k次渡河前此岸妻子的人數(shù)</p><p>　　表示第次過渡船上丈夫的人數(shù)

20、</p><p>　　表示第次過渡船上妻子的人數(shù)</p><p><b>　　表示第幾次渡河</b></p><p><b>　　表示渡河的次數(shù)</b></p><p><b>　　表示允許狀態(tài)集合</b></p><p><b>　　表示允許

21、決策集合</b></p><p><b>　　表示狀態(tài)</b></p><p><b>　　表示決策</b></p><p>　　5 重述3、4對夫妻過河問題的解</p><p>　　有3對夫妻要過河，船最多可載2人，約束條件是根據(jù)阿拉伯法律，任一女子不得在其丈夫不在場的情況下與其他男子

22、在一起，問此時(shí)這3對夫妻能否過河？如果是4對夫妻過河，其他條件不變的情況下，夫妻能否過河？</p><p>　　記次過河前此岸丈夫的人數(shù)為，妻子的人數(shù)為.記表示狀態(tài)，=（）,記表示決策，=（）。</p><p>　　5.1 3對夫妻過河的解</p><p>　　5.2 4對夫妻過河的解</p><p>　　可看出問題無法再解下去</p&

23、gt;<p>　　6 五對夫妻過河模型</p><p><b>　　6.1模型構(gòu)成</b></p><p>　　記第次過河前此岸丈夫的人數(shù)為，妻子的人數(shù)為，=1,2，3……</p><p>　　由已知條件知可取狀態(tài)為（0,1）（0,2）（0,3）（0,4）（0,5）（0,0）（5,5）（5,4）（5,3）（5,2）（5,1）（5,

24、0）（1,1）（2,2）（3,3）（4,4）共16種，用表示可取狀態(tài)集合，成為允許狀態(tài)集合，不難驗(yàn)證，對此岸和彼岸都是可行的.</p><p>　　記第次過渡船上的丈夫的人數(shù)為，妻子的人數(shù)為，由已知條件知可取狀態(tài)為（0,1）（0,2）（0,3）（1,0）（2,0）（3,0）（1,1）（2,1），其中（1，1）表示1對夫妻，共五種，用表示可取狀態(tài)集合，成為允許決策集合. </p><p>&

25、lt;b>　　6.2模型建立</b></p><p>　　我們發(fā)現(xiàn)當(dāng)為奇數(shù)時(shí)船從此岸駛向彼岸，當(dāng)為偶數(shù)時(shí)船從此岸駛向彼岸，記表示狀態(tài)，=（）,記表示決策，=（）。所以狀態(tài)隨的變化規(guī)律為： </p><p><b>　　稱為狀態(tài)轉(zhuǎn)移律</b></p><p>　　求決策（=1,2，3……n）使?fàn)顟B(tài)按照狀態(tài)轉(zhuǎn)移律，由初始

26、狀態(tài)</p><p>　　=（1,1）有限步n到達(dá)狀態(tài)=（0，0）</p><p><b>　　6.3模型求解</b></p><p>　　6.31 Matlab編程求解</p><p>　　對于這個(gè)問題通常用“窮舉求解” 的方法， 即從初始狀態(tài)（5， 5）開始， 從允許決策集合D 中選擇一個(gè)決策， 產(chǎn)生一個(gè)新狀態(tài).若新

27、狀態(tài)可行， 則保存該狀態(tài)， 并從這個(gè)狀態(tài)開始繼續(xù)進(jìn)行決策尋找下一可行狀態(tài)； 否則， 從允許決策集合D 中重新選擇一個(gè)新決策以產(chǎn)生下一狀態(tài).如果某個(gè)狀態(tài)的所有可選決策產(chǎn)生的下一狀態(tài)均不可行， 則返回到上一個(gè)可行狀態(tài)， 從該可行狀態(tài)開始尋找除了狀態(tài)的其它狀態(tài)， 直到找到一個(gè)可行的下一狀態(tài).這個(gè)決策過程反復(fù)進(jìn)行， 直到到達(dá)最終狀態(tài)（0， 0），即可以安全渡河.其中，判斷狀態(tài)是否可行包括兩個(gè)方面： </p><p>　　

28、（1） 該狀態(tài)是否在允許狀態(tài)集合S 中.</p><p>　　（2） 在由決策所確定產(chǎn)生的一系列狀態(tài)中，船由此岸駛向彼岸前的所有狀態(tài)不允許重復(fù)， 船由彼岸駛向此岸前的所有狀態(tài)亦不允許重復(fù). </p><p>　　可以應(yīng)用人工智能原理中的狀態(tài)空間搜索法解決.首先定義一個(gè)安全渡河問題的狀態(tài)空間，規(guī)定出該空間的初始狀態(tài)和目標(biāo)狀態(tài)，建立相應(yīng)的渡河規(guī)則和控制策略，而后推理搜索，直至找出由初始狀態(tài)到目

29、標(biāo)狀態(tài)的某條路徑或一組路徑，即安全渡河的操作序列.用matlab編寫一段程序求解，程序編寫思路如下圖</p><p>　　程序運(yùn)行結(jié)果（程序見附錄）：</p><p><b>　　ans =</b></p><p>　　Columns 1 through 11 </p><p>　　5 5 5 5

30、 5 5 5 2 3 0 0</p><p>　　5 2 3 0 1 0 2 2 3 3 4</p><p>　　Columns 12 through 22 </p><p>　　0 0 0 -1 -1

31、 -1 -1 -1 -1 -1 -1</p><p>　　1 2 0 -1 -1 -1 -1 -1 -1 -1 -1</p><p>　　Columns 23 through 33 </p><p>　　-1 -1 -1 -1 -1 -1

32、 -1 -1 -1 -1 -1</p><p>　　-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1</p><p>　　Columns 34 through 44 </p><p>　　-1 -1 -1 -1 -1 -1 -1

33、 -1 -1 -1 -1</p><p>　　-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1</p><p>　　Columns 45 through 50 </p><p>　　-1 -1 -1 -1 -1 -1</p>

34、<p>　　-1 -1 -1 -1 -1 -1</p><p>　　從運(yùn)行結(jié)果來看通過13次可以安全渡河，但是這個(gè)解不是最優(yōu)解（即渡河次數(shù)最少）.從（5,5）—（0,0）我們可看到中間每一次的運(yùn)行步驟都符合我們的可取狀態(tài)集合={（0,1）（0,2）（0,3）（0,4）（0,5）（0,0）（5,5）（5,4）（5,3）（5,2）（5,1）（5,0）（1,1）（2,2）（3,

35、3）（4,4）}，我們也可驗(yàn)證每一步渡船上的人數(shù)也符合允許決策集合={（0,1）（0,2）（0,3）（1,0）（2,0）（3,0）（1,1）（2,1）}，因此程序可行.</p><p><b>　　6.32 圖解法</b></p><p>　　當(dāng)所討論問題變量不很多時(shí)，我們也常常利用作圖的方法來解決狀態(tài)轉(zhuǎn)移問題．對于“夫妻過河”問題求解，也就是要確定一系列的允許運(yùn)算(

36、k=1，2，…,m)，使得</p><p>　　我們可以在x－y平面上標(biāo)出允許狀態(tài)集S中的點(diǎn)， </p><p>　　而將允許運(yùn)算看作是沿方格移動(dòng)1格或2格，為了區(qū)別小船的往返，我們用實(shí)線表示小船由此岸至彼岸，用虛線表示小船由彼岸至此岸．于是我們給出一個(gè)“夫妻過河”問題的最優(yōu)解法.</p><p>　　圖解過程如下圖所示：</p><p>　

37、　7 六對夫妻過河模型</p><p><b>　　7.1模型構(gòu)成</b></p><p>　　記第次過河前此岸丈夫的人數(shù)為，妻子的人數(shù)為，=1,2，3……</p><p>　　由已知條件知可取狀態(tài)為（0,1）（0,2）（0,3）（0,4）（0,5）（0,6）（0,0）（6,6）（5,5）（5,4）（5,3）（5,2）（5,1）（5,0）（1,

38、1）（2,2）（3,3）（4,4）（5,5）共19種，用表示可取狀態(tài)集合，成為允許狀態(tài)集合，不難驗(yàn)證，對此岸和彼岸都是可行的.</p><p>　　記第次過渡船上的丈夫的人數(shù)為，妻子的人數(shù)為，由已知條件知可取狀態(tài)為（0,1）（0,2）（0,3）（1,0）（2,0）（3,0）（1,1）（2,1），其中（1，1）表示1對夫妻，共五種，用表示可取狀態(tài)集合，成為允許決策集合.</p><p>　　

39、模型建立：我們發(fā)現(xiàn)當(dāng)為奇數(shù)時(shí)船從此岸駛向彼岸，當(dāng)為偶數(shù)時(shí)船從此岸駛向彼岸，記表示狀態(tài)，=（）,記表示決策，=（）。所以狀態(tài)隨的變化規(guī)律為： 稱為狀態(tài)轉(zhuǎn)移律</p><p>　　求決策（=1,2，3……n）使?fàn)顟B(tài)按照狀態(tài)轉(zhuǎn)移律，由初始狀態(tài)=（1,1）有限步n到達(dá)狀態(tài)=（0，0）</p><p><b>　　7.2模型求解</b></p><

40、p>　　同樣的我們仿照“五對夫妻過河”在x－y平面上標(biāo)出允許狀態(tài)集S中的點(diǎn)， 而將允許運(yùn)算看作是沿方格移動(dòng)1格或2格，為了區(qū)別小船的往返，我們用實(shí)線表示小船由此岸至彼岸，用虛線表示小船由彼岸至此岸．</p><p>　　在解題過程中我們發(fā)現(xiàn)若要讓六對夫妻過河，路徑須經(jīng)由（6，3）到</p><p>　?。?，4）狀態(tài)，由條件所致，無法通過這條路徑.</p><p&

41、gt;　　那么我們改變條件為船最多能載4人，圖解過程如下圖</p><p>　　所以由此我們得到6對夫妻，當(dāng)船至少能載4人時(shí)才可以安全渡河</p><p>　　8 對夫妻過河情況</p><p><b>　　8.1求解</b></p><p>　　因?qū)Ψ蚱抟^河，船最多能載人，我們可以利用一個(gè)簡單的圖解法</p&

42、gt;<p>　　在解決前面的問題中，發(fā)現(xiàn)當(dāng)可行時(shí)每一次圖解法都要經(jīng)過下圖步驟 </p><p>　　另外我們總結(jié)了幾組數(shù)據(jù)：</p><p>　　由此可推斷如果要使夫妻能安全渡河,和的關(guān)系應(yīng)為</p><p><b>　　8.2驗(yàn)證</b></p><p>　　利用已有程序驗(yàn)證（驗(yàn)證程序見附錄）得到以下結(jié)

43、果</p><p>　　>> fuqiman</p><p><b>　　輸入丈夫數(shù)目：8</b></p><p><b>　　輸入妻子數(shù)目：8</b></p><p>　　輸入船的最大容量：4</p><p><b>　　ans =</b>

44、</p><p><b>　　沒有找到可行路徑！</b></p><p>　　>> fuqiman</p><p><b>　　輸入丈夫數(shù)目：8</b></p><p><b>　　輸入妻子數(shù)目：8</b></p><p>　　輸入船的最大容

45、量：5</p><p><b>　　ans =</b></p><p>　　0 0 </p><p><b>　　0 5</b></p><p><b>　　0 4 </b></p><p>　　4 4 <

46、/p><p>　　3 3 </p><p>　　8 3 </p><p>　　8 2 </p><p>　　8 4 </p><p>　　8 3 </p><p>　　8 8 </p><p>

47、;　　>> fuqiman</p><p><b>　　輸入丈夫數(shù)目：9</b></p><p><b>　　輸入妻子數(shù)目：9</b></p><p>　　輸入船的最大容量：5</p><p><b>　　ans =</b></p><p>

48、<b>　　0 0</b></p><p><b>　　0 2</b></p><p><b>　　0 1</b></p><p><b>　　0 5</b></p><p><b>　　5 5 </

49、b></p><p><b>　　4 4 </b></p><p><b>　　9 4 </b></p><p><b>　　9 3 </b></p><p>　　9 5 </p><p>　　9

50、4 </p><p>　　9 9 </p><p>　　>> fuqiman</p><p><b>　　輸入丈夫數(shù)目：10</b></p><p><b>　　輸入妻子數(shù)目：10</b></p><p>　　輸入船的最大容量：5</p

51、><p><b>　　ans =</b></p><p><b>　　沒有找到可行路徑</b></p><p>　?。ù颂幬覀儾辉倥e過多的例子）</p><p><b>　　9 總結(jié)與展望</b></p><p><b>　　9.1總結(jié)</b

52、></p><p>　　本文對夫妻過河問題進(jìn)一步探討，由五對、六對延伸至對夫妻.其中五對、六對夫妻過河利用matlab編程和圖解法解決，解決對夫妻要過河，船最多能載人，和有怎樣的關(guān)系時(shí)，利用類比推斷的方法推斷出.再利用已有程序檢驗(yàn).鑒于本人知識(shí)水平和計(jì)算機(jī)編程水平有限，還有很多不足的地方，有待于日后進(jìn)一步學(xué)習(xí)和研究．</p><p>　　9.2后續(xù)研究工作展望</p>

53、<p>　　本文對夫妻過河問題進(jìn)一步探討，由五對、六對延伸至對夫妻.在五對夫妻渡河方案中由于本人計(jì)算機(jī)編程水平有限得到的結(jié)果不是最優(yōu)解（即過河所用次數(shù)最少），在對夫妻要過河，船最多能載人，和有怎樣的關(guān)系時(shí)，盡管推論得到驗(yàn)證但是說服力不足，所以后續(xù)的研究工作在如下幾個(gè)方面展開：</p><p>　　利用matlab編程得到五對夫妻過河最優(yōu)情況</p><p>　　仿照文獻(xiàn)中已有的方

54、法求解夫妻過河問題</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 付艷玲，劉高峰，張偉.商人渡河問題解的存在性及算法實(shí)現(xiàn)[J].工程數(shù)學(xué)學(xué)報(bào)，2013,30:561</p><p>　　[2] 邵建峰，許丙勝.商人渡河問題的算法實(shí)現(xiàn)[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012,42:137</p><p&g

55、t;　　[3] 溫鴻航, 溫鴻翔, 任曉莉. 渡河問題的圖解分析[J].電子科技，2012,25:33</p><p>　　[4] 溫鴻航，任曉莉，溫鴻翔. 渡河問題的矩陣表示與迭代算法[J].電子科技,2012,25:101</p><p>　　[5] 達(dá)瓦, 加央. 種種渡河同題及其算法[J].科教文匯,2008,269</p><p>　　[6] 俞濤.“船運(yùn)

56、狼、羊、菜”問題的新解法[J]. 河北師范大學(xué)學(xué)報(bào)( 自然科學(xué)版),1996,20:27</p><p>　　[7] 善強(qiáng), 雷鳴. 數(shù)學(xué)模型( 第二版)[M].重慶大學(xué)出版社,1998.24</p><p>　　[8] 姜啟源，謝金星，葉俊.數(shù)學(xué)模型[M].第三版.北京：高等教育出版社，2003,7</p><p>　　[9] 李天瑞.安全渡河問題的計(jì)算機(jī)求解和模

57、擬[J].工科數(shù)學(xué)，1999，15:119</p><p>　　[10]武建林.商人渡河游戲的解題算法[J].電腦編程技巧與維護(hù)，2009,78</p><p>　　[11]張念發(fā)，張憲新，劉長征.基于狀態(tài)空間搜索法的商人過河問題解決方案[J].電腦編程技巧與維護(hù)，2010，36</p><p>　　[12]劉衛(wèi)國.MATLAB程序設(shè)計(jì)教程[M].第二版.北京：中國

58、水利水電出版社，2010,2</p><p>　　[13]趙靜,但琦.數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)[M].第三版.北京:高等教育出版社,2003,19</p><p>　　[14]張北辰，張建明.狀態(tài)轉(zhuǎn)移問題的計(jì)算機(jī)模擬[J].益陽師專學(xué)報(bào)，1998，13:67</p><p>　　[15]俞哲明，樊艷芬.利用數(shù)組解決農(nóng)夫過河問題[J].福建電腦，2013,（5）：151&l

59、t;/p><p>　　[16]陳義華.狀態(tài)轉(zhuǎn)移問題的圖論法建模[J]. 甘肅工業(yè)大學(xué)學(xué)報(bào),1997,23:92</p><p><b>　　附 錄</b></p><p><b>　　五對夫妻過河程序：</b></p><p>　　function kexing = f_kexing(a)</p&

60、gt;<p>　　% 判斷一個(gè)狀態(tài)a是否可行狀態(tài)</p><p>　　% 可行狀態(tài)為（0,i),（i,i),(5,i);0<=i<=5</p><p>　　if (a(1) == a(2) && a(1) >= 0 && a(1) <= 5)%可行狀態(tài)為（i,i),</p><p>　　kexin

61、g = 1;</p><p><b>　　else</b></p><p>　　if (a(1) == 0 ) && a(2) >= 0 && a(2) <= 5%可行狀態(tài)為（0,i)</p><p>　　kexing = 1;</p><p><b>　　else&

62、lt;/b></p><p>　　if((a(1) == 5) && a(2) >= 0 && a(2) <= 5)%可行狀態(tài)為（5,i)</p><p>　　kexing = 1;</p><p><b>　　else</b></p><p>　　kexing = 0;

63、</p><p><b>　　end</b></p><p><b>　　end</b></p><p><b>　　end</b></p><p>　　function jie = guohe()</p><p>　　kaishi = [5,5];%開

64、始狀態(tài)</p><p>　　jieshu = [0,0];%結(jié)束狀態(tài)</p><p>　　jie = -ones(2,50) ;</p><p>　　jie(:,1) = kaishi;</p><p>　　jie(:,2) = [5,2];%第一次移動(dòng) 三個(gè)人過去</p><p>　　%過去時(shí)人盡量多，去多<

65、/p><p>　　qu = [0 3 2 1 2 0 0 1;</p><p>　　3 0 1 1 0 2 1 0];</p><p><b>　　%回來時(shí)人盡量少</b></p><p>　　hui = [0 1 0 2 1 0 3 2;</p><p>　　1 0 2 0 1 3 0 1];<

66、;/p><p>　　yd_cishu = 2;%移動(dòng)次數(shù)</p><p>　　index = zeros(1,50);%指示第yd_cishu次移動(dòng)是采用的是那種方式</p><p>　　index(1) = 1;</p><p>　　index(2) = 1;</p><p>　　%注意矩陣是否相等的判斷</p&g

67、t;<p>　　while(jie(1,yd_cishu) ~= jieshu(1) || jie(2,yd_cishu) ~= jieshu(2) )</p><p>　　if( mod(yd_cishu,2) ~= 0 )%奇數(shù)次移動(dòng)</p><p>　　while(index(yd_cishu)<=9)</p><p>　　switch(i

68、ndex(yd_cishu))</p><p><b>　　case {1} </b></p><p>　　jixu = jie(:,yd_cishu) - qu(:,1); </p><p><b>　　case {2} </b></p><p>　　jixu= jie(

69、:,yd_cishu) - qu(:,2);</p><p><b>　　case {3} </b></p><p>　　jixu = jie(:,yd_cishu) - qu(:,3);</p><p><b>　　case {4} </b></p><p>　　jixu = jie(:,yd

70、_cishu) - qu(:,4); </p><p><b>　　case {5} </b></p><p>　　jixu = jie(:,yd_cishu) - qu(:,5); </p><p><b>　　case {6} </b></p><p>　　jixu = jie(:,yd_c

71、ishu) - qu(:,6);</p><p><b>　　case {7} </b></p><p>　　jixu = jie(:,yd_cishu) - qu(:,7);</p><p><b>　　case {8} </b></p><p>　　jixu = jie(:,yd_cishu

72、) - qu(:,8);</p><p><b>　　end</b></p><p>　　if(f_kexing(jixu))%當(dāng)移動(dòng)狀態(tài)可行，則保存移動(dòng)情況</p><p>　　yd_cishu = yd_cishu + 1;%繼續(xù)移動(dòng)</p><p>　　jie(:,yd_cishu) = jixu;</p&

73、gt;<p>　　index(yd_cishu) = index(yd_cishu) + 1;</p><p>　　index(yd_cishu) = 1;%下一次移動(dòng)選擇從新開始</p><p>　　break; </p><p><b>　　else</b></p><p>　

74、　index(yd_cishu) = index(yd_cishu) + 1;</p><p><b>　　end</b></p><p><b>　　end</b></p><p>　　if(index(yd_cishu)>9)</p><p>　　yd_cishu = yd_cishu -

75、 1;%回退</p><p>　　end </p><p>　　else%偶數(shù)次移動(dòng)</p><p>　　while(index(yd_cishu)<=9)</p><p>　　switch(index(yd_cishu))</p><p><b>　　case {1} &

76、lt;/b></p><p>　　jixu = jie(:,yd_cishu) + hui(:,1);</p><p>　　case {2}% </p><p>　　jixu = jie(:,yd_cishu) + hui(:,2); </p><p>　　case {3}% </p><

77、p>　　jixu = jie(:,yd_cishu) + hui(:,3);</p><p>　　case {4}% </p><p>　　jixu = jie(:,yd_cishu) + hui(:,4);</p><p><b>　　case {5} </b></p><p>　　jixu = jie(:,

78、yd_cishu) + hui(:,5);</p><p><b>　　case {6} </b></p><p>　　jixu = jie(:,yd_cishu) + hui(:,6);</p><p><b>　　case {7} </b></p><p>　　jixu = jie(:,yd

79、_cishu) + hui(:,7);</p><p><b>　　case {8} </b></p><p>　　jixu = jie(:,yd_cishu) + hui(:,8)</p><p><b>　　end</b></p><p>　　%當(dāng)移動(dòng)狀態(tài)可行，則保存移動(dòng)情況 且 回來船上的

80、人員狀態(tài)不能和上一次的情況完全一樣，否則就重復(fù)操作無意義了。</p><p>　　if( f_kexing(jixu) && ( hui(1,index(yd_cishu)) ~= qu(1,index(yd_cishu - 1)) || hui(2,index(yd_cishu)) ~= qu(2,index(yd_cishu - 1))))</p><p>　　yd_c

81、ishu = yd_cishu + 1;%繼續(xù)移動(dòng)</p><p>　　jie(:,yd_cishu) = jixu;</p><p>　　index(yd_cishu) = index(yd_cishu) + 1; </p><p>　　index(yd_cishu) = 1;%下一次移動(dòng)選擇從新開始</p><p&g

82、t;　　break; </p><p><b>　　else</b></p><p>　　index(yd_cishu) = index(yd_cishu) + 1;</p><p><b>　　end</b></p><p><b>　　end</b>

83、;</p><p>　　if(index(yd_cishu)>9)</p><p>　　yd_cishu = yd_cishu - 1;%回退</p><p>　　end </p><p><b>　　end</b></p><p><b>　　end</b>

84、;</p><p><b>　　驗(yàn)證程序：</b></p><p>　　function s=fuqiman</p><p>　　n=input('輸入丈夫數(shù)目：');</p><p>　　nn=input('輸入妻子數(shù)目：');</p><p>　　nnn=inp

85、ut('輸入船的最大容量：');</p><p><b>　　if nn>n</b></p><p>　　n=input('輸入丈夫數(shù)目：');</p><p>　　nn=input('輸入妻子數(shù)目：');</p><p>　　nnn=input('輸入船的最

86、大容量：');</p><p><b>　　end</b></p><p><b>　　k=1;</b></p><p>　　for i=0:nnn </p><p>　　for j=0:nnn</p><p>　　if (i+j<=nnn) &(i+j

87、>0)</p><p>　　d(k,1:3)=[i,j,1]; </p><p>　　d(k+1,1:3)=[-i,-j,-1]; </p><p><b>　　k=k+2;</b></p><p><b>　　end</b></p><p><b&

88、gt;　　end</b></p><p><b>　　end</b></p><p><b>　　k=1;</b></p><p>　　for i=n:-1:0 </p><p>　　for j=nn:-1:0</p><p>　　if ((

89、i>=j) & ((n-i)>=(nn-j))) | ((i==0)|(i==n))</p><p>　　A(k,1:3)=[i,j,1]; </p><p><b>　　k=k+1;</b></p><p><b>　　end</b></p><p><b&

90、gt;　　end</b></p><p><b>　　end</b></p><p>　　sq(1,1)=n;sq(1,2)=nn;sq(1,3)=0;sq(1,4)=1;sq(1,5)=0; sq(1,6)=1; </p><p>　　front=1;rear=1; </p><p>　　while(f

91、ront<=rear)</p><p>　　x=sq(front,1);</p><p>　　y=sq(front,2);</p><p><b>　　flag=0;</b></p><p>　　if (sq(front,4)==1)</p><p>　　for v=2:2:size(d,1

92、)</p><p>　　i=x+d(v,1);</p><p>　　j=y+d(v,2);</p><p>　　if (is_save(A,i,j)==1) & is_same(sq,i,j,-1)~=0</p><p>　　if sq(is_same(sq,i,j,-1),5)==(sq(front,5)+1)</p>

93、<p>　　sq(is_same(sq,i,j,-1),6)=sq(is_same(sq,i,j,-1),6)+1;</p><p><b>　　end</b></p><p><b>　　end</b></p><p>　　if (is_save(A,i,j)==1) & is_same(sq,i,j

94、,-1)==0</p><p>　　rear=rear+1;</p><p>　　sq(rear,1)=i;</p><p>　　sq(rear,2)=j;</p><p>　　sq(rear,3)=front;</p><p>　　sq(rear,4)=-1;</p><p>　　sq(rea

95、r,5)=sq(front,5)+1; </p><p>　　sq(rear,6)=1;</p><p><b>　　end</b></p><p>　　if (i==0 & j==0)</p><p>　　flag=1; </p><p><b>　　end

96、</b></p><p>　　end </p><p><b>　　end</b></p><p>　　if (flag==1)</p><p><b>　　% break;</b></p><p><b>　　end</b>&l

97、t;/p><p><b>　　flag=0;</b></p><p>　　if (sq(front,4)==-1)</p><p>　　for v=1:2:size(d,1)</p><p>　　i=x+d(v,1);</p><p>　　j=y+d(v,2);</p><p>

98、;　　if (is_save(A,i,j)==1) & is_same(sq,i,j,1)~=0</p><p>　　if sq(is_same(sq,i,j,1),5)==(sq(front,5)+1)</p><p>　　sq(is_same(sq,i,j,1),6)=sq(is_same(sq,i,j,1),6)+1;</p><p><b>

99、;　　end</b></p><p><b>　　end</b></p><p>　　if (is_save(A,i,j)==1) & is_same(sq,i,j,1)==0</p><p>　　rear=rear+1;</p><p>　　sq(rear,1)=i;</p><

100、p>　　sq(rear,2)=j;</p><p>　　sq(rear,3)=front;</p><p>　　sq(rear,4)=1;</p><p>　　sq(rear,5)=sq(front,5)+1;</p><p>　　sq(rear,6)=1;</p><p><b>　　end</

101、b></p><p>　　if (i==0 & j==0)</p><p><b>　　flag=1;</b></p><p><b>　　end</b></p><p><b>　　end</b></p><p><b>　　e

102、nd</b></p><p>　　if (flag==1)</p><p><b>　　% break;</b></p><p><b>　　end</b></p><p>　　front=front+1;</p><p><b>　　end</

103、b></p><p>　　if sq(rear,1)~=0 & sq(rear,2)~=0</p><p>　　s='沒有找到可行路徑！';</p><p><b>　　else</b></p><p>　　i=sq(rear,3);</p><p><b>

104、;　　k=2;</b></p><p><b>　　r=1;</b></p><p>　　for w=1:rear</p><p><b>　　% sq(w,6)</b></p><p>　　%r=r*sq(w,6);</p><p><b>　　end

105、</b></p><p>　　s(1,1)=0;s(1,2)=0;s(1,3)=0;s(1,4)=0;</p><p>　　while(i>0)</p><p>　　s(k,1)=sq(i,1);</p><p>　　s(k,2)=sq(i,2);</p><p>　　s(k,3)=sq(i,6);&

106、lt;/p><p>　　s(k,4)=sq(i,5);</p><p>　　r=r*sq(i,6);</p><p>　　i=sq(i,3);</p><p><b>　　k=k+1;</b></p><p><b>　　end</b></p><p>&

107、lt;b>　　r</b></p><p><b>　　end</b></p><p>　　is_same.m文件：</p><p>　　function a=is_same(sq,x,y,z)</p><p>　　for i=1:size(sq,1)</p><p>　　if (

108、x==sq(i,1) & y==sq(i,2) & z==sq(i,4))</p><p><b>　　break;</b></p><p><b>　　end</b></p><p><b>　　end</b></p><p>　　if i<size(s

109、q,1)</p><p><b>　　a=2;</b></p><p><b>　　else</b></p><p><b>　　a=1;</b></p><p><b>　　end</b></p><p>　　is_save.m文

110、件：</p><p>　　function a=is_save(A,x,y)</p><p>　　for i=1:size(A,1)</p><p>　　if (x==A(i,1) && y==A(i,2))</p><p><b>　　break;</b></p><p><

111、;b>　　end</b></p><p><b>　　end</b></p><p>　　if i<size(A,1)</p><p><b>　　a=1;</b></p><p><b>　　else</b></p><p>&