太驚豔了,原來算法可視化後可以這麼藝術

原標題：太驚豔了，原來算法可視化後可以這麼藝術

採樣

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

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

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

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

但是構造一個泊松圓盤分布並不容易，我們先來看看米切爾最佳候選算法(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）法，即取三個元素先進行排序，將中間數作為基準，一般是取左端、右端和中間三個數，也可以隨機抽取。這樣做的好處是得 到的基準有很大可能會更接近真正的中間數，劃分出來的兩個部分大小會更加均衡，遞歸的層數會更少，可以提高算法的效率。另一種優化方法是在當遞歸進行到一 定程度時，也就是當數組元素比較少的時候採用插入排序而不是繼續遞歸下去。

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

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

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

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

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

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

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

關鍵步驟如下

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

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

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

迷宮生成

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

迷宮生成的原理也比較簡單，主要就是用到了生成樹的一些算法，如果你對廣度優先遍歷、深度優先遍歷、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、java 和 HTML5 （尤其是 svg 標籤和 canvas 標籤的使用）等很多內容，這些沒有深厚的功底是做不到的。

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

排序

個人比較喜歡最後一個~

光影效果

迷宮&尋路

數學

• 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

  （以上網站均可通過搜索進入）

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

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

冒泡排序

插入排序

快速排序

後記

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

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

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

本文轉載自猿性畢露（ID：yuanxingbl）

作者| 圖文來自網絡、如涉及版權問題，請聯繫我們以便處理。文章內容純屬作者個人觀點，不代表本網觀點。

編輯| 老貓返回搜狐，查看更多

責任編輯：