太驚艷了，原來算法可視化后可以這么藝術（多gif圖)

前言

最近讀到一篇老外的文章 《Visualizing Algorithms》 ，表示被里面各種算法炫酷的展示亮瞎了眼，一時沖動決定要將這篇文章翻譯成中文，但是由于原文較長而且很文藝（我會告訴你們是我的英語太渣了么-_-）， 我打算以解讀的形式來展示原文而并非翻譯，如果感興趣可以直接看原版。最后我會整合其他一些算法可視化的素材。好了，閑話不多說，Let’s begin~

采樣

首先我們來欣賞一下梵高同學的名畫《星空》的一部分

關于光是怎樣在人的視網膜上成像涉及到物理和生物的一些知識，這里我們不作討論。但是其中有很重要的一個過程就是人眼把連續的光信號變成了離散的信號，并將其反饋給大腦。這個過程就稱為 采樣 。

采樣在計算機圖形學中扮演著非常重要的角色。即使是簡單的調整圖像大小也要用到采樣。因此如何進行采樣就顯得十分重要，一方面要保證采樣點要均勻 分布，另一方面要避免采樣點重復或產生規律（否則會產生混疊）。人的視網膜在采樣上做的非常出色，看下面這張視網膜在顯微鏡下的圖，圖中的較大的視錐細胞 探測顏色，較小的視桿細胞對弱光較為敏感。

這些細胞稠密且均勻的分布在視網膜上，而且它們之間的相對位置是無規律的。我們稱之為泊松圓盤分布，因為任意細胞間的最小距離總是一定的。

但是構造一個泊松圓盤分布并不容易，我們先來看看米切爾最佳候選算法(Mitchell’s best-candidate algorithm)，它是泊松圓盤分布的一個近似，方便起見，我們就稱之為best-candidate算法吧~

從圖上來看 best-candidate 算法形成的采樣點還算令人滿意，至少隨機性是不錯。不過缺點也很明顯，有的區域采樣點非常多（過采樣），而有的區域則較稀疏（欠采樣）。當然即使這樣也是相當不錯的，因為這個算法易于實現。

我們來看看這個算法的原理

best-candidate算法 ，顧名思義，是從一堆候選采樣點中選取一個最佳采樣點。首先，生成固定數量（上圖中為10）的候選采樣點，用灰色表示，每一個候選采樣點是在采樣區域隨機 生成的。然后尋找最佳候選采樣點，用紅色表示。什么是最佳候選采樣點呢？就是距離已固定的采樣點（黑色表示）最遠的那個點。這么說大家可能還是不太明白， 其實就是把已固定的采樣點整體看成一個集合，候選采樣點與這個集合中每一個元素都有一個距離，我們把最小的那個距離定義為該候選采樣點到已固定采樣點的距 離。

從圖上來說就是對每一個灰點（候選采樣點），尋找離它最近的黑點（已固定的采樣點），在它們之間劃一條線，線的長度就是它們的距離。紅點（最佳候 選采樣點）就是在當前所有灰點中這個距離最大的那個點。當這一輪結束這后，把紅點標為黑點（把最佳候選采樣點作為已固定的采樣點），然后進行下一輪的選 取，如此循環下去。

下面是實現代碼

其中 numCandidates 表示一次生成的候選采樣點個數， numCandidates 越小，算法運行速度越快。相反， numCandidates 越大，算法運行速度越慢，但是采樣質量越高。

distance函數 也非常簡單，如下所示

findClosest函數 返回距離當前灰點最近的黑點（距離當前候選采樣點最近的已固定采樣點）。我們可以用暴力搜索來實現，即遍歷所有黑點，計算當前灰點與它們之間的距離，找出最小值。當然也可以采用一些快速的搜索算法，如 四叉樹搜索算法 。暴力搜索簡單，但是時間復雜度太高。而四叉樹搜索算法需要一個前期建立四叉樹的過程。

下面我們來看看另一種 隨機采樣算法uniform random。uniform random算法 是最簡單的一種隨機采樣的實現，它的效果如下

uniform random算法 雖然簡單，但是它的結果實在有點慘不忍睹，采樣點重疊，過采樣，欠采樣等等。

那么除了通過采樣點的分布規律來鑒別采樣質量，還有沒有其他方法呢？這里我們可以通過取距離采樣點最近的顏色并對采樣點所在色塊進行著色的方法，也可以使用沃羅諾伊圖

先來看看在 uniform random算法 生成的6667個采樣點下的《星空》是什么樣的

效果果然很一般，采樣點分布不均導致色塊大小不一、細節丟失嚴重等一系列問題。左下角還有一些粉紅色的色塊，而原作中是沒有這種顏色的。

