4015擦線法最短路線 | 高斯 小學奧數知識點視頻 | math olympiad #數學奧利匹克

阿熊的学堂
9粉絲
1 次觀看·2025年1月4日
有一天,朱小白要從AD到BD,他打開地圖,發現有這麼多條路
根據經驗,他把走每條路所需要的時間標在了圖上
那他最快多久能走到BD呢?
先來把圖變簡單一些,看這裏
從F如果往H走,接下來就只能走到D了
所以這兩條路,其實就是一條路
把它合併一下,就是9分鐘走到
同樣的,這一段也可以合起來,10分鐘走到
注意,這條路只能用來從C走到E
可是想要從C走到E,其實從這邊走更快
只要9分鐘就能到了
也就是說,這條路唯一能派上用場的
從C走到E這件事兒,咱們也不用它
那它就徹底沒用了,直接去掉
類似的,這條路只能用來從F走到D
但是從F走到D,從這邊走也是9分鐘,一樣快
所以這條路也沒用了,去掉它
現在看起來就簡單多了
再把線合併合併
這是6分鐘,這是5分鐘,這是12分鐘
這條是9分鐘,現在就容易挑出最快的線了
5分鐘比6分鐘快,9分鐘比12分鐘快
所以最快的路線是這一條
加一加,總共14分鐘
這個方法被稱爲擦線法
特別適合解決這類求最短路線的問題
來回顧一下,它的做法是
把能合併的路線合併成一條
對於兩點之間的線
如果有其它繞一圈的線能夠比它更快
就去掉這條線
現在問題來了
如果走每條路所需的時間是這樣
還是從AD到BD,最短要多久呢?
