精品文檔推薦第十五講最短路線問題

1、最短路線在日常生活、工作中，經(jīng)常會(huì)遇到有關(guān)行程路線的問題。比如：郵遞員送信，要穿遍所有的街道，為了少走冤枉路，需要 選擇一條最短的路線；旅行者希望尋求最佳旅行路線，以求能夠走最 近的路而達(dá)到目的地，等等。這樣的問題，就是我們所要研究學(xué)習(xí)的“最短路線問題”。例1假如直線AB是一條公路，公路兩旁有甲乙兩個(gè)村子，如 下圖1?，F(xiàn)在要在公路上修建一個(gè)公共汽車站，讓這兩個(gè)村子的人到 汽車站的路線之和最短。問：車站應(yīng)該建在什么地方？分析如果只考慮甲村的人距離公路AB最近，只要由甲村向公甲甲AQ丨.Ao B乙A7“ B乙路AB畫一條垂直線，交AB于C點(diǎn)，那么C點(diǎn)是甲村到公路AB最近的點(diǎn)，但是乙村到C點(diǎn)就較遠(yuǎn)了

2、反過(guò)來(lái)，由乙村向公路 AB畫垂線，交AB于D點(diǎn)，那么D點(diǎn) 是乙村到公路AB最近的點(diǎn)。但是這時(shí)甲村到公路 AB的D點(diǎn)又遠(yuǎn)了。 因?yàn)楸绢}要求我們?cè)诠?AB上取的建站點(diǎn)，能夠兼顧甲村和乙村的 人到這個(gè)車站來(lái)不走冤枉路（既路程之和最短），根據(jù)我們的經(jīng)驗(yàn)： 兩個(gè)地點(diǎn)之間走直線最近，所以，只要在甲村乙村間連一條直線，這 條直線與公路AB交點(diǎn)P,就是所求的公共汽車站的建站點(diǎn)了 （圖2）。解 用直線把甲村、乙村連起來(lái)。因?yàn)榧状逡掖逶诠返膬蓚?cè)， 所以這條連線必與公路 AB有一個(gè)交點(diǎn)，設(shè)這個(gè)交點(diǎn)為 P,那么在P 點(diǎn)建立汽車站，就能使甲村乙村的人到汽車站所走的路程之和最短。例2 一個(gè)郵遞員投送信件的街道如圖 3

3、所示，圖上數(shù)字表示 各段街道的千米數(shù)。他從郵局出發(fā)，要走遍各街道，最后回到郵局。 問：走什么樣的路線最合理？全程要走多少千米？1 242_分析 選擇最短的路線最合理。那么，什么路線最短呢？ 一筆畫路線應(yīng)該是最短的。郵遞員從郵局出發(fā)，還要回到郵局，按一筆畫問題，就是從偶點(diǎn)出發(fā)，回到偶點(diǎn)。因此，要能一筆把路線畫出來(lái)，必須途徑的各點(diǎn)全是偶點(diǎn)。但是圖中有8個(gè)奇點(diǎn)，顯然郵遞員要走遍所 有街道而又不走重復(fù)的路是不可能的。 要使郵遞員從郵局出發(fā)，仍回 到郵局，必須使8個(gè)奇點(diǎn)都變成偶點(diǎn)，就是要考慮應(yīng)在哪些街道上重 復(fù)走，也就是相當(dāng)于在圖上添哪些線段，能使奇點(diǎn)變成偶點(diǎn)。如果有 不同的添法，就還要考慮哪一種添法能

4、使總路程最短。為使8個(gè)奇點(diǎn)變成偶點(diǎn)，我們可以用圖4的4種方法走重復(fù)的路線。k11242131/112421322412332圖4中添虛線的地方，就是重復(fù)走的路線。重復(fù)走的路程分別為:(a) 3X 4=12 (千米)(b) 3X 2+ 2X2=10 (千米)(c) 2X 4=8 (千米)(d) 3X 2+ 4X2=14 (千米)當(dāng)然，重復(fù)走的路程最短，總路程就最短。從上面的計(jì)算不難找 出最合理的路線了。解 郵遞員應(yīng)按圖4（ c）所示的路線走，這條路重復(fù)的路程最 短，所以最合理。全程為：（1 + 2 + 4+2+ 1）X 2+ 3X 6+ 2X4=20+ 18+ 8=46 （千米）例3圖5中的線段

5、表示的是小明從家到學(xué)校所能經(jīng)過(guò)的所有 街道。小明上學(xué)走路的方向都是向東或向南，因?yàn)樗幌肫x學(xué)校的 方向而走冤枉路。那么小明從家到學(xué)校可以有多少條不同的路線？北小明家學(xué)校 分析 為了敘述的方便，我們?cè)诟鹘徊纥c(diǎn)標(biāo)上字母（見圖 6）小明E我們從小明家出發(fā)，順序往前推。由于從小明家到A、B、C、D各 處都是沿直線行走，所以都只有一種走法。我們分別在交叉點(diǎn)處標(biāo)上“ 1”。而從小明家到E處，就有先到A或先到D的兩種走法，正好 是兩個(gè)對(duì)角上標(biāo)的數(shù)1 + 1的和。從小明家到F點(diǎn)，則有3條路線，又 正好是兩個(gè)對(duì)角上標(biāo)的數(shù)1+2的和。標(biāo)在各交叉點(diǎn)的數(shù)，就是依次順序推出的到各交叉點(diǎn)能有多少種 不同的路線的數(shù)。從中我們可以看出，每個(gè)格內(nèi)上右角與下左角兩個(gè) 對(duì)角上的數(shù)的和，正好等于下右角上的數(shù)。解 從小明家到學(xué)校有13條不同的路線。如圖7所示。小明家1111234EFG425913CB