(完整版)matlab求解夫妻過(guò)河問(wèn)題畢業(yè)設(shè)計(jì).doc

1、曲靖師范學(xué)院本科生畢業(yè)論文論文題目 : matlab 求解夫妻過(guò)河問(wèn)題學(xué)院、年級(jí)：數(shù)學(xué)與信息科學(xué)學(xué)院2010 級(jí)學(xué)科、專業(yè)：數(shù)學(xué)數(shù)學(xué)與應(yīng)用數(shù)學(xué)指導(dǎo)教師：郭昀完成日期：2013年 12月 27日曲靖師范學(xué)院教務(wù)處摘要渡河問(wèn)題 . 始于公元8 世紀(jì)，至今它仍是一個(gè)邏輯難題，許多數(shù)學(xué)建模教材上已經(jīng)提到 . 這個(gè)問(wèn)題指的是：有不同的對(duì)象或生物，他們其中一些相互不共存，逐步地讓一小群體從河的一岸到另一岸，經(jīng)過(guò)有限步后，該群體全部從一岸達(dá)到另一岸，并且要求沒(méi)有任何損失在渡河問(wèn)題的夫妻過(guò)河問(wèn)題中我們發(fā)現(xiàn)狀態(tài)轉(zhuǎn)移問(wèn)題有時(shí)不一定有解，有時(shí)的解又不一定有規(guī)律，本文對(duì)于夫妻過(guò)河問(wèn)題利用圖解法和matlab 編寫(xiě)程序

2、求解 5 對(duì)、6 對(duì)夫妻過(guò)河是否有解，并推廣到對(duì)夫妻與船的運(yùn)載能力對(duì)于能否安全渡河時(shí)它們之間的關(guān)系。關(guān)鍵詞： 多步?jīng)Q策matlab數(shù)學(xué)模型渡河問(wèn)題Problem of couples across the riverAbstract: the problem of crossing the river. In the 8th century, it still is a logical problem, many mathematical modeling teaching material mentioned. The question is: crossing the river prob

3、lem of couples across the river, we found that state transition problem sometimes does not necessarily , sometimes the solution is not necessarily regular, in this paper, using the graphical method for the problem of couples across the river and the matlab program to solve the 5, 6 for couple across

4、 a river if there is a solution,And derived to n couple with the ability to run m to safe crossingthe river when the relationship between them.Keywords: MultistepdecisionMatlabMathematicalmodelProblem of crossing the river目 錄1 引言 .2 文獻(xiàn)綜述 .2.1國(guó)內(nèi)外研究現(xiàn)狀 . .2.2國(guó)內(nèi)外研究現(xiàn)狀評(píng)價(jià) . .2.3問(wèn)題提出 .3 模型假設(shè) .4 符號(hào)說(shuō)明 .5 重述 3

5、、4 對(duì)夫妻過(guò)河問(wèn)題的解 .5.1 3對(duì)夫妻過(guò)河的解 .5.2 4對(duì)夫妻過(guò)河的解 .6 五對(duì)夫妻過(guò)河模型 . .6.1 模型構(gòu)成 .6.2模型建立 .6.3模型求解 .6.31 Matlab編程求解 .6.32圖解法 .7 六對(duì)夫妻過(guò)河模型 . .7.1 模型構(gòu)成 .7.2模型求解 .8 n對(duì)夫妻過(guò)河情況 .8.1求解 .8.2驗(yàn)證 .9總結(jié)與展望 .9.1總結(jié) .9.2后續(xù)研究工作展望 .參考文獻(xiàn) .附 錄 .1 引言這是一個(gè)古老的阿拉伯?dāng)?shù)學(xué)問(wèn)題。有 3 對(duì)夫妻要過(guò)河，船最多可載 2 人，約束條件是根據(jù)阿拉伯法律，任一女子不得在其丈夫不在場(chǎng)的情況下與其他男子在一起，問(wèn)此時(shí)這 3 對(duì)夫妻能否過(guò)

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