再來看看 best-candidate算法 采樣后的《星空》

盡管仍有一些細節丟失等問題，但明顯要比上一幅效果要好。

我們也可以用沃羅諾伊圖更直觀的衡量采樣質量，通過對每個色塊的大小對其進行著色，色塊越大顏色越深，色塊越小顏色越淺。最佳的采樣模式應該有幾乎統一的著色，同時又保證不規律的采樣點分布。下圖是 uniform random 的效果

色塊之間的差別非常大，原因不再贅述。

best-candidate 的效果如下：

顏色明顯均勻多了~

那么有沒有什么算法能比 best-candidate算法 效果更好呢？當然有了，這就是我們下面要討論的Bridson泊松圓盤采樣算法，這次可不是近似了哦~先來看看 Poisson-disc算法 的效果

看起來是不是非常均勻和舒服？它與前面兩個算法最大不同在于，它是 充分利用現有采樣點逐步生成新的采樣點 ，而不是在整個采樣區域隨機生成新的采樣點。同時也注意到，任意兩個采樣點的最小距離都是一定，沒有特別靠近的兩個點（正如泊松圓盤分布所定義的那樣），這些都是由算法的執行過程嚴格保證的。來看看算法的執行過程

我們用紅點表示活躍采樣點，在每一輪的循環中從所有活躍采樣點中隨機選取一個點，然后以該點為圓心，分別以r和2r為半徑作兩個同心圓，其中r為 兩個采樣點之間所允許的最小間距。然后我們在r與2r之間的環形區域隨機生成一些候選采樣點（白點），接下來的步驟就是從這些候選采樣點中篩選出一個滿足 條件的采樣點了。

注意到圖中的灰色區域，它們是由已固定的采樣點（包括紅點和黑點）為圓心，r為半徑作圓所形成的區域，我們可以稱之為“禁區”。如果候選采樣點落 在灰色區域，那么表明它一定與某個已固定的采樣點的距離不足r，這是不允許的，因此可以將這樣的候選采樣點排除掉。當我們找到一個沒有落在灰色區域的候選 采樣點之后，便把它標為紅點作為一個新的活躍采樣點，原來的活躍采樣點不變。如果生成的所有候選采樣點都落在灰色區域內，那么就認為在r到2r的區域內不 存在滿足最小距離為r的點（當然實際情況不一定如此），然后把作為圓心的活躍采樣點標為即不活躍采樣點（從紅點變成黑點）。當所有點都變成黑點之后，算法 結束。

下圖是 Poisson-disc算法 的沃羅諾伊圖

顏色更加勻稱了是不是？ 再看看 Poisson-disc 算法下的星空

美不勝收！

洗牌

正如撲克的洗牌一樣，洗牌算法是對一組元素的隨機重排列的過程。一個好的洗牌算法應該是無偏的，即每一種排列都是等可能的。

下面我們來看看 Fisher–Yates洗牌算法 ，它可是最優洗牌算法哦~它不僅是無偏的，而且時間復雜度是O(n)，空間復雜度是O(1)，同時也非常容易實現，代碼如下

算法的過程見下圖

圖中的每一條線代表一個數字，線的傾斜程度代表數的大小，線越往左傾斜表明數越小，反之越往右傾斜表明數越大。

從圖中可以明顯看出，該算法把數組劃分為兩個部分，右半邊是已洗牌區域（用黑線表示），左半邊是待洗牌區域（用灰線表示）。每一步從左邊的待洗牌區域隨機選擇一個元素并將其移動到右側，如此循環下去直到待洗牌區域無數組元素，算法終止。

Fisher–Yates洗牌算法是一個簡單而且正確的算法，但并不是每一個簡單的洗牌算法都一定是正確的。我們來看看下面這個錯誤的洗牌算法

我們先來解釋一下代碼， array.sort() 表示對數組進行排序，一般情況下是按照數組中元素的大小（例如整形）或者是按照字典序列（例如字符）來進行排序。當然我們也可以自定義規則，也就是自定義一個 comparator函數 ，然后依據返回值來確定待排元素的大小關系，返回值大于表明第一個參數更大，返回值小于表明第二個參數更大，返回值為表明相等。上面的代碼中定義了這樣的一個 comparator函數 ，從數組中隨機取兩個元素a和b，然后隨機返回 [-0.5,0.5) 之間的一個值，也就是說元素a和b之間的大小關系是隨機的，所以它們之間的順序也是隨機的，這樣遍歷完整個數組后所有元素的順序都是隨機的。

