四年級(jí)統(tǒng)籌與最優(yōu)化過河問題詳細(xì)分析-終結(jié)版

1、年級(jí)統(tǒng)籌與最優(yōu)化-過河問題詳細(xì)解析終結(jié)版時(shí)間統(tǒng)籌-過河問題網(wǎng)上關(guān)于過河問題有很多解題方法。其中最典型的就是“快的來回走，接近的一起走”，但問題什么是最接近的？數(shù)字大小接近，還是順序接近？另外即使接近的找到了，你也會(huì)發(fā)現(xiàn)，有些解題結(jié)果也不是最佳，反而是速度最快的反復(fù)送速度最慢的時(shí)間更短！那么到底該如何解題呢？本文將作出詳細(xì)的分析：首先明確兩種模式：通常而言，假設(shè)A為最快，B為次快，而Z是任意一個(gè)其他旅行者。模式一：“由A護(hù)送最慢過橋，回來，然后繼續(xù)護(hù)送最慢的過橋，再回來”，也就是快的來回送慢的。模式二：“兩個(gè)最快的過橋（A和B過橋），A回來，兩個(gè)最慢的過橋，B回來”，也就是分兩撥（兩個(gè)一組），最

2、快的一組，最慢的一組，最快的一組過去，然后最快的那個(gè)A回來，然后最慢的一組兩個(gè)過去，B回來。明確上述概念后，開始解題：和人數(shù)相關(guān)（三個(gè)以內(nèi)） 當(dāng)數(shù)量為1時(shí)，直接過河，不需要策略； 當(dāng)人數(shù)是2時(shí)，兩個(gè)人一起過河，也不需要策略； 當(dāng)人數(shù)為3時(shí)，就必須使用策略，也就是“快的來回走，快的送慢的”例題1：小明騎在牛背上趕牛過河。共有甲乙丙3頭牛，甲牛過河需要1分鐘，乙牛過河需要2分鐘，丙牛過河需要5分鐘。每次只能趕兩頭牛過河，那么小明要把這3頭牛都趕到對(duì)岸，最少要用多少分鐘？解題思路：用“快的來回走，快的送慢的”最快的牛是甲，因此是甲牛來回走。陪著送其它牛，至于先送乙還是先送丙？答案是都可以。甲+乙2分

3、鐘甲回來1分鐘甲+丙5分鐘共8分鐘最佳，先送丙也可以乙+丙5分鐘乙回來2分鐘甲+乙2分鐘共9分鐘-不采用解題思路建議方案，肯定不是最佳方案和人數(shù)相關(guān)（四個(gè)及四個(gè)以上）當(dāng)人數(shù)N四個(gè)及四個(gè)以上時(shí)，要分出最快的前兩個(gè),最慢的后兩個(gè)。最快A,次快B，次慢Y，最慢Z如果人數(shù)N>4,設(shè)A、B為走得最快和次快的旅行者，過橋所需時(shí)間分別為a、b;而Z、Y為走得最慢和次慢的旅行者，過橋所需時(shí)間分別為z、y。那么,當(dāng)2b>=a+y時(shí)，使用模式一將Z和Y移動(dòng)過橋；也就是當(dāng)?shù)诙煜鄬?duì)較慢的時(shí)候（用的時(shí)間多），采用最快的A一個(gè)一個(gè)送最慢的。當(dāng)2bva+y時(shí)，使用模式二將Z和Y移動(dòng)過橋；也就是當(dāng)?shù)诙焯斓臅r(shí)