7、多目標(biāo)決策方法是從 20世紀(jì) 70年代中期發(fā)展起來(lái)的一種決策分析方法 . 決策分析是在系統(tǒng)規(guī)劃、設(shè)計(jì)和制造等階段為解決當(dāng)前或未來(lái)可能發(fā)生的問(wèn)題，在若干可選的方案中選擇和決定最佳方案的一種分析過(guò)程 . 在社會(huì)經(jīng)濟(jì)系統(tǒng)的研究控制過(guò)程中我們所面臨的系統(tǒng)決策問(wèn)題常常是多目標(biāo)的，例如我們?cè)谘芯可a(chǎn)過(guò)程的組織決策時(shí)，既要考慮生產(chǎn)系統(tǒng)的產(chǎn)量最大，又要使產(chǎn)品質(zhì)量高，生產(chǎn)成本低等。這些目標(biāo)之間相互作用和矛盾，使決策過(guò)程相當(dāng)復(fù)雜使決策者常常很難輕易作出決策. 這類具有多個(gè)目標(biāo)的決策總是就是多目標(biāo)決策 . 多目標(biāo)決策方法現(xiàn)已廣泛地應(yīng)用于工藝過(guò)程、工藝設(shè)計(jì)、配方配比、水資源利用、能源、環(huán)境、人口、教育、經(jīng)濟(jì)管理等領(lǐng)域

8、 .2 文獻(xiàn)綜述2.1 國(guó)內(nèi)外研究現(xiàn)狀渡河問(wèn)題有不同的版本，從目前參閱的文獻(xiàn)資料中了解的信息來(lái)看文獻(xiàn) 1 、 5 、 6 的商人和隨從渡河問(wèn)題利用通過(guò)遍歷狀態(tài)空間樹(shù)來(lái)搜索可行的渡河方案、建立多步?jīng)Q策模型、計(jì)算機(jī)編程等方法解決, 文獻(xiàn) 3 、4 的傳教士和食人族難題仿照整數(shù) ( 二元 ) 規(guī)劃的圖示方法、用矩陣表示與迭代算法等方法解決，文獻(xiàn) 5 軍官渡河問(wèn)題和人與機(jī)器渡河問(wèn)題利用 Dijkstra算法 , 文獻(xiàn) 13 的人、貓、雞、米過(guò)河問(wèn)題利用計(jì)算機(jī)C 語(yǔ)言編程求解，文獻(xiàn) 6 、15 的人、狼、羊、菜過(guò)河問(wèn)題利用多為向量的方法解決 . 但是解決方法是類似的 , 都是要找到允許狀態(tài)和允許決策 .

9、2.2 國(guó)內(nèi)外研究現(xiàn)狀評(píng)價(jià)綜上所述，渡河問(wèn)題至今仍是一個(gè)邏輯難題. 國(guó)內(nèi)外對(duì)于過(guò)河問(wèn)題的研究很多，但是不是很全面，由于渡河問(wèn)題的種類很多，盡管研究方法大體相同，但是他的解卻是有很多種，或者有的問(wèn)題根本無(wú)解，就夫妻過(guò)河問(wèn)題而言當(dāng)4 對(duì)夫妻過(guò)河，船只能載2 人時(shí)問(wèn)題無(wú)解 . 本文在夫妻過(guò)河問(wèn)題的基礎(chǔ)上從3 對(duì)、 4 對(duì)夫妻研究至5 對(duì)、 6 對(duì)，并推至 n 對(duì)夫妻過(guò)河情況，利用圖解法和matlab 編程解決 .2.3問(wèn)題提出問(wèn)題 1：若船最多能載3 人， 5 對(duì)夫妻能否過(guò)河？六對(duì)夫妻呢？如果不可以那么船最多能載幾人才可以？問(wèn)題 2： n 對(duì)夫妻要過(guò)河，船最多能載 m人， n 和 m有怎樣的關(guān)系？任

10、務(wù)：用 matlab 編寫(xiě)程序求問(wèn)題 1 的解，并用已有程序驗(yàn)證問(wèn)題 2.3 模型假設(shè)1. 不考慮過(guò)河環(huán)境因素的影響情況；2. 夫妻過(guò)河只能依靠小船；3. 每個(gè)男人和女人都會(huì)劃船；4 符號(hào)說(shuō)明表示渡河的夫妻對(duì)數(shù)表示第 k 次渡河前此岸丈夫的人數(shù)表示第 k 次渡河前此岸妻子的人數(shù)表示第次過(guò)渡船上丈夫的人數(shù)表示第次過(guò)渡船上妻子的人數(shù)表示第幾次渡河表示渡河的次數(shù)表示允許狀態(tài)集合表示允許決策集合表示狀態(tài)表示決策5 重述 3、4 對(duì)夫妻過(guò)河問(wèn)題的解有 3 對(duì)夫妻要過(guò)河，船最多可載2 人，約束條件是根據(jù)阿拉伯法律，任一女子不得在其丈夫不在場(chǎng)的情況下與其他男子在一起，問(wèn)此時(shí)這3 對(duì)夫妻能否過(guò)河？如果是4 對(duì)