但真的是這樣的嗎？當然不是，這個算法的有著非常嚴重的缺陷。首先我們要知道，任意兩個元素之間的順序隨機性并不能保證整體的順序隨機性。同時，一個比較器應該滿足 傳遞性 ，如果有a>b且b>c，那么就有 a>c 。而上述代碼中的隨機比較器破壞了這個特性，導致 array.sort() 的行為是不確定的，所以最后的結果也是不可靠的。

那么它的結果到底如何呢？來看看下面這張圖

乍一看好像也是隨機的啊，但是我們要注意有些東西人眼看起來是隨機的，但實際上確并非隨機的。

為了更直觀的衡量算法的質量，我們換一種方式來進行展示~

一個好的洗牌算法應該保證無偏性，也就是說保證每個元素在洗牌結束后出現在數組的任何位置都是等可能的，概率為 1/n ，其中 n 為數組元素個數。當然準確的計算這個概率有點困難（依賴具體的算法），但是我們可以從統計意義上來計算這個概率。也就是把洗牌算法運行幾千次，統計原先在位置i的元素在洗牌后出現在位置j的次數，然后畫在一張圖上，如下

上圖中列表示元素在洗牌前的位置，行表示元素在洗牌后的位置。顏色表示概率，綠色表示正偏，也就是其出現次數高于預期。紅色表示負偏，也就是其出現次數低于預期。

上圖是在 Chrome 瀏覽器下的結果，只能說很一般。注意到在對角線偏下的位置有嚴重的正偏現象，表明這個算法很容易將一個在位置 i元素在洗牌后放置到i+1或者i+2的位置上 去，同時也注意到在數組第一個、中間的和最后一個元素也有很多正偏和負偏現象，這個可能和 Chrome 瀏覽器的具體實現有關。

而 Fisher–Yates 洗牌算法的結果就要好很多

圖中沒有明顯的規律可循，個別偏差也是因為我們使用的是統計的方法，與算法本身無關。

另外值得一提的一點是，隨機比較器( random comparator )洗牌算法的結果與瀏覽器的實現也有很大關系。剛才Chrome瀏覽器的結果已經很糟糕了，我們再來看看 Firefox 下的結果

只能說慘不忍睹！當然這并不意味著 Chrome比Firefox 要強，只能說明我們所使用的算法是有問題的，導致其結果是不確定的。而瀏覽器內部的不同實現更直觀的把這個問題暴露出來了。

排序

排序呢大家都很熟悉了，我們先來看看耳熟能詳的快速排序

快排的原理這里也不多說了，就是通過在當前待排元素中取一個基準，然后將比該基準小的元素放置其左側，比基準大的元素放置在其右側，然后遞歸進行下去。

以下是實現代碼

當然快排算法有很多版本，上面演示的那個版本是最簡單也是最慢的一種，主要用于教學演示，在實際應用中有很多其他優化的方法。例如三數取中 （median-of-three）法，即取三個元素先進行排序，將中間數作為基準，一般是取左端、右端和中間三個數，也可以隨機抽取。這樣做的好處是得 到的基準有很大可能會更接近真正的中間數，劃分出來的兩個部分大小會更加均衡，遞歸的層數會更少，可以提高算法的效率。另一種優化方法是在當遞歸進行到一 定程度時，也就是當數組元素比較少的時候采用插入排序而不是繼續遞歸下去。

用動畫來展示算法雖然有趣直觀，但有的時候卻可能讓我們忽視掉一些細節，而且如果動畫太快的話思維就跟不上了。所以我們可以用一種類似漫畫的方法來進行展示，突出算法中的關鍵步驟。

注意這里左右兩個部分的快速排序是并行執行的，紅線表示當前劃分所使用的基準，在下一層中使用過的基準會標成灰色。

還有另外一種展示方法，用色帶來表示元素。色帶顏色越深表示元素越大，色帶顏色越淺表示元素越小。下面我們用這種方法來展示上述快排算法

至此我們演示了三種可視化快速排序算法的方法，動畫展示、分步展示、色帶展示。這三種方法各有各的優點和缺點，相信大家心里也有數。

看完了快排算法的可視化，我們再來看看歸并排序

上面是歸并排序的代碼，效果如下圖

與快速排序不同，歸并排序需要用到額外的存儲空間，所以在動畫中我們用到了兩行來進行演示。歸并排序的原理也很好理解，就是把兩個相鄰的有序表歸并為一個新的有序表。

關鍵步驟如下

不過我們也不能一味的追求炫麗的視覺效果，因為我們的最終目的是學習和理解算法的本質，而不是僅僅局限在一個數據集上。

這里我們可以通過數據最終的展示形式將算法可視化劃分為三個層次：

