《尋找最短的路徑》知識清單

《尋找最短的路徑》知識清單一、路徑的概念1、在我們的生活中有很多路徑，比如說從家到學(xué)校的路、從這個(gè)房間到另一個(gè)房間可以走的路線，這些都是路徑。2、在數(shù)學(xué)或者計(jì)算機(jī)里說的路徑，就是從一個(gè)點(diǎn)到另一個(gè)點(diǎn)可以走的路線。就像在一個(gè)迷宮里，小老鼠從入口到出口可以走很多條不同的路，這些不同的路就是不同的路徑。二、最短路徑的意義1、**節(jié)約資源**-在生活中，如果我們要送快遞，走最短的路徑就能節(jié)省時(shí)間和油錢。比如說快遞員要在一個(gè)小區(qū)里給好幾戶人家送快遞，規(guī)劃出最短的路徑，就能更快地把快遞送完，而且車的油也不會浪費(fèi)太多。2、**提高效率**-假如你在一個(gè)大商場里找一家店，按照最短路徑走就能更快找到，不會在商場里繞來繞去浪費(fèi)時(shí)間。三、尋找最短路徑的方法1、**直接觀察法**-有時(shí)候我們可以直接看出來哪條路最短。比如說在一個(gè)簡單的三角形形狀的公園里，從一個(gè)角到對角，如果有三條路，一條是沿著三角形的邊，另外兩條是彎彎繞繞的，那我們直接就能看出沿著邊的路是最短的。2、**列舉比較法**-當(dāng)有幾條不同的路徑可以選擇的時(shí)候，我們可以把每條路徑的長度算出來，然后比較。就像在一個(gè)方格圖里，從A點(diǎn)到B點(diǎn)有三條路，我們把每條路經(jīng)過的方格邊長加起來，比如說第一條路經(jīng)過5個(gè)方格邊長，第二條路經(jīng)過4個(gè)方格邊長，第三條路經(jīng)過6個(gè)方格邊長，那第二條路就是最短的。四、在算法中的最短路徑1、在計(jì)算機(jī)算法里，也有尋找最短路徑的問題。比如在一個(gè)由很多節(jié)點(diǎn)和連線組成的網(wǎng)絡(luò)里，要找到從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的最短路徑。2、計(jì)算機(jī)可以按照一定的規(guī)則，像我們前面說的列舉比較法那樣，把所有可能的路徑都找出來，然后比較它們的長度，找到最短的那個(gè)。不過計(jì)算機(jī)計(jì)算的速度非?？?，可以處理很復(fù)雜的網(wǎng)絡(luò)。五、相關(guān)的練習(xí)1、在一個(gè)正方形的場地里，從一個(gè)角到對角有兩條路徑，一條是沿著正方形的兩條邊走，另一條是從這個(gè)角直接斜著走到對角。哪條路徑短呢？2、有一個(gè)像棋盤一樣的方格圖，從左上角到右下角有好幾條彎彎曲曲的路，你怎么找出最短的路呢？答案：1、在正方形里，設(shè)正方形邊長為a，沿著兩條邊走的路徑長度是2a，根據(jù)勾股定理，斜著走的路徑長度是sqrt(2)a，因?yàn)閟qrt(2)大約是1.41