11、夫妻過(guò)河，其他條件不變的情況下，夫妻能否過(guò)河？記次過(guò)河前此岸丈夫的人數(shù)為，妻子的人數(shù)為. 記表示狀態(tài)，= （） ,記表示決策，= （）。5.1 3對(duì)夫妻過(guò)河的解5.2 4對(duì)夫妻過(guò)河的解可看出問(wèn)題無(wú)法再解下去6 五對(duì)夫妻過(guò)河模型6.1 模型構(gòu)成記第次過(guò)河前此岸丈夫的人數(shù)為，妻子的人數(shù)為，=1,2 ，3,由已知條件知可取狀態(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,3 ）（ 4,4 ）共 16 種，用表示可取狀態(tài)集合，成為允許狀態(tài)集合，不難驗(yàn)證，對(duì)此岸

12、和彼岸都是可行的 .記第次過(guò)渡船上的丈夫的人數(shù)為， 妻子的人數(shù)為， 由已知條件知可取狀態(tài)為（ 0,1 ）（0,2 ）（0,3 ）（1,0 ）（2,0 ）（3,0 ）（1,1 ）（ 2,1 ），其中（ 1，1）表示 1 對(duì)夫妻，共五種，用表示可取狀態(tài)集合，成為允許決策集合.6.2 模型建立我們發(fā)現(xiàn)當(dāng)為奇數(shù)時(shí)船從此岸駛向彼岸，當(dāng)為偶數(shù)時(shí)船從此岸駛向彼岸，記表示狀態(tài)，= （） , 記表示決策，= （）。所以狀態(tài)隨的變化規(guī)律為：稱為狀態(tài)轉(zhuǎn)移律求決策（ =1,2 ，3,n）使?fàn)顟B(tài)按照狀態(tài)轉(zhuǎn)移律，由初始狀態(tài)=（ 1,1 ）有限步 n 到達(dá)狀態(tài) =（0，0）6.3 模型求解6.31 Matlab編程求解對(duì)于

13、這個(gè)問(wèn)題通常用“窮舉求解”的方法，即從初始狀態(tài)（ 5， 5 ）開(kāi)始，從允許決策集合D 中選擇一個(gè)決策，產(chǎn)生一個(gè)新?tīng)顟B(tài) . 若新?tīng)顟B(tài)可行，則保存該狀態(tài)，并從這個(gè)狀態(tài)開(kāi)始繼續(xù)進(jìn)行決策尋找下一可行狀態(tài)； 否則，從允許決策集合D 中重新選擇一個(gè)新決策以產(chǎn)生下一狀態(tài).如果某個(gè)狀態(tài)的所有可選決策產(chǎn)生的下一狀態(tài)均不可行，則返回到上一個(gè)可行狀態(tài)， 從該可行狀態(tài)開(kāi)始尋找除了狀態(tài)的其它狀態(tài)， 直到找到一個(gè)可行的下一狀態(tài) . 這個(gè)決策過(guò)程反復(fù)進(jìn)行， 直到到達(dá)最終狀態(tài)（ 0， 0 ），即可以安全渡河 . 其中，判斷狀態(tài)是否可行包括兩個(gè)方面：（ 1） 該狀態(tài)是否在允許狀態(tài)集合 S 中.（ 2） 在由決策所確定產(chǎn)生的一系

14、列狀態(tài)中，船由此岸駛向彼岸前的所有狀態(tài)不允許重復(fù)， 船由彼岸駛向此岸前的所有狀態(tài)亦不允許重復(fù) .可以應(yīng)用人工智能原理中的狀態(tài)空間搜索法解決 . 首先定義一個(gè)安全渡河問(wèn)題的狀態(tài)空間，規(guī)定出該空間的初始狀態(tài)和目標(biāo)狀態(tài)，建立相應(yīng)的渡河規(guī)則和控制策略，而后推理搜索，直至找出由初始狀態(tài)到目標(biāo)狀態(tài)的某條路徑或一組路徑，即安全渡河的操作序列 . 用 matlab 編寫(xiě)一段程序求解，程序編寫(xiě)思路如下圖程序運(yùn)行結(jié)果（程序見(jiàn)附錄） ：ans =Columns 1 through 115555555230052301022334Columns 12 through 22000-1-1-1-1-1-1-1-1120-

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

