商人過(guò)河問(wèn)題.doc

_商人過(guò)河數(shù)學(xué)建模論文摘要4個(gè)商人帶著4個(gè)仆人過(guò)河，過(guò)河的工具只有一艘小船，只能同時(shí)載兩個(gè)人過(guò)河，包括劃船的人。在河的任何一邊，只要仆人的數(shù)量超過(guò)商人的數(shù)量，仆人就會(huì)聯(lián)合起來(lái)將商人殺死并搶奪其財(cái)物，問(wèn)應(yīng)如何設(shè)計(jì)過(guò)河順序才能讓所有人都安全地過(guò)到河的另一邊。經(jīng)典的商人過(guò)河問(wèn)題可以看做一個(gè)多步?jīng)Q策過(guò)程。每一步由此岸到彼岸或彼岸到此岸船上的人員在安全的前提下(兩岸的隨從數(shù)不比商人多),經(jīng)有限步使全體人員過(guò)河。用狀態(tài)變量表示某一岸的人員狀況，決策變量表示船上的人員情況，可以找出狀態(tài)隨決策變化的規(guī)律。問(wèn)題就轉(zhuǎn)換為在狀態(tài)的允許變化范圍內(nèi)（即安全渡河條件），確定每一步的決策，達(dá)到安全渡河的目標(biāo)。分別建立兩個(gè)模型：模型一采用窮舉法，對(duì)各種過(guò)河的方案一一列舉，然后根據(jù)商人們要安全過(guò)河為前提對(duì)各種進(jìn)行了列舉，經(jīng)過(guò)層層篩選，最終求出商人安全的方案。模型二采用圖解法，利用圖示表示說(shuō)明該題的解法。關(guān)鍵詞：窮舉法多步?jīng)Q策圖解法安全渡河一、問(wèn)題提出4個(gè)商人帶著4個(gè)仆人過(guò)河，過(guò)河的工具只有一艘小船，只能同時(shí)載兩個(gè)人過(guò)河，包括劃船的人。在河的任何一邊，只要仆人的數(shù)量超過(guò)商人的數(shù)量，仆人就會(huì)聯(lián)合起來(lái)將商人殺死并搶奪其財(cái)物，問(wèn)應(yīng)如何設(shè)計(jì)過(guò)河順序才能讓所有安全過(guò)河。二、模型的假設(shè)和符號(hào)說(shuō)明模型假設(shè)：過(guò)河途中不會(huì)出現(xiàn)不可抗力的自然因素當(dāng)仆人數(shù)大于商人數(shù)時(shí)，隨從們不會(huì)改變殺人的計(jì)劃船很結(jié)實(shí)，不會(huì)發(fā)生任何的意外（2） 符號(hào)的說(shuō)明 （A,B）表示商人和仆人的個(gè)數(shù)，A表示商人，B表示仆人 三、模型的建立模型一(窮舉法）：此岸船彼岸（4,4）（0,0）（0,0）（3,3）（1,1,）（0,0）（3,3）（1,0）（0,1）（3,2）（1,1）（0,1）（3,2）（0,1）（1,1）（2,2）（1,1）（1,1）（2.2）（0,1）（2,1）（2,2,）（0,0）（2,2）這樣如果商人回去，彼岸的商人就比仆人多了，如果仆人過(guò)去，此岸的仆人就會(huì)比商人多了。所以無(wú)法達(dá)到（0,0）這樣的最終結(jié)果。模型二（圖解法）：四人過(guò)河模型圖允許步驟數(shù)L是沿方格線移動(dòng)1格或2格，L為奇數(shù)時(shí)向左.下方移動(dòng)，L為偶數(shù)時(shí)向右.上方移動(dòng)，要確定一系列的L，使初始狀態(tài)（4，4）最終變?yōu)椋?，0），無(wú)論怎樣走都必須經(jīng)過(guò)中間點(diǎn)（2，2），然后奇數(shù)次到達(dá)Y軸,，而無(wú)論怎么變化人數(shù)都也只能到達(dá)此點(diǎn)后不能繼續(xù)走下去，只能循環(huán)走，達(dá)