作業(yè)1、2：商人過河一、 問題重述問題一：4個(gè)商人帶著4個(gè)隨從過河，過河的工具只有一艘小船，只能同時(shí)載兩個(gè)人過河，包括劃船的人。隨從們密約, 在河的任一岸, 一旦隨從的人數(shù)比商人多, 就殺人越貨。乘船渡河的方案由商人決定。商人們?cè)鯓硬拍馨踩^河?問題二：假如小船可以容3人，請(qǐng)問最多可以有幾名商人各帶一名隨從安全過河。二、問題分析問題可以看做一個(gè)多步?jīng)Q策過程。每一步由此岸到彼岸或彼岸到此岸船上的人員在安全的前提下(兩岸的隨從數(shù)不比商人多),經(jīng)有限步使全體人員過河。用狀態(tài)變量表示某一岸的人員狀況，決策變量表示船上的人員情況，可以找出狀態(tài)隨決策變化的規(guī)律。問題就轉(zhuǎn)換為在狀態(tài)的允許變化范圍內(nèi)（即安全渡河條件），確定每一步的決策，達(dá)到安全渡河的目標(biāo)。三問題假設(shè)1. 過河途中不會(huì)出現(xiàn)不可抗力的自然因素。2. 當(dāng)隨從人數(shù)大于商人數(shù)時(shí)，隨從們不會(huì)改變殺人的計(jì)劃。3船的質(zhì)量很好，在多次滿載的情況下也能正常運(yùn)作。4. 隨從會(huì)聽從商人的調(diào)度。四、模型構(gòu)成x(k)第k次渡河前此岸的商人數(shù) x(k),y(k)=0,1,2,3,4;y(k)第k次渡河前此岸的隨從數(shù) k=1,2,.s(k)= x(k), y(k)過程的狀態(tài) S允許狀態(tài)集合S=(x,y) |x=0,y=0,1,2,3,4; x=4,y=0,1,2,3,4;x=y=1,2,3u(k)第k次渡船上的商人數(shù) u(k), v(k)=0,1,2;v(k) 第k次渡船上的隨從數(shù) k=1,2.d(k)=( u(k), v(k)過程的決策 D允許決策集合D=u,v|u+v=1,2,u,v=0,1,2狀態(tài)因決策而改變s(k+1)=s(k)+(-1)k*d(k)狀態(tài)轉(zhuǎn)移律求d(k) D(k=1,2,.n),使s(k) S并按轉(zhuǎn)移律s(k+1)=s(k)+(-1)k*d(k)由（4,4）到達(dá)（0,0）商人x隨從y數(shù)學(xué)模型： （1） （2） （3） （4） （5）模型分析：由（2）（3）（5）可得 化簡(jiǎn)得 綜合（4）可得 和 （6）還要考慮 （7）把（2）（3）帶入（7）可得化簡(jiǎn)得 （8）綜合（6）（7）（8）式可得 滿足條件的情況滿足下式 （9） 所以我們知道滿足條件的點(diǎn)如上圖所示：點(diǎn)移動(dòng)由 （8）到達(dá) （6）時(shí)，可以認(rèn)為完成渡河。因?yàn)橐苿?dòng)的格數(shù)小于等于2，只有中心點(diǎn)（2，2）到（6）點(diǎn)和（8）點(diǎn)的距離為2，所以中心點(diǎn)（2,2）成為渡河的關(guān)鍵點(diǎn)。當(dāng)我們移動(dòng)到（2,2）點(diǎn)時(shí)，就無法進(jìn)行下去。故4個(gè)商人，4個(gè)隨從，船容量為2人時(shí)，無法安全渡河。對(duì)于問題二，我們可以建立模型為： （10） （11） （12） （13） （14） u(k), v(k)=0,1,2,3; （15）通過類似于問題一的步驟可以知道：坐標(biāo)上的關(guān)鍵點(diǎn)是（3,3），最多可以五名商人帶五名隨從過去。 需要確定五名商人帶五名隨從的方案可行再確定六名商人帶六名隨從的方案不可行 1、五名商人帶五名隨從的情況： （1）首先不可能有三名商人先過河，兩名商人一名隨從過河，一名商人兩名隨從過河 （2）三個(gè)隨從先過河（5,2），回來一個(gè)隨從（5,3），過去兩個(gè)隨從（5,1）回來一個(gè)隨從（5,2），再過去三個(gè)商人（2,2），回來一個(gè)商人一個(gè)隨從（3,3），再過去三個(gè)商人（0,3），回來一個(gè)隨從（0,4），過去三個(gè)隨從（0,1），回來一個(gè)隨從（0,2）再過去兩個(gè)隨從（0,0）綜上可知：五名商人帶五名隨從，小船可以載三個(gè)人可以過河 2、六名商人帶六名隨從的情況： （1）首先不可能有三名商人先過河，兩名商人一名隨從過河，一名商人兩名隨從過河 （2）三個(gè)隨從先過河（6,3），回來一個(gè)隨從（6,4），過去兩個(gè)隨從（6,2）回來一個(gè)隨從（6,3），過去三個(gè)商人（3,3），此時(shí)兩岸都是（3,3），由坐標(biāo)法分析知，這是最接近終點(diǎn)的臨界點(diǎn)，但是如果回來的時(shí)候一定是回來一個(gè)商人和一個(gè)隨從，如果這一步可行，后面就進(jìn)行不去 綜上所述，六個(gè)商人帶六個(gè)隨從，小船載三個(gè)人的情況下不能渡河 結(jié)合1、2知，當(dāng)小船最多載三個(gè)人的時(shí)候，最多五名商人各帶一個(gè)隨從可以過河。5、 模型的檢