《商人過河問題》由會員分享，可在線閱讀，更多相關(guān)《商人過河問題（13頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,*,單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,,,*,商人過河問題,,此類智力問題當(dāng)然可以通過一番思考，拼湊出一個可行方案來。 ????但是，我們現(xiàn)在希望能找到求解這類問題的規(guī)律性、建立數(shù)學(xué)模型，用以解決更為廣泛的問題。,分析,,此問題可視為一個,多步?jīng)Q策,問題，每一步就是一,,次渡河，每次渡河就是一次狀態(tài)轉(zhuǎn)移。 ???用三維變量,(x,y,z),表示狀態(tài)：,x?------,商人數(shù)，,y ------,隨從數(shù),,x,y,的,取值范圍：,{
2、0,，,1,，,2,，,3} ???z ------,船,,,z,的取值范圍：,{0,1},那么,安全狀態(tài),可表示為,,x=0,3, y=0,1,2,3,或,,x=1,2, y=x,,,,,,這就是此問題的數(shù)學(xué)模型。,(3,3,1),(3,2,1),(3,1,1),(2,2,1),(3,0,1),(0,3,1),(0,2,1),(1,1,1),(0,1,1),(3,2,0),(3,1,0),(2,2,0),(3,0,0),(0,3,0),(0,2,0),(1,1,0),(0,1,0),(0,0,0),模型建立,,,,這樣問題要求由,(3,，,3,，,1),變到,(0,，,0,，,0),
3、的一條道路。 ?根據(jù)題意，狀態(tài)轉(zhuǎn)移時要滿足一定的規(guī)則：,1. Z,從,1,變?yōu)?0,與從,0,變?yōu)?1,交替進行；,2.,當(dāng),Z,從,1,變?yōu)?0,時，即船從此岸到對岸，此岸人數(shù)減,,少,1,或,2,個； ?? ?即,(,x,,,y,,1)→(,u,,,v,,0),時,,,u,≤,x,,,v,≤,y,,,u,+,v=x,+,y,-1 or,,,u,+,v,=,x,+,y,-2 ?3.,當(dāng),Z,從,0,變?yōu)?1,時，即船從對岸到此岸，此岸人數(shù)增,,加,1,或,2,個； ??? 即,(,x,,,y,,0)→(,u,,,v,,1),時,,,u,≥,x,,,v,≥,y,,,u,+,v,=,x,
4、+,y,+1 or,,,u,+,v,=,x,+,y,+2 ?4.,不重復(fù)已出現(xiàn)過的狀態(tài)，如,,,(3,3,1)→(3,1,0)→(3,3,1),；,模型求解,按照以上規(guī)則，求解過程如下：,從,(3,，,2,，,0),只能到達,(3,，,3,，,1)/*,不必考慮*,/,從,(3,3,1),出發(fā),(3,2,0),(3,1,0),如右圖,(2,2,0),,,,,(3,3,1),(3,2,0),(3,1,0),(2,2,0),從,(3,1,0),出發(fā),(3,3,1),/*,不必考慮*,/,(3,2,1)/*,可取*,/,從,(2,2,0),出發(fā),(3,3,1),/*,不必考慮*,/,(3,2,1)/
5、*,可取*,/,如下圖所示：,這樣可得到所有答案,:,,,由此可得到渡河策略,:,(3,3,1) (3,2,1),→,(3,0,0),→,(3,1,1),→,(1,1,0),→,(2,2,1),→,(0,2,0),→,(0,3,1),→,(0,1,0) (0,0,0),(2,2,0),(3,1,0),(1,1,1),(0,2,1),,,狀態(tài)平面分析法,,,設(shè),x,為商人數(shù)，,y,為隨從數(shù)，在,xoy,平面上作分析。先標(biāo)出此岸的,安全狀態(tài)點。,,起始點,-----(3,，,3),，最終點,-----(0,，,0)
6、,模型求解就是求從狀態(tài),(3,，,3),轉(zhuǎn)移到狀態(tài),(0,，,0),的方法。 ????用,di,表示第,i,次狀態(tài)轉(zhuǎn)移，,i,為奇數(shù)時：船從此岸到對岸，,x,y,只能減少，不能增加,(,即移向左下方,),且,(x+y),至多減少,2,，（即至多移兩格,) ????i,為偶數(shù)時：船從對岸到此岸。,模型求解法二,例如：,d1,：,(3,3)-----(2,2) 1,個商人,1,個隨從過對岸,d1,：,(3,3)-----(3,1)2,個隨從過對岸,如圖所示,:,,,,(1),若船的情況不變，則,2,名商人,2,個隨從,,如何安全渡河？,,,(2) m,名商人,m,個隨從,(m≥4),能否安全
7、渡,,河？,思 考,(1) (2,2)→(1,1) or (2,0)→(2,1)→(0,1) → (1,1)→(0,0),,,如下圖：,,,(2) m,名商人,m,個隨從,(m≥4),無法安全渡河,,,如,m=4,時的圖,(,如下圖,),，,d7,就無法作不重復(fù)的轉(zhuǎn)移。,,,(1),夫妻過河問題 ????有三對夫妻要過河，船最多可載兩人。 ????約束條件是根據(jù)法律，任一女子不得在其丈夫不在場的情況下與另外男子在一起，問此時這三對夫妻能否過河,?,四對夫妻呢,,(2),人、狗、雞、米過河問題 ????某人要帶一條狗、一只雞、一籮米過河，但小船除需要人劃外，最多只能載一物過河，而當(dāng)人不在場時，狗要咬雞、雞要吃米。問此人應(yīng)如何過河,?,,探 索,
商人過河問題