16、 ）（ 0,5 ）（0,0 ）（5,5 ）（ 5,4 ）（5,3 ）（5,2 ）（ 5,1 ）（ 5,0 ）（ 1,1 ）（ 2,2 ）（ 3,3 ）（ 4,4 ） ，我們也可驗(yàn)證每一步渡船上的人數(shù)也符合允許決策集合= （ 0,1 ）（ 0,2 ）（0,3 ）（ 1,0 ）（2,0 ）（3,0 ）（1,1 ）（ 2,1 ） ，因此程序可行 . 6.32 圖解法當(dāng)所討論問(wèn)題變量不很多時(shí)，我們也常常利用作圖的方法來(lái)解決狀態(tài)轉(zhuǎn)移問(wèn)題對(duì)于“夫妻過(guò)河”問(wèn)題求解，也就是要確定一系列的允許運(yùn)算(k=1 ， 2，, ,m) ，使得(5,5)ddd(0,0)12m我們可以在 x y 平面上標(biāo)出允許狀態(tài)集S 中的

17、點(diǎn)，而將允許運(yùn)算看作是沿方格移動(dòng) 1 格或 2 格，為了區(qū)別小船的往返，我們用實(shí)線表示小船由此岸至彼岸，用虛線表示小船由彼岸至此岸于是我們給出一個(gè)“夫妻過(guò)河”問(wèn)題的最優(yōu)解法.圖解過(guò)程如下圖所示：7 六對(duì)夫妻過(guò)河模型7.1 模型構(gòu)成記第次過(guò)河前此岸丈夫的人數(shù)為，妻子的人數(shù)為，=1,2 ，3,由已知條件知可取狀態(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,1 ）（ 2,2 ）（3,3 ）（4,4 ）（ 5,5 ）共 19 種，用表示可取狀態(tài)集合，成為允許狀

18、態(tài)集合，不難驗(yàn)證，對(duì)此岸和彼岸都是可行的 .記第次過(guò)渡船上的丈夫的人數(shù)為，妻子的人數(shù)為，由已知條件知可取狀態(tài)為（ 0,1 ）（0,2 ）（ 0,3 ）（ 1,0 ）（ 2,0 ）（ 3,0 ）（ 1,1 ）（ 2,1 ），其中（ 1，1）表示 1 對(duì)夫妻，共五種，用表示可取狀態(tài)集合，成為允許決策集合.模型建立：我們發(fā)現(xiàn)當(dāng)為奇數(shù)時(shí)船從此岸駛向彼岸，當(dāng)為偶數(shù)時(shí)船從此岸駛向彼岸，記表示狀態(tài)，= （） , 記表示決策， = （）。所以狀態(tài)隨的變化規(guī)律為：稱為狀態(tài)轉(zhuǎn)移律求決策（ =1,2 ，3,n）使?fàn)顟B(tài)按照狀態(tài)轉(zhuǎn)移律，由初始狀態(tài)=（1,1 ）有限步 n 到達(dá)狀態(tài) =（0， 0）7.2 模型求解同樣的我

19、們仿照“五對(duì)夫妻過(guò)河”在xy平面上標(biāo)出允許狀態(tài)集S中的點(diǎn)，而將允許運(yùn)算看作是沿方格移動(dòng)1 格或2 格，為了區(qū)別小船的往返，我們用實(shí)線表示小船由此岸至彼岸，用虛線表示小船由彼岸至此岸在解題過(guò)程中我們發(fā)現(xiàn)若要讓六對(duì)夫妻過(guò)河，路徑須經(jīng)由（6，3）到（ 0，4）狀態(tài)，由條件所致，無(wú)法通過(guò)這條路徑.那么我們改變條件為船最多能載4 人，圖解過(guò)程如下圖所以由此我們得到6 對(duì)夫妻，當(dāng)船至少能載4 人時(shí)才可以安全渡河8 對(duì)夫妻過(guò)河情況8.1 求解因?qū)Ψ蚱抟^(guò)河，船最多能載人，我們可以利用一個(gè)簡(jiǎn)單的圖解法在解決前面的問(wèn)題中，發(fā)現(xiàn)當(dāng)可行時(shí)每一次圖解法都要經(jīng)過(guò)下圖步驟另外我們總結(jié)了幾組數(shù)據(jù)：安全渡河可行數(shù)據(jù)表序號(hào)夫妻

