前言

最近读到一篇老外的文章《Visualizing Algorithms》，表示被里面各种算法炫酷的展示亮瞎了眼，一时冲动决定要将这篇文章翻译成中文，但是由于原文较长而且很文艺（我会告诉你们是我的英语太渣了么-_-），我打算以解读的形式来展示原文而并非翻译，如果感兴趣可以直接看原版。最后我会整合其他一些算法可视化的素材。好了，闲话不多说，Let’s begin~

本文译者为Resume，原文地址>>>

采样

首先我们来欣赏一下梵高同学的名画《星空》的一部分

关于光是怎样在人的视网膜上成像涉及到物理和生物的一些知识，这里我们不作讨论。但是其中有很重要的一个过程就是人眼把连续的光信号变成了离散的信号，并将其反馈给大脑。这个过程就称为采样。

采样在计算机图形学中扮演着非常重要的角色。即使是简单的调整图像大小也要用到采样。因此如何进行采样就显得十分重要，一方面要保证采样点要均匀分布，另一方面要避免采样点重复或产生规律（否则会产生混叠）。人的视网膜在采样上做的非常出色，看下面这张视网膜在显微镜下的图，图中的较大的视锥细胞探测颜色，较小的视杆细胞对弱光较为敏感。

这些细胞稠密且均匀的分布在视网膜上，而且它们之间的相对位置是无规律的。我们称之为泊松圆盘分布，因为任意细胞间的最小距离总是一定的。

