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

本科生畢業(yè)論文論文題目:matlab求解夫妻過河問題摘要渡河問題.始于公元8世紀(jì)，至今它仍是一個(gè)邏輯難題，許多數(shù)學(xué)建模教材上已經(jīng)提到.這個(gè)問題指的是：有不同的對(duì)象或生物，他們其中一些相互不共存，逐步地讓一小群體從河的一岸到另一岸，經(jīng)過有限步后，該群體全部從一岸達(dá)到另一岸，并且要求沒有任何損失．在渡河問題的夫妻過河問題中我們發(fā)現(xiàn)狀態(tài)轉(zhuǎn)移問題有時(shí)不一定有解，有時(shí)的解又不一定有規(guī)律，本文對(duì)于夫妻過河問題利用圖解法和matlab編寫程序求解5對(duì)、6對(duì)夫妻過河是否有解，并推廣到對(duì)夫妻與船的運(yùn)載能力對(duì)于能否安全渡河時(shí)它們之間的關(guān)系。關(guān)鍵詞：多步?jīng)Q策matlab數(shù)學(xué)模型渡河問題Problem

of

couples

across

the

riverAbstract:theproblemofcrossingtheriver.Inthe8thcentury,itstillisalogicalproblem,manymathematicalmodelingteachingmaterialhasbeenmentioned.Thequestionis:havedifferentobjectsorcreatures,theylacksomemutualcoexistence,graduallytoasmallgroupfromonebanktoanotherbankoftheriver,afterfinitesteps,thegroupallfromonesidetotheothershore,andrequiresnolosses.Incrossingtheriverproblemofcouplesacrosstheriver,wefoundthatstatetransitionproblemsometimesdoesnotnecessarilyhaveasolution,sometimesthesolutionisnotnecessarilyregular,inthispaper,usingthegraphicalmethodfortheproblemofcouplesacrosstheriverandthematlabprogramtosolvethe5,6forcoupleacrossariverifthereisasolution,Andderivedtoncouplewiththeabilitytorunmtosafecrossingtheriverwhentherelationshipbetweenthem.Keywords:MultistepdecisionMatlabMathematicalmodelProblemofcrossingtheriver目錄1引言12文獻(xiàn)綜述12.1國(guó)外研究現(xiàn)狀12.2國(guó)外研究現(xiàn)狀評(píng)價(jià)22.3問題提出23模型假設(shè)24符號(hào)說明25重述3、4對(duì)夫妻過河問題的解35.13對(duì)夫妻過河的解35.24對(duì)夫妻過河的解36五對(duì)夫妻過河模型46.1模型構(gòu)成46.2模型建立46.3模型求解46.31Matlab編程求解46.32圖解法77六對(duì)夫妻過河模型87.1模型構(gòu)成87.2模型求解98n對(duì)夫妻過河情況108.1求解108.2驗(yàn)證119總結(jié)與展望129.1總結(jié)129.2后續(xù)研究工作展望13參考文獻(xiàn)14附錄151引言這是一個(gè)古老的阿拉伯?dāng)?shù)學(xué)問題。有3對(duì)夫妻要過河，船最多可載2人，約束條件是根據(jù)阿拉伯法律，任一女子不得在其丈夫不在場(chǎng)的情況下與其他男子在一起，問此時(shí)這3對(duì)夫妻能否過河？如果是4對(duì)夫妻過河，其他條件不變的情況下，夫妻能否過河？就這一問題我們發(fā)現(xiàn)狀態(tài)轉(zhuǎn)移問題有時(shí)不一定有解，有時(shí)的解又不一定有規(guī)律（當(dāng)4對(duì)夫妻過河，其他條件不變的情況下，夫妻能否過河？我們發(fā)現(xiàn)此問題是無解的），但是當(dāng)我們改變條件船最多可載3人時(shí)有解.就其數(shù)學(xué)建模思想來說,一般采用將該問題轉(zhuǎn)化為一個(gè)多步?jīng)Q策模型,模型求解的方法大多為圖解法然而一旦問題的條件(例如丈夫、妻子或者小船上每次渡河人數(shù)等)發(fā)生變化,圖解法求解猶如大海撈針!很難奏效.因此計(jì)算機(jī)編程求解模型的方法就顯得非常重要了.該題求解編程的難點(diǎn)在于允許狀態(tài)與決策這兩個(gè)方面的處理與實(shí)現(xiàn).此問題中利用的多目標(biāo)決策方法是從20世紀(jì)70年代中期發(fā)展起來的一種決策分析方法.決策分析是在系統(tǒng)規(guī)劃、設(shè)計(jì)和制造等階段為解決當(dāng)前或未來可能發(fā)生的問題，在若干可選的方案中選擇和決定最佳方案的一種分析過程.在社會(huì)經(jīng)濟(jì)系統(tǒng)的研究控制過程中我們所面臨的系統(tǒng)決策問題常常是多目標(biāo)的，例如我們?cè)谘芯可a(chǎn)過程的組織決策時(shí)，既要考慮生產(chǎn)系統(tǒng)的產(chǎn)量最大，又要使產(chǎn)品質(zhì)量高，生產(chǎn)成本低等。這些目標(biāo)之間相互作用和矛盾，使決策過程相當(dāng)復(fù)雜使決策者常常很難輕易作出決策.這類具有多個(gè)目標(biāo)的決策總是就是多目標(biāo)決策.多目標(biāo)決策方法現(xiàn)已廣泛地應(yīng)用于工藝過程、工藝設(shè)計(jì)、配方配比、水資源利用、能源、環(huán)境、人口、教育、經(jīng)濟(jì)管理等領(lǐng)域.2文獻(xiàn)綜述2.1國(guó)外研究現(xiàn)狀渡河問題有不同的版本，從目前參閱的文獻(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]的人、狼、羊、菜過河問題利用多為向量的方法解決.但是解決方法是類似的,都是要找到允許狀態(tài)和允許決策.2.2國(guó)外研究現(xiàn)狀評(píng)價(jià)綜上所述，渡河問題至今仍是一個(gè)邏輯難題.國(guó)外對(duì)于過河問題的研究很多，但是不是很全面，由于渡河問題的種類很多，盡管研究方法大體一樣，但是他的解卻是有很多種，或者有的問題根本無解，就夫妻過河問題而言當(dāng)4對(duì)夫妻過河，船只能載2人時(shí)問題無解.本文在夫妻過河問題的基礎(chǔ)上從3對(duì)、4對(duì)夫妻研究至5對(duì)、6對(duì)，并推至n對(duì)夫妻過河情況，利用圖解法和matlab編程解決.2.3問題提出問題1：若船最多能載3人，5對(duì)夫妻能否過河？六對(duì)夫妻呢？如果不可以那么船最多能載幾人才可以？問題2：n對(duì)夫妻要過河，船最多能載m人，n和m有怎樣的關(guān)系？任務(wù)：用matlab編寫程序求問題1的解，并用已有程序驗(yàn)證問題2.3模型假設(shè)1.不考慮過河環(huán)境因素的影響情況；2.夫妻過河只能依靠小船；3.每個(gè)男人和女人都會(huì)劃船；4符號(hào)說明表示渡河的夫妻對(duì)數(shù)表示第k次渡河前此岸丈夫的人數(shù)表示第k次渡河前此岸妻子的人數(shù)表示第次過渡船上丈夫的人數(shù)表示第次過渡船上妻子的人數(shù)表示第幾次渡河表示渡河的次數(shù)表示允許狀態(tài)集合表示允許決策集合表示狀態(tài)表示決策5重述3、4對(duì)夫妻過河問題的解有3對(duì)夫妻要過河，船最多可載2人，約束條件是根據(jù)阿拉伯法律，任一女子不得在其丈夫不在場(chǎng)的情況下與其他男子在一起，問此時(shí)這3對(duì)夫妻能否過河？如果是4對(duì)夫妻過河，其他條件不變的情況下，夫妻能否過河？記次過河前此岸丈夫的人數(shù)為，妻子的人數(shù)為.記表示狀態(tài)，=（）,記表示決策，=（）。5.13對(duì)夫妻過河的解（3,3）（3,3）去二女（3,2）去二女（3,1）回一女（3,0）回一女（3,1）去二男（1,1）回一男一女（2,2）去二男（0,2）去一女（0,3）去二女（0,1）回一女（0,2）去二女（0,0）5.24對(duì)夫妻過河的解（4,3）（4,3）去二女（4,2）回一女（4,4）去二女（4,0）去兩男去兩女（4,0）（4,2）（4,1）（4,0）去兩男去兩女（4,0）（4,2）（4,1）回一女可看出問題無法再解下去6五對(duì)夫妻過河模型6.1模型構(gòu)成記第次過河前此岸丈夫的人數(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ì)此岸和彼岸都是可行的.記第次過渡船上的丈夫的人數(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.31Matlab編程求解對(duì)于這個(gè)問題通常用“窮舉求解”的方法，即從初始狀態(tài)（5，5）開始，從允許決策集合D中選擇一個(gè)決策，產(chǎn)生一個(gè)新狀態(tài).若新狀態(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è)方面：（1）該狀態(tài)是否在允許狀態(tài)集合S中.（2）在由決策所確定產(chǎn)生的一系列狀態(tài)中，船由此岸駛向彼岸前的所有狀態(tài)不允許重復(fù)，船由彼岸駛向此岸前的所有狀態(tài)亦不允許重復(fù).可以應(yīng)用人工智能原理中的狀態(tài)空間搜索法解決.首先定義一個(gè)安全渡河問題的狀態(tài)空間，規(guī)定出該空間的初始狀態(tài)和目標(biāo)狀態(tài)，建立相應(yīng)的渡河規(guī)則和控制策略，而后推理搜索，直至找出由初始狀態(tài)到目標(biāo)狀態(tài)的某條路徑或一組路徑，即安全渡河的操作序列.用matlab編寫一段程序求解，程序編寫思路如下圖開始開始變量初始賦值化可行狀態(tài)奇數(shù)次移動(dòng)偶數(shù)次移動(dòng)選擇一種可行方案繼續(xù)移動(dòng)且下一次移動(dòng)重新開始結(jié)束程序運(yùn)行結(jié)果（程序見附錄）：ans=Columns1through115555555230052301022334Columns12through22000-1-1-1-1-1-1-1-1120-1-1-1-1-1-1-1-1Columns23through33-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1Columns34through44-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1Columns45through50-1-1-1-1-1-1-1-1-1-1-1-1從運(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,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)所討論問題變量不很多時(shí)，我們也常常利用作圖的方法來解決狀態(tài)轉(zhuǎn)移問題．對(duì)于“夫妻過河”問題求解，也就是要確定一系列的允許運(yùn)算(k=1，2，…,m)，使得我們可以在x－y平面上標(biāo)出允許狀態(tài)集S中的點(diǎn)，而將允許運(yùn)算看作是沿方格移動(dòng)1格或2格，為了區(qū)別小船的往返，我們用實(shí)線表示小船由此岸至彼岸，用虛線表示小船由彼岸至此岸．于是我們給出一個(gè)“夫妻過河”問題的最優(yōu)解法.（（5,5）去三女（5,2）回一女（5,3）去兩女（5,1）回一女（5,2）去三男（2,2）回一男一女（3,3）去三男（0,3）回一女（0,4）（0,1）去三女回一女（0,2）去兩女（0,0）圖解過程如下圖所示：554321（0,0）（5,5）12345xy7六對(duì)夫妻過河模型7.1模型構(gòu)成記第次過河前此岸丈夫的人數(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)集合，成為允許狀態(tài)集合，不難驗(yàn)證，對(duì)此岸和彼岸都是可行的.記第次過渡船上的丈夫的人數(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模型求解同樣的我們仿照“五對(duì)夫妻過河”在x－y平面上標(biāo)出允許狀態(tài)集S中的點(diǎn)，而將允許運(yùn)算看作是沿方格移動(dòng)1格或2格，為了區(qū)別小船的往返，我們用實(shí)線表示小船由此岸至彼岸，用虛線表示小船由彼岸至此岸．yy54321（0,0）（6,6）12345x6在解題過程中我們發(fā)現(xiàn)若要讓六對(duì)夫妻過河，路徑須經(jīng)由（6，3）到（0，4）狀態(tài)，由條件所致，無法通過這條路徑.那么我們改變條件為船最多能載4人，圖解過程如下圖yy54321（0,0）（6,6）12345x6所以由此我們得到6對(duì)夫妻，當(dāng)船至少能載4人時(shí)才可以安全渡河8對(duì)夫妻過河情況8.1求解因?qū)Ψ蚱抟^河，船最多能載人，我們可以利用一個(gè)簡(jiǎn)單的圖解法在解決前面的問題中，發(fā)現(xiàn)當(dāng)可行時(shí)每一次圖解法都要經(jīng)過下圖步驟或或-1另外我們總結(jié)了幾組數(shù)據(jù)：安全渡河可行數(shù)據(jù)表序號(hào)夫妻（對(duì)）船最大容量（人）132243353464574由此可推斷如果要使夫妻能安全渡河,和的關(guān)系應(yīng)為8.2驗(yàn)證利用已有程序驗(yàn)證（驗(yàn)證程序見附錄）得到以下結(jié)果>>fuqiman輸入丈夫數(shù)目：8輸入妻子數(shù)目：8輸入船的最大容量：4ans=沒有找到可行路徑！>>fuqiman輸入丈夫數(shù)目：8輸入妻子數(shù)目：8輸入船的最大容量：5ans=00050444338382848388>>fuqiman輸入丈夫數(shù)目：9輸入妻子數(shù)目：9輸入船的最大容量：5ans=0002010555449493959499>>fuqiman輸入丈夫數(shù)目：10輸入妻子數(shù)目：10輸入船的最大容量：5ans=沒有找到可行路徑（此處我們不再舉過多的例子）9總結(jié)與展望9.1總結(jié)本文對(duì)夫妻過河問題進(jìn)一步探討，由五對(duì)、六對(duì)延伸至對(duì)夫妻.其中五對(duì)、六對(duì)夫妻過河利用matlab編程和圖解法解決，解決對(duì)夫妻要過河，船最多能載人，和有怎樣的關(guān)系時(shí)，利用類比推斷的方法推斷出.再利用已有程序檢驗(yàn).鑒于本人知識(shí)水平和計(jì)算機(jī)編程水平有限，還有很多不足的地方，有待于日后進(jìn)一步學(xué)習(xí)和研究．9.2后續(xù)研究工作展望本文對(duì)夫妻過河問題進(jìn)一步探討，由五對(duì)、六對(duì)延伸至對(duì)夫妻.在五對(duì)夫妻渡河方案中由于本人計(jì)算機(jī)編程水平有限得到的結(jié)果不是最優(yōu)解（即過河所用次數(shù)最少），在對(duì)夫妻要過河，船最多能載人，和有怎樣的關(guān)系時(shí)，盡管推論得到驗(yàn)證但是說服力不足，所以后續(xù)的研究工作在如下幾個(gè)方面展開：利用matlab編程得到五對(duì)夫妻過河最優(yōu)情況仿照文獻(xiàn)中已有的方法求解夫妻過河問題參考文獻(xiàn)[1]付艷玲，高峰，偉.商人渡河問題解的存在性與算法實(shí)現(xiàn)[J].工程數(shù)學(xué)學(xué)報(bào)，2013,30:561[2]邵建峰，許丙勝.商人渡河問題的算法實(shí)現(xiàn)[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012,42:137[3]溫鴻航,溫鴻翔,任曉莉.渡河問題的圖解分析[J].電子科技，2012,25:33[4]溫鴻航，任曉莉，溫鴻翔.渡河問題的矩陣表示與迭代算法[J].電子科技,2012,25:101[5]達(dá)瓦,加央.種種渡河同題與其算法[J].科教文匯,2008,269[6]俞濤.“船運(yùn)狼、羊、菜”問題的新解法[J].師大學(xué)學(xué)報(bào)(自然科學(xué)版),1996,20:27[7]善強(qiáng),雷鳴.數(shù)學(xué)模型(第二版)[M].大學(xué),1998.24[8]啟源，金星，葉俊.數(shù)學(xué)模型[M].第三版.：高等教育，2003,7[9]天瑞.安全渡河問題的計(jì)算機(jī)求解和模擬[J].工科數(shù)學(xué)，1999，15:119[10]武建林.商人渡河游戲的解題算法[J].電腦編程技巧與維護(hù)，2009,78[11]念發(fā)，憲新，長(zhǎng)征.基于狀態(tài)空間搜索法的商人過河問題解決方案[J].電腦編程技巧與維護(hù)，2010，36[12]衛(wèi)國(guó).MATLAB程序設(shè)計(jì)教程[M].第二版.：中國(guó)水利水電，2010,2[13]靜,但琦.數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)[M].第三版.:高等教育,2003,19[14]北辰，建明.狀態(tài)轉(zhuǎn)移問題的計(jì)算機(jī)模擬[J].師專學(xué)報(bào)，1998，13:67[15]俞哲明，樊艷芬.利用數(shù)組解決農(nóng)夫過河問題[J].電腦，2013,（5）：151[16]義華.狀態(tài)轉(zhuǎn)移問題的圖論法建模[J].工業(yè)大學(xué)學(xué)報(bào),1997,23:92附錄五對(duì)夫妻過河程序：functionkexing=f_kexing(a)%判斷一個(gè)狀態(tài)a是否可行狀態(tài)%可行狀態(tài)為（0,i),（i,i),(5,i);0<=i<=5if(a(1)==a(2)&&a(1)>=0&&a(1)<=5)%可行狀態(tài)為（i,i),kexing=1;elseif(a(1)==0)&&a(2)>=0&&a(2)<=5%可行狀態(tài)為（0,i)kexing=1;elseif((a(1)==5)&&a(2)>=0&&a(2)<=5)%可行狀態(tài)為（5,i)kexing=1;elsekexing=0;endendendfunctionjie=guohe()kaishi=[5,5];%開始狀態(tài)jieshu=[0,0];%結(jié)束狀態(tài)jie=-ones(2,50);jie(:,1)=kaishi;jie(:,2)=[5,2];%第一次移動(dòng)三個(gè)人過去%過去時(shí)人盡量多，去多qu=[03212001;30110210];%回來時(shí)人盡量少hui=[01021032;10201301];yd_cishu=2;%移動(dòng)次數(shù)index=zeros(1,50);%指示第yd_cishu次移動(dòng)是采用的是那種方式index(1)=1;index(2)=1;%注意矩陣是否相等的判斷while(jie(1,yd_cishu)~=jieshu(1)||jie(2,yd_cishu)~=jieshu(2))if(mod(yd_cishu,2)~=0)%奇數(shù)次移動(dòng)while(index(yd_cishu)<=9)switch(index(yd_cishu))case{1}jixu=jie(:,yd_cishu)-qu(:,1);case{2}jixu=jie(:,yd_cishu)-qu(:,2);case{3}jixu=jie(:,yd_cishu)-qu(:,3);case{4}jixu=jie(:,yd_cishu)-qu(:,4);case{5}jixu=jie(:,yd_cishu)-qu(:,5);case{6}jixu=jie(:,yd_cishu)-qu(:,6);case{7}jixu=jie(:,yd_cishu)-qu(:,7);case{8}jixu=jie(:,yd_cishu)-qu(:,8);endif(f_kexing(jixu))%當(dāng)移動(dòng)狀態(tài)可行，則保存移動(dòng)情況yd_cishu=yd_cishu+1;%繼續(xù)移動(dòng)jie(:,yd_cishu)=jixu;index(yd_cishu)=index(yd_cishu)+1;index(yd_cishu)=1;%下一次移動(dòng)選擇從新開始break;elseindex(yd_cishu)=index(yd_cishu)+1;endendif(index(yd_cishu)>9)yd_cishu=yd_cishu-1;%回退endelse%偶數(shù)次移動(dòng)while(index(yd_cishu)<=9)switch(index(yd_cishu))case{1}jixu=jie(:,yd_cishu)+hui(:,1);case{2}%jixu=jie(:,yd_cishu)+hui(:,2);case{3}%jixu=jie(:,yd_cishu)+hui(:,3);case{4}%jixu=jie(:,yd_cishu)+hui(:,4);case{5}jixu=jie(:,yd_cishu)+hui(:,5);case{6}jixu=jie(:,yd_cishu)+hui(:,6);case{7}jixu=jie(:,yd_cishu)+hui(:,7);case{8}jixu=jie(:,yd_cishu)+hui(:,8)end%當(dāng)移動(dòng)狀態(tài)可行，則保存移動(dòng)情況且回來船上的人員狀態(tài)不能和上一次的情況完全一樣，否則就重復(fù)操作無意義了。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))))yd_cishu=yd_cishu+1;%繼續(xù)移動(dòng)jie(:,yd_cishu)=jixu;index(yd_cishu)=index(yd_cishu)+1;index(yd_cishu)=1;%下一次移動(dòng)選擇從新開始break;elseindex(yd_cishu)=index(yd_cishu)+1;endendif(index(yd_cishu)>9)yd_cishu=yd_cishu-1;%回退endendend驗(yàn)證程序：functions=fuqimann=input('輸入丈夫數(shù)目：');nn=input('輸入妻子數(shù)目：');nnn=input('輸入船的最大容量：');ifnn>nn=input('輸入丈夫數(shù)目：');nn=input('輸入妻子數(shù)目：');nnn=input('輸入船的最大容量：');endk=1;fori=0:nnnforj=0:nnnif(i+j<=nnn)&(i+j>0)d(k,1:3)=[i,j,1];d(k+1,1:3)=[-i,-j,-1];k=k+2;endendendk=1;fori=n:-1:0forj=nn:-1:0if((i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n))A(k,1:3)=[i,j,1];k=k+1;endendendsq(1,1)=n;sq(1,2)=nn;sq(1,3)=0;sq(1,4)=1;sq(1,5)=0;sq(