4、候（用的時(shí)間少），采用最快的一組過，最快的A回來，然后最慢的一組過去，B回來。例題2：小明騎在牛背上趕牛過河。共有甲乙丙丁4頭牛，甲牛過河需要1分鐘，乙牛過河需要2分鐘，丙牛過河需要5分鐘，丁牛過河需要6分鐘。每次只能趕兩頭牛過河，那么小明要把這4頭牛都趕到對(duì)岸，最少要用多少分鐘？解題思路：首先開始排序125,6。A二甲，B二乙，Y二丙，Z二丁。2xb=4va+y=1+5=6，屬于第二快太快，用時(shí)較短。采用模式二過河。即甲乙先過，甲回來，丙丁過去，乙回來，然后甲乙過去。具體如下：甲、乙；時(shí)間：2 甲；時(shí)間：1丁、丙；時(shí)間:6 乙；時(shí)間：2甲、乙；時(shí)間：2時(shí)間：2+1+6+2+2=13分鐘例題3

5、：有一家五口人要在夜晚過一座獨(dú)木橋.他們家里的老爺爺行動(dòng)非常不便,過橋需要12分鐘；孩子們的父親貪吃且不愛運(yùn)動(dòng),體重嚴(yán)重超標(biāo),過河需要時(shí)間也較長(zhǎng),8分鐘；母親則一直堅(jiān)持勞作,動(dòng)作還算敏捷,過橋要6分鐘；兩個(gè)孩子中姐姐需要3分鐘,弟弟只要1分鐘.當(dāng)時(shí)正是初一夜晚又是陰天,不要說月亮,連一點(diǎn)星光都沒有,真所謂伸手不見五指.所幸的是他們有一盞油燈,同時(shí)可以有兩個(gè)人借助燈光過橋.但要命的燈油將盡,這盞燈只能再維持30分鐘了!他們焦急萬分,該怎樣過橋呢?解題思路：第一、開始排序1,3,6,8,12第二、分兩組。前兩快：A弟弟：1分鐘，B姐姐：3分鐘；后兩慢：Y父親：8分鐘，Z爺爺：12分鐘第三、用第二慢

6、作比較。2xb=2x3=6va+y=1+8=9,第二慢用時(shí)少，應(yīng)該用模式二，快的兩個(gè)和最慢的兩個(gè)分開，快的兩個(gè)先走。姐、弟；時(shí)間：3AV 弟；時(shí)間：1父、爺；時(shí)間：12V 姐；時(shí)間：3第四、現(xiàn)在剩下弟弟、姐姐和媽媽，三個(gè)人。在三個(gè)人條件，用最快的人送其它兩個(gè)人即可，慢的兩個(gè)人順序無關(guān)。弟，媽；時(shí)間：6-V弟；時(shí)間：1弟、姐；時(shí)間：3A第五、總時(shí)間：3+1+12+3+6+1+3=29分鐘例題4：有一家五口人要在夜晚過一座獨(dú)木橋.他們家里的老爺爺行動(dòng)非常不便,過橋需要12分鐘；孩子們的父親貪吃且不愛運(yùn)動(dòng),體重嚴(yán)重超標(biāo),過河需要時(shí)間也較長(zhǎng),8分鐘；母親則一直堅(jiān)持勞作,動(dòng)作還算敏捷,過橋要6分鐘；兩個(gè)

7、孩子中姐姐需要5分鐘,弟弟只要1分鐘.當(dāng)時(shí)正是初一夜晚又是陰天,不要說月亮,連一點(diǎn)星光都沒有,真所謂伸手不見五指.所幸的是他們有一盞油燈,同時(shí)可以有兩個(gè)人借助燈光過橋.但要命的燈油將盡,!他們焦急萬分,該怎樣用最快的速度過橋呢?解題思路：第一、開始排序1,5,6,8,12第二、分兩組。前兩快：A弟弟：1分鐘，B姐姐：5分鐘；后兩慢：Y父親：8分鐘，Z爺爺：12分鐘第三、用第二慢作比較。2xb=2x5=10>a+y=1+8=9,第二慢用時(shí)多，應(yīng)該用模式一，由最快的送最慢的。弟、爺；時(shí)間：12町弟；時(shí)間:1第四、現(xiàn)在剩下弟弟、姐姐，媽媽，爸爸，四個(gè)人。繼續(xù)排序1,5,6,8。用第二慢作比較。2xb=2x5=10>a+y=1+6=7,第二慢用時(shí)多