但是构造一个泊松圆盘分布并不容易，我们先来看看米切尔最佳候选算法(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函数，然后依据返回值来确定待排元素的大小关系，返回值大于0表明第一个参数更大，返回值小于0表明第二个参数更大，返回值为0表明相等。上面的代码中定义了这样的一个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/黑盒——这是最简单的一类，就是只展示最终结果，我们看不到算法运行的过程，但是可以判断算法的正确性。用这种形式来展示更有助于我们比较不同算法之间结果。我们也可以将黑盒可视化与其他更深层次的分析方法结合起来，如前面洗牌算法部分用到的展示算法偏差方法。

• Level 1/灰盒——许多算法是逐渐生成最终结果的，通过观察算法过程中的一些关键步骤有助于我们理解算法的运行过程，而且我们也不需要引入什么新的名词概念，因为中间过程的结构和最终结果的结构是相似的。但是灰盒可视化也会引入更多问题，因为它并没有触及到算法的本质，大家往往搞不清为什么算法的中间过程是这样的。

• Level 2/白盒——要解答为什么算法是这样运行的我们就要用到白盒可视化了，它展示了算法的详细过程包括那些关键步骤。但是缺点也很明显——读者的负担太重，也就是你的思维可能会跟不上你的眼睛。同时，由于这种方法的中间过程与特定算法耦合的比较紧，也不适用于不同算法之间的比较。

当然想真正理解一个算法还是要阅读它的源码，算法可视只不过是辅助我们理解它的一个手段，而不是万能的银弹。

迷宫生成

我们讨论的最一个问题是迷宫生成，它可能不如前面的洗牌或者排序应用的广泛，但它比较有趣。本节所有算法生成的迷宫本质上是一个二维矩阵网络形式的生成树，也就是说其中没有回路，同时从左下角的起点到迷宫中的每一点都有且仅有一条路径。

迷宫生成的原理也比较简单，主要就是用到了生成树的一些算法，如果你对广度优先遍历、深度优先遍历、Kruskal算法、Prim算法这些不是很熟悉的话强烈建议你先去看看相应的资料。我们先来看看随机遍历

算法从左下角开始，每一步从所有可以扩展的点（图中的红点）中随机选择一个进行扩展。注意这个方法看起来可能和广度优先遍历类似，但它们的扩展规则是不一样的。广度优先遍历是严格按照每一层的顺序进行遍历，当前层所有结点遍历完之后才会对下一层进行遍历。

然后是随机深度优先遍历

刚才的算法不同，随机深度优先遍历总是从当前最长的路径的末端随机选择一个可扩展点进行扩展，如果出现回路或者抵达边界，那么就回溯到最近的一个可扩展分枝。这种算法生成的迷路分枝相对较少，路径也更长更曲折。

Prim算法用于构造一棵最小生成树，其边的权重在所有可能的生成树中是最小的。在迷宫生成中，我们可以通过随机指定边的权重，然后就可以使用Prim算法构造出迷宫了~

Prim算法每一步都从当前最小权重的边中挑一条添加当前迷宫上，如果形成了回路那么将其丢弃，再选一条权重最小的边。

最后我们再来看一个与众不同的迷宫生成算法

Wilson算法利用擦圈随机游动(loop-erased random walks)的方法生成了一个均匀随机迷宫，实际上就是一棵均匀支撑树(uniform spanning tree)，具体概念可以参考维基百科

Wilson算法每一轮随机指定一个起始点，然后开始随机游走（图中红色部分），直到其与当前迷宫（图中的白色部分）相交，此时将红色部分变为白色，然后开始下一轮随机游走。如果随机游走的过程中红色部分形成了回路，则将所形成回路擦除，然后继续随机游走。

不过Wilson算法看起来可能有些无聊，尤其是刚开始的时候，红色部分很难与白色部分相交。但是随着迷宫的规模慢慢扩大，白色部分越来越多时算法运行就较快了。

回顾我们介绍的四种迷宫生成算法，其原理各不相同，但是仅从结果来看，你可能很难分辨它们之间的区别，毕竟都是眼花缭乱的迷宫嘛~那么我们这里提供一种可以从结果看出迷宫结构（准确的说是生成树结构）的可视化方法——染色法。

先来看看随机遍历

我们用颜色来表示生成树的深度，这里用到的是一种类似彩虹颜色的层次表示方法，意会就好~

如果我们把黑色的墙去掉并降低视觉噪声，就可以更精细的观察迷宫的结构，如下图

图中的颜色形成了一层一层的同心圆结构，而且其路径结构也比较单一，没有特别蜿蜒曲折的路径，基本都是沿着一个很小的方向范围前进。当然这与算法的逻辑有很大关系。

随机深度优先遍历则完全不同

随机深度优先遍历的层次结构要比随机遍历深的多，因为是深度优先嘛，这里彩虹的七种颜色显然不够用了，我们已经完全无法看出结果的层次结构了，只是知道它很复杂。

再来看随机Prim算法

虽然看着有那么一点乱，但是还是可以大致看出其它们之间的层次结构。

最后来看Wilson算法

看起来是不是和随机Prim算法的结果有一点像？但是我们又被眼睛骗了，结果类似并不能说明两个算法类似，这再次印证了可视化并不是万能。

考虑到这些迷宫本质上都是生成树，所以我们干脆直接将把迷宫变成生成树的过程可视化，来看看Wilson算法生成的迷宫变成生成树是什么样子

将其和随机深度优先遍历比较一下

这里两棵生成树的结点数都为3239。用这种方式展示是不是非常直观呢？不过要注意，由于为了适应大小，我们把第二张图缩小了，其生成树的实际深度要远远高于Wilson算法。两张图的生成树的最大深度分别为310和832，而在更大规模的迷宫中，例如有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

个人比较喜欢最后一个~

光影效果

• 2D visibility
• 2D visibility and shadow effects

迷宫&寻路

• maze generation algorithms
• pathfinding
• polygonal map generation
• GPU-based path finding implementation

数学

• 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文件很大，而且录制出来的效果也不是很好。

所以我决定将原文中的动画原汁原味的保留下来，这个过程太辛酸，20多个动画的样式和脚本一个一个的复制和微调（为了适应我这个博客的主题），纯手工操作（本人比较菜，也只会这个方法了），不过仍有一些瑕疵——一些动画的位置有很小的偏移，不过不影响大家的观看啦~

文章较长，一半翻译一半是我自己的理解，难免有一些错误的地方，欢迎大家指出，在下面留言就好了~谢谢！

后记：本文译者为Resume。文中涉及了大量的FLASH，为了能转过来，我们把FLASH转化成了Gif，效果可能没有原来的好了，但仍然很惊艳，很喜欢。看原来的请到原文.

End.

转载请注明来自36大数据（36dsj.com)：36大数据 » 太惊艳了，原来算法可视化后可以这么艺术（多gif图)