20、（對(duì)）船最大容量（人）132243353464574由此可推斷如果要使夫妻能安全渡河, 和的關(guān)系應(yīng)為8.2 驗(yàn)證利用已有程序驗(yàn)證（驗(yàn)證程序見(jiàn)附錄）得到以下結(jié)果 fuqiman輸入丈夫數(shù)目： 8輸入妻子數(shù)目： 8輸入船的最大容量： 4ans =沒(méi)有找到可行路徑！ fuqiman輸入丈夫數(shù)目： 8輸入妻子數(shù)目： 8輸入船的最大容量： 5ans =0005044433838284838 8 fuqiman輸入丈夫數(shù)目： 9輸入妻子數(shù)目： 9輸入船的最大容量： 5ans =000201055 54 49493959 49 9 fuqiman輸入丈夫數(shù)目： 10輸入妻子數(shù)目： 10輸入船的最大容量： 5

21、ans =沒(méi)有找到可行路徑（此處我們不再舉過(guò)多的例子）9 總結(jié)與展望9.1 總結(jié)本文對(duì)夫妻過(guò)河問(wèn)題進(jìn)一步探討，由五對(duì)、六對(duì)延伸至對(duì)夫妻 . 其中五對(duì)、六對(duì)夫妻過(guò)河利用matlab編程和圖解法解決，解決對(duì)夫妻要過(guò)河，船最多能載人，和有怎樣的關(guān)系時(shí)，利用類比推斷的方法推斷出. 再利用已有程序檢驗(yàn) . 鑒于本人知識(shí)水平和計(jì)算機(jī)編程水平有限，還有很多不足的地方，有待于日后進(jìn)一步學(xué)習(xí)和研究9.2 后續(xù)研究工作展望本文對(duì)夫妻過(guò)河問(wèn)題進(jìn)一步探討，由五對(duì)、六對(duì)延伸至對(duì)夫妻. 在五對(duì)夫妻渡河方案中由于本人計(jì)算機(jī)編程水平有限得到的結(jié)果不是最優(yōu)解（即過(guò)河所用次數(shù)最少） ，在對(duì)夫妻要過(guò)河，船最多能載人，和有怎樣的關(guān)系

22、時(shí)，盡管推論得到驗(yàn)證但是說(shuō)服力不足，所以后續(xù)的研究工作在如下幾個(gè)方面展開(kāi)：1. 利用 matlab 編程得到五對(duì)夫妻過(guò)河最優(yōu)情況2. 仿照文獻(xiàn)中已有的方法求解夫妻過(guò)河問(wèn)題參考文獻(xiàn)1付艷玲， 劉高峰， 張偉 . 商人渡河問(wèn)題解的存在性及算法實(shí)現(xiàn)J.工程數(shù)學(xué)學(xué)報(bào)，27 善強(qiáng) , 雷鳴 . 數(shù)學(xué)模型 ( 第二版 )M. 重慶大學(xué)出版社 ,1998.248 姜啟源，謝金星，葉俊 . 數(shù)學(xué)模型 M. 第三版 . 北京：高等教育出版社， 2003,79李天瑞 . 安全渡河問(wèn)題的計(jì)算機(jī)求解和模擬J. 工科數(shù)學(xué)， 1999， 15:11911張念發(fā)，張憲新，劉長(zhǎng)征 . 基于狀態(tài)空間搜索法的商人過(guò)河問(wèn)題解決方案J.電腦編程技巧與維護(hù)， 2010， 3612劉衛(wèi)國(guó) .MATLAB程序設(shè)計(jì)教程 M. 第二版 . 北京：中國(guó)水利水電出版社，2010,214 張北辰，張建明 . 狀態(tài)轉(zhuǎn)移問(wèn)題的計(jì)算機(jī)模擬 J. 益陽(yáng)師專學(xué)報(bào)， 1998 ，13:6715 俞哲明，樊艷芬. 利用數(shù)組解決農(nóng)夫過(guò)河問(wèn)題J.福建電腦， 2013, （ 5）： 151附 錄五對(duì)夫妻過(guò)河程序：function kexing = f_kexing(a)% 判斷一個(gè)狀態(tài)