• Level 0/黑盒——這是最簡單的一類，就是只展示最終結果，我們看不到算法運行的過程，但是可以判斷算法的正確性。用這種形式來展示更有助于我們比較不同算法之 間結果。我們也可以將黑盒可視化與其他更深層次的分析方法結合起來，如前面洗牌算法部分用到的展示算法偏差方法。
</ul>

• Level 1/灰盒——許多算法是逐漸生成最終結果的，通過觀察算法過程中的一些關鍵步驟有助于我們理解算法的運行過程，而且我們也不需要引入什么新的名詞概念，因 為中間過程的結構和最終結果的結構是相似的。但是灰盒可視化也會引入更多問題，因為它并沒有觸及到算法的本質，大家往往搞不清為什么算法的中間過程是這樣 的。
</ul>

• Level 2/白盒——要解答為什么算法是這樣運行的我們就要用到白盒可視化了，它展示了算法的詳細過程包括那些關鍵步驟。但是缺點也很明顯——讀者的負擔太重，也 就是你的思維可能會跟不上你的眼睛。同時，由于這種方法的中間過程與特定算法耦合的比較緊，也不適用于不同算法之間的比較。
</ul>

當然想真正理解一個算法還是要閱讀它的源碼，算法可視只不過是輔助我們理解它的一個手段，而不是萬能的銀彈。

迷宮生成

我們討論的最一個問題是迷宮生成，它可能不如前面的洗牌或者排序應用的廣泛，但它比較有趣。本節所有算法生成的迷宮本質上是一個二維矩陣網絡形式的生成樹，也就是說其中沒有回路，同時從左下角的起點到迷宮中的每一點都有且僅有一條路徑。

迷宮生成的原理也比較簡單，主要就是用到了生成樹的一些算法，如果你對廣度優先遍歷、深度優先遍歷、Kruskal算法、Prim算法這些不是很熟悉的話強烈建議你先去看看相應的資料。我們先來看看隨機遍歷



算法從左下角開始，每一步從所有可以擴展的點（圖中的紅點）中隨機選擇一個進行擴展。注意這個方法看起來可能和廣度優先遍歷類似，但它們的擴展規則是不一樣的。廣度優先遍歷是嚴格按照每一層的順序進行遍歷，當前層所有結點遍歷完之后才會對下一層進行遍歷。

然后是隨機深度優先遍歷



剛才的算法不同，隨機深度優先遍歷總是從當前最長的路徑的末端隨機選擇一個可擴展點進行擴展，如果出現回路或者抵達邊界，那么就回溯到最近的一個可擴展分枝。這種算法生成的迷路分枝相對較少，路徑也更長更曲折。

Prim 算法用于構造一棵最小生成樹，其邊的權重在所有可能的生成樹中是最小的。在迷宮生成中，我們可以通過隨機指定邊的權重，然后就可以使用 Prim 算法構造出迷宮了~



Prim 算法每一步都從當前最小權重的邊中挑一條添加當前迷宮上，如果形成了回路那么將其丟棄，再選一條權重最小的邊。

最后我們再來看一個與眾不同的迷宮生成算法



Wilson算法 利用擦圈隨機游動(loop-erased random walks)的方法生成了一個均勻隨機迷宮，實際上就是一棵均勻支撐樹(uniform spanning tree)，具體概念可以參考 維基百科

Wilson算法 每一輪隨機指定一個起始點，然后開始隨機游走（圖中紅色部分），直到其與當前迷宮（圖中的白色部分）相交，此時將紅色部分變為白色，然后開始下一輪隨機游走。如果隨機游走的過程中紅色部分形成了回路，則將所形成回路擦除，然后繼續隨機游走。

不過 Wilson算 法看起來可能有些無聊，尤其是剛開始的時候，紅色部分很難與白色部分相交。但是隨著迷宮的規模慢慢擴大，白色部分越來越多時算法運行就較快了。

回顧我們介紹的四種迷宮生成算法，其原理各不相同，但是僅從結果來看，你可能很難分辨它們之間的區別，畢竟都是眼花繚亂的迷宮嘛~那么我們這里提供一種可以從結果看出迷宮結構（準確的說是生成樹結構）的可視化方法——染色法。

先來看看隨機遍歷



我們用顏色來表示生成樹的深度，這里用到的是一種類似彩虹顏色的層次表示方法，意會就好~

如果我們把黑色的墻去掉并降低視覺噪聲，就可以更精細的觀察迷宮的結構，如下圖



圖中的顏色形成了一層一層的同心圓結構，而且其路徑結構也比較單一，沒有特別蜿蜒曲折的路徑，基本都是沿著一個很小的方向范圍前進。當然這與算法的邏輯有很大關系。

