小學奧數(shù)講義最短路線專題小學奧數(shù)講義最短路線專題/NUM咨詢熱線淀校區(qū)地址：北京市海淀區(qū)北三環(huán)西路聯(lián)想橋滿庭芳園（人民大學東門）1號樓A座206室乘車路線：1、紅民村站下：425路，619路，718路，827路，836路，323路，422路，361路，367路。2、四通橋東站下：619路，8路，727路，967路，801路，836路，731路，425路，422路，302路，運通101路，運通201路。小學奧數(shù)講義最短路線專題小學奧數(shù)講義最短路線專題最短路線專題在日常生活、工作中，經(jīng)常會遇到有關行程路線的問題。比如：郵遞員送信，要穿遍所有的街道，為了少走冤枉路，需要選擇一條最短的路線；旅行者希望尋求最佳旅行路線，以求能夠走最近的路而達到目的地，等等。這樣的問題，就是我們所要研究學習的“最短路線問題”。典型例題例[1]假如直線AB是一條公路，公路兩旁有甲乙兩個村子，如下圖1。現(xiàn)在要在公路上修建一個公共汽車站，讓這兩個村子的人到汽車站的路線之和最短。問：車站應該建在什么地方？AAB甲村乙村AB甲村乙村圖1圖2分析如果只考慮甲村的人距離公路AB最近，只要由甲村向公路AB畫一條垂直線，交AB于C點，那么C點是甲村到公路AB最近的點，但是乙村到C點就較遠了。反過來，由乙村向公路AB畫垂線，交AB于D點，那么D點是乙村到公路AB最近的點。但是這時甲村到公路AB的D點又遠了。因為本題要求我們在公路AB上取的建站點，能夠兼顧甲村和乙村的人到這個車站來不走冤枉路（既路程之和最短），根據(jù)我們的經(jīng)驗：兩個地點之間走直線最近，所以，只要在甲村乙村間連一條直線，這條直線與公路AB交點P，就是所求的公共汽車站的建站點了（圖2）。解用直線把甲村、乙村連起來。因為甲村乙村在公路的兩側，所以這條連線必與公路AB有一個交點，設這個交點為P，那么在P點建立汽車站，就能使甲村乙村的人到汽車站所走的路程之和最短。例[2]一個郵遞員投送信件的街道如圖3所示，圖上數(shù)字表示各段街道的千米數(shù)。他從郵局出發(fā)，要走遍各街道，最后回到郵局。問：走什么樣的路線最合理？全程要走多少千米？1124213分析選擇最短的路線最合理。那么，什么路線最短呢？一筆畫路線應該是最短的。郵遞員從郵局出發(fā)，還要回到郵局，按一筆畫問題，就是從偶點出發(fā)，回到偶點。因此，要能一筆把路線畫出來，必須途徑的各點全是偶點。但是圖中有8個奇點，顯然郵遞員要走遍所有街道而又不走重復的路是不可能的。要使郵遞員從郵局出發(fā)，仍回到郵局，必須使8個奇點都變成偶點，就是要考慮應在哪些街道上重復走，也就是相當于在圖上添哪些線段，能使奇點變成偶點。如果有不同的添法，就還要考慮哪一種添法能使總路程最短。12124213124213124213124213(a)(b)(c)(d)圖4圖4中添虛線的地方，就是重復走的路線。重復走的路程分別為：3×4=12（千米）3×2＋2×2=10（千米）2×4=8（千米）3×2＋4×2=14（千米）當然，重復走的路程最短，總路程就最短。從上面的計算不難找出最合理的路線了。解郵遞員應按圖4（c）所示的路線走，這條路重復的路程最短，所以最合理。全程為：（1＋2＋4＋2＋1）×2＋3×6＋2×4=20＋18＋8=46（千米）小明家學校北小明家學校北分析為了敘述的方便，我們在各交叉點標上字母（見圖6）。小明家小明家ABFEFDEF我們從小明家出發(fā)，順序往前推。由于從小明家到A、B、C、D各處都是沿直線行走，所以都只有一種走法。我們分別在交叉點處標上“1”。而從小明家到E處，就有先到A或先到D的兩種走法，正好是兩個對角上標的數(shù)1+1的和。從小明家到F點，則有3條路線，又正好是兩個對角上標的數(shù)1+2的和。標在各交叉點的數(shù)，就是依次順序推出的到各交叉點能有多少種不同的路線的數(shù)。從中我們可以看出，每個格內(nèi)上右角與下左角兩個對角上的數(shù)的和，正好等于下右角上的數(shù)。小明家學校北小明家學校北1121314259134A