还有实现算法可视化的实际问题。通常不能只是运行代码;必须有办法捕获它以便可视化(查看本文的源代码示例)。甚至可能需要与可视化交叉执行,这对于捕获递归算法的堆栈状态尤其具有挑战性。语言解析器如Esprima可以通过代码检测方便地实现算法可视化,将执行代码与可视化代码完全分离。 迷宫的生成 最后一个问题,我们会看下的是迷宫生成。本节中的所有算法生成二维矩形网格的生成树。这意味着没有循环,并且存在从左下角的根到迷宫中的每个其他单元的唯一路径。 我为如此深奥的主题而感到歉意。我不知道为什么这些算法是有用的,除了简单的游戏,可能是关于电气网络。但即使如此,它们从可视化视角看也很迷人,因为它们以非常不同的方式解决了同样的有高度约束的问题。 观看它们真有趣。 随机遍历算法初始化左下角的迷宫的第一个单元。该算法然后跟踪迷宫可以扩展的所有可能的方式(以红色标示)。在每个步骤,随机挑选这些可能的扩展中的一个,只要这不重新连接它与另一个部分的迷宫,该迷宫就会延伸扩展。 像Bridon的泊松盘采样算法一样,随机遍历保持前沿,并从边界中随机选择进行扩展。因此,两种算法似乎都像真菌一样有机地生长。 随机深度优先遍历遵循一个非常不同的模式: 不是每次都选择一个新的随机通道,该算法总是在随机方向上延伸最深的通道,一个最长的回到根的通道。因此,随机深度优先遍历分支,仅当当前路径是个死结时,进入迷宫的较早时的分支。要继续,它会回溯,直到它可以开始一个新的分支。这种蛇状的探索导致迷宫带有明显更少的分支和更长的蜿蜒通道。 Prim的算法构造最小生成树,具有加权边缘的图的生成树具有最低的总权重。 该算法可以用于通过随机初始化边缘权重来构建随机生成树: 在每个步骤中,Prim的算法使用连接到现有迷宫的最低加权边缘(潜在方向)扩展迷宫。如果该边缘将形成环路,则其被丢弃,然后考虑次最低加权边缘。 Prim的算法通常使用堆来实现,这是用于对元素进行优先级排序的有效数据结构。 当一个新的单元格加入迷宫时,连接的边缘(以红色标示)被添加到堆。尽管边以任意顺序添加,堆允许快速除去最低加权边。 最后,这是一个最不寻常的例子: Wilson的算法使用循环擦除随机游走来生成统一的生成树,是所有可能的生成树的无偏差样本。我们看到的其他迷宫生成算法缺乏这个美丽的数学属性。 该算法用任意起始单元初始化迷宫。然后,新的单元格被加入迷宫,启动随机游走(用红色标示)。继续随机游走,直到它重新连接到现有的迷宫(用白色标示)。然而,如果随机游走本身相交,则在随机游走继续之前擦除所得到的循环。 最初,算法看着可能令人沮丧地慢,因为早期随机游走不可能与小的现有迷宫重新连接。随着迷宫增长,随机游走变得更可能与迷宫碰撞,并且算法加速显著。 这四种迷宫生成算法的工作方式截然不同。然而,当动画结束时,所得到的迷宫彼此件难以区分。动画可用于显示算法如何工作,但无法显示生成的树结构。 一种显示结构,而不是过程的方法是用颜色填充迷宫: 颜色编码树深度——回到在左下角的根的路径的长度。随着越深入树,颜色标度循环;当一个深路径循环回邻近一个浅路径时,这偶尔会误导,但更高的对比度允许更好的局部结构的分化。(这不是一个传统的彩虹色标,名义上被认为有害,但立方体的彩虹具有改善的感知性能的能力。) 我们可以通过减去墙,进一步强调迷宫的结构,减少视觉噪声。下面的图中,每个像素表示通过迷宫的路径。如上所述,路径通过深度着色,随着时间的推移,颜色像潮水一样更深入迷宫。 (责任编辑:本港台直播) |