隨機深度優先遍歷則完全不同



隨機深度優先遍歷的層次結構要比隨機遍歷深的多，因為是深度優先嘛，這里彩虹的七種顏色顯然不夠用了，我們已經完全無法看出結果的層次結構了，只是知道它很復雜。

再來看隨機 Prim算法



雖然看著有那么一點亂，但是還是可以大致看出其它們之間的層次結構。

最后來看 Wilson算法



看起來是不是和隨機 Prim算法 的結果有一點像？但是我們又被眼睛騙了，結果類似并不能說明兩個算法類似，這再次印證了可視化并不是萬能。

考慮到這些迷宮本質上都是生成樹，所以我們干脆直接將把迷宮變成生成樹的過程可視化，來看看 Wilson算法 生成的迷宮變成生成樹是什么樣子



將其和隨機深度優先遍歷比較一下



這里兩棵生成樹的。用這種方式展示是不是非常直觀呢？不過要注意，由于為了適應大小，我們把第二張圖縮小了，其生成樹的實際深度要遠遠高于 Wilson算法 。兩張圖的生成樹的最大深度分別為 和 ，而在更大規模的迷宮中，例如有480,000個結點的迷宮 ，兩棵生成樹最大深度的有可能會相差10~20倍！所以使用隨機深度優先遍歷要謹慎啊~

小結&補充

OK，到這里原文的主要內容就結束了，后面就是一些心靈雞湯部分了（-_-||），什么 use vision to think ，用視覺思考？好吧，如果你感興趣可以去看原文~

這里還是談談我的感受吧，回想當初學習數據結構和算法的主要方法就是啃代碼，極其枯燥。而且我們的教學形式很久都沒有變化了，現在的學生們估計還是要硬生生的去理解代碼（-_-），不過這篇《 Visualizing Algorithms 》卻給我們提供了一個很好的思路，那就是把算法變得直觀、有趣，從不同角度和層面去剖析一個算法。

當然這并不是一件容易的事情，首先我們對算法的理解需要更加深入和透徹，否則不可能想出那些神奇的展現方式。其次就是我們的美工水平和前端編程能力，我看了一下原作者網頁中可視化實現的一些代碼，涉及到 CSS、javascript 和 HTML5 （尤其是 svg 標簽和 canvas 標簽的使用）等很多內容，這些沒有深厚的功底是做不到的。

我這里再把原文中列出的一些其他算法可視化方面的資源放在這里

排序

• Aldo Cortesi’s sorting visualizations
• sorting-algorithms.com
• sorting.at
• Sorting Visualizer
</ul>

個人比較喜歡最后一個~

光影效果

• 2D visibility
• 2D visibility and shadow effects
</ul>

迷宮&尋路

• maze generation algorithms
• pathfinding
• polygonal map generation
• GPU-based path finding implementation
</ul>

數學

• Lloyd’s Relaxation
• Coalescing Soap Bubbles
• Biham-Middleton-Levine Traffic Model
• Collatz Graph
• Random Points on a Sphere
• Bloom Filters
• Animated Bézier Curves
• Animated Trigonometry
• Proof of Pythagoras’ Theorem
• Morley’s Trisector Theorem
• Fourier series
• Simpson’s paradox
• central limit theorem
• conditional probabilities
• topology inference
</ul>

不得不承認老外比我們領先太多了，不僅僅是技術上的領先，更多的是想法和思維上的領先。記得前一段時間刷微博的時候看到羅馬尼亞人民是怎樣教算法的，他們的計算機學院編排了排序算法的教學舞蹈~詳情請戳 讓程序員抓狂的排序算法教學視頻

說了這么多，如果你也想學習算法可視化，可以從這個用 C# 實現的 排序算法可視化 開始，有源碼哦~它的效果也挺不錯的，大概是這個樣子

冒泡排序



插入排序



快速排序



后記

折騰這篇文章真的太辛苦了，首先原文實在是太長了，其次是那些動畫和圖片，本來想把那些動畫用GIF錄制器錄制下來，但是發現有些動畫實在太長，這樣會導致GIF文件很大，而且錄制出來的效果也不是很好。

文章較長，一半翻譯一半是我自己的理解，難免有一些錯誤的地方，歡迎大家指出，在下面留言就好了~謝謝！

后記：本文譯者為Resume。文中涉及了大量的FLASH，為了能轉過來，我們把FLASH轉化成了Gif，效果可能原來的好了，但仍然很驚艷，很喜歡。看原來的請到 原文 .

End.

</div>