摘要

1. 似乎大部分算法講解缺少對(duì)迪杰斯特拉算法的形象化和感性化認(rèn)識(shí)。

2. 我對(duì)迪杰斯特拉算法的感性認(rèn)識(shí)

3. 我對(duì)迪杰斯特拉和普里姆算法的區(qū)別的簡(jiǎn)單感性概述

4. 對(duì)總結(jié)了一個(gè)學(xué)習(xí)算法的方法。

流水賬一樣的記錄

以下一些算法細(xì)節(jié)上的理解僅僅是我個(gè)人的理解。沒(méi)有做好插圖，很潦草。若有讀者，看不懂也不必看懂。這個(gè)文章是寫(xiě)給未來(lái)的我自己。這里只是像記事本一樣做個(gè)記錄，做個(gè)記憶保存。

2022年8月25日。我又又又又把有向圖的最短路徑算法給忘了。

我為什么老是忘了這個(gè)東西啊？我想了想，我覺(jué)得是因?yàn)楫?dāng)時(shí)在學(xué)這個(gè)算法和寫(xiě)這個(gè)算法的時(shí)候沒(méi)有形成感性層面的直觀的認(rèn)識(shí)和理解。

看的王道的視頻，直接給出了三個(gè)數(shù)組，給了一個(gè)例子，然后開(kāi)始講。當(dāng)時(shí)好像是暫停又暫停著聽(tīng)懂了，也照著講的內(nèi)容寫(xiě)出來(lái)了代碼。甚至當(dāng)時(shí)還用js和canvas繪圖做出了動(dòng)態(tài)的效果。然而我沒(méi)有形成感性的直觀的理解。

案例中帶權(quán)有向圖一個(gè)阻礙直觀可視化的最大的問(wèn)題，其實(shí)是邊的權(quán)值應(yīng)該表示節(jié)點(diǎn)之間距離的遠(yuǎn)近，然而例圖不能夠體現(xiàn)出來(lái)，只是僅僅的標(biāo)了個(gè)數(shù)字。其實(shí)可以表達(dá)出來(lái)的，把一些線畫(huà)長(zhǎng)一些，一些線畫(huà)短一些就可以了。但是發(fā)現(xiàn)王道里的這個(gè)例子還是不利于直觀化。想要把圖直觀化還得把一些直線畫(huà)成彎彎曲曲的用來(lái)表示它很長(zhǎng)。不過(guò)湊活還能看。

我覺(jué)得沒(méi)必要一上來(lái)就懟三個(gè)數(shù)組出來(lái)了。那是第二階段的理解。第一階段應(yīng)該是感性認(rèn)識(shí)的學(xué)習(xí)。

經(jīng)過(guò)一番寫(xiě)寫(xiě)畫(huà)畫(huà)發(fā)現(xiàn)，三個(gè)數(shù)組的信息可以直接在圖的節(jié)點(diǎn)上標(biāo)注。也很直觀。標(biāo)數(shù)字，給節(jié)點(diǎn)畫(huà)紅圈，以及涂紅。就很直觀了。

迪杰斯特拉最短路徑是一種貪心思想。它總是選擇當(dāng)前能拓展出去的，離最開(kāi)始節(jié)點(diǎn)最近的待擴(kuò)散節(jié)點(diǎn)開(kāi)始往外繼續(xù)拓展探索。如果遇到了已經(jīng)拓展出去的節(jié)點(diǎn)，就看看是不是現(xiàn)在能“抄近路”，修改那個(gè)節(jié)點(diǎn)的“上一個(gè)節(jié)點(diǎn)”信息。拓展完了還把自己給“鎖住”，表示自己這個(gè)已經(jīng)是最短路徑了。

最后的path數(shù)組其實(shí)就是這從最開(kāi)始的點(diǎn)，在這個(gè)圖上，一步一步拓展出去形成的一個(gè)樹(shù)。

這個(gè)紅色的樹(shù)形狀的物質(zhì)在拓展擴(kuò)散出去的時(shí)候呢，總是從最近處地方開(kāi)始繼續(xù)拓展擴(kuò)散。一碰到自己這個(gè)物質(zhì)本身，就把碰到的那個(gè)地方看能不能再拽短。最終直到擴(kuò)散完畢。

這個(gè)跟最小生成樹(shù)好像還有點(diǎn)像，都是把圖生成成一棵樹(shù)。但是生成樹(shù)是不唯一的。生成樹(shù)的普里姆算法是可以隨便從一個(gè)節(jié)點(diǎn)開(kāi)始選的，但是這個(gè)迪杰斯特拉算法是從指定的節(jié)點(diǎn)開(kāi)始，計(jì)算從它到所有節(jié)點(diǎn)的最短路徑的。他們倒是都用了貪心思想，總是選擇最小的。

普里姆：先隨便選一個(gè)節(jié)點(diǎn)，然后也是開(kāi)始擴(kuò)張，擴(kuò)張的時(shí)候選擇距離自己這個(gè)生成樹(shù)輪廓最近的，然后納入生成樹(shù)。迪杰斯特拉是不停的選擇距離最開(kāi)始的那個(gè)節(jié)點(diǎn)最近的然后開(kāi)始擴(kuò)。

但普里姆在考研的數(shù)據(jù)結(jié)構(gòu)里沒(méi)有給出能寫(xiě)出代碼的要求，只需要理解和手推就行了。我覺(jué)得這就算是第一階段的算法理解程度，問(wèn)題在于第一階段的程度不能很好的體會(huì)到時(shí)間復(fù)雜度。書(shū)上也沒(méi)給出代碼。居然還是像集合論一樣的偽代碼。還是克魯斯卡爾算法更好理解一些。直接給所有邊放到數(shù)組里排個(gè)序。然后每個(gè)邊取出來(lái)兩端的端點(diǎn)兩兩連通就可以了。像并查集一樣。如果本來(lái)就是連通的了就pass。所以時(shí)間復(fù)雜度很容易就看出來(lái)是NlogN級(jí)別，因?yàn)槭桥判?。后面的并查集一樣的檢測(cè)連通是N級(jí)別的。所以省略了。普里姆算法怎么看都像是超過(guò)N2的。

普里姆算法現(xiàn)在只是停留在第一階段了。休息一下，先學(xué)更重要的，回頭再來(lái)關(guān)注他怎么實(shí)現(xiàn)。

對(duì)學(xué)習(xí)算法的方法總結(jié)

第一階段：想法直觀化，可以破壞程序性表達(dá)。做到感性認(rèn)識(shí)，和本質(zhì)理解。腦海中盡力想象樣子。

第二階段：從寫(xiě)代碼的角度學(xué)習(xí)，想法把第一階段腦海中的東西轉(zhuǎn)化成用代碼怎么寫(xiě)，怎么轉(zhuǎn)化成數(shù)組，字典，比如快排的partion，直觀想很簡(jiǎn)單，但代碼寫(xiě)還沒(méi)那么簡(jiǎn)單。比如kmp的next數(shù)組，感性認(rèn)識(shí)（手工求）和代碼寫(xiě)甚至就是兩種方法了。

如果沒(méi)有第一階段，半年或者一年后基本就又忘了具體怎么做了。如果只有第一階段，就不知道怎么寫(xiě)代碼，也不容易很快分析出復(fù)雜度。兩種階段結(jié)合在一起才能形成完整、深刻的認(rèn)識(shí)和理解。