分类目录归档：算法

  作者：杨超 本文地址：http://sokoban.ws/blog/?p=3757 量子计算机常被大众媒体描述得十分神奇，甚至有科学家也添油加醋，如 David Deutsch 的 The Fabric of Reality 一书。用量子计算机能设计出快速求解推箱子关卡的算法吗？我在读了David Deutsch的书后，对此问题颇感兴趣。这个月，阅读了不少相关文献，找到了答案。答案是否定的。 首先，制造出通用的量子计算机仍然有极大的工程技术困难。 第二，再看看理论上，量子算法能干什么。最有名的量子算法就是Peter Shor的整数分解算法，这一算法使得基于大数分解比较困难的公钥加密算法岌岌可危。Shor的算法是1994年提出（Shor因此获得哥德尔奖Godel Prize），历史也没有太长。想要知道这一算法与传统计算机算法有何不同，可读Scott Aaronson的博文 《Shor, I’ll do it》。Scott Aaronson生于1981年，才36岁，是德州大学奥斯汀分校的教授，在理论计算机科学特别是计算复杂度理论方面有非常高的造诣。他博文中对Shor算法的核心解释得深入浅出。关键是整数分解还是有某种规律，量子算法恰恰能更好地利用这一规律，一定程度上避免了暴力穷举。 要注意的是，整数分解并非特别难的问题。在基于传统计算机（图灵机）的计算复杂度理论中，整数分解被认为不属于P，但也只是比P问题略难一些，介于P和NP-Complete之间，且更靠近P。因此，量子算法能快速分解大数也只是情理之中。 知道量子算法是怎么做的，能做什么，就更好地理解量子算法不能做什么。Scott Aaronson博客的站名banner位置有这么一段话，澄清大众对量子计算的误解： If you take just one piece of information from this blog: Quantum computers would … 继续阅读 →

本文地址：http://sokoban.ws/blog/?p=1000 之前的博文《推箱子游戏的一个箱子推动路径搜索算法 （二）》介绍了图论中寻找割点的算法在推箱子路径搜索中的应用。但是对用DFS寻找割点的原理说得不够清楚明白，本文的目的是试图进一步阐明这个算法，并把示意图画的更漂亮一些。 用DFS遍历一个图的所有顶点时，按访问顺序依次标号为1到n，称之为DFS数。顶点v的DFS数记作D(v)。并得到一棵DFS树（黑色边），称DFS树的边为树边（tree edge），其余的边（红色边）称为回头边（back edge）。如下图，图的边都按搜索过程中向外的方向定向，得到一个有向图。树边都是从DFS数小的顶点指向大的，回头边都是从DFS数大的顶点指向小的。   根据上面由深度优先搜索得到的有向图中，可定义每个顶点的低位数（lowpoint）：从该顶点出发，只用最多一条回头边，沿有向边能走到的顶点中DFS数最小值。顶点v的低位数记为L(v)。 低位数取值有两种情况：一是没用上回头边，则能走到的DFS数最小的的顶点就是该点自身，对应的路是一个顶点构成的平凡的路。此时L(v)=D(v)。二是用了回头边，则一定是最后一条边是回头边，走到一个DFS数更小的顶点。此时L(v)<=D(v)。 所以，一般地，总有L(v)<=D(v)。 有了这两个参数，就可以确定割点了：对根节点，即DFS数为1的顶点，其为割点当且仅当在DFS树中有两个或以上子节点；其余所有非根节点v是割点的充分必要条件是：v存在一个子节点u（在DFS树中的子节点）满足u的低位数大于等于v的DFS数，即L(u)>=D(v)。 下图标出的顶点的低位数（圈外数字，没标圈外数字的顶点低位数和DFS数相等），绿色顶点为割点。 注：若用 DFS的深度（depth）来替代上面算法中的DFS数，并用深度来计算低位数，则算法一样能有效地找出割点。 ［参考文献］ 1. Shimon Even, Graph Algorithms (2nd Edition). Cambridge University Press. 2012. p52-54 ［文中的图使用http://draw.io制作］

作者：杨超 本文地址：http://sokoban.ws/blog/?p=843 在博文《推箱子游戏的一个箱子推动路径搜索算法》中，我介绍了推箱子游戏如何用鼠标双击或拖放来进行推箱子操作。我知道的大概有十多个甚至二十多个推箱子软件都实现了这一功能。最近，anian告诉我，他通过用20603兄的《一箭十万》关卡测试了多个推箱子软件，发现《YSokoban》的速度最快，点击箱子，瞬间程序就给出了所有能被推到的格子的提示。而我编写的《SokoPlayer HTML5》则需要约2秒。经过和anian兄的讨论，我们改进了算法，大幅度提高的效率，使得《SokoPlayer HTML5》也能瞬间给出提示（约3毫秒）。下面简单介绍一下我们如何作出改进的。 在一个箱子推动路径搜索过程中，要反复判断人是否能从箱子的一侧自由移动（即不推动箱子情况下）到箱子的另一侧。这个不难判断，用简单的广度和深度优先搜索都能在线性时间内得到答案。但是箱子推动过程中，箱子位置在变化，要在不同的位置都作出判断。假设涉及到的格子有n个，每判断一次要O(n)时间，但箱子最多也可能出现在n个不同的格子，要做n次这样的判断，所以总的时间复杂度是O(n^2)。当关卡比较大时，如《一箭十万》是50×50的关卡，不算墙体，格子也上千，导致计算时间比较长。 后来，我们发现判断各种位置下人能否从箱子一侧自由移动到另一侧，可以用一个线性时间算法完成。这可以用图论里的割点（Cut Vertex）和块（Block）的理论和算法来帮助我们。举一个具体的例子来说明什么是割点和块。割点把关卡区域分割成不连通的小区域，称为块。下图关卡中，黄色格子为割点，共有10个块，分别用数字1到10标记。 我们若能把推箱子地图所对应的图中的割点和块全部标记出来，那么回答人能否从一侧移动到另一侧就很简单了。可以用这两步来判断：（1）先看箱子是否在一个 割点上。若不是割点，则人一定能从箱子一侧移动到任意的另一侧。若是割点，则还要进行第2步判断。（2）看该箱子这两侧的格子是否属于同一个块。若是，则 能移动。否则不行。 如上图中，若箱子在割点G6位置，人能从箱子左侧(F6)移动到上侧(G5)，因为属于同一个块3号。但不能从左侧(F6)移动到右侧(H6)。又若箱子在H4位置，由于H4不是割点，人可以从一侧移动到任意的另一侧。 标记图的所有割点和块，有一个线性时间算法。这是一个基于深度优先搜索（Depth First Search）的算法。在深度优先搜索过程中，对每个结点记录两个参数。一个是结点的深度depth，另一个是结点的低位数（low point）。一个结点v的低位数是这样计算的，取下面三者的最小值：（a）v自身的深度，（b）v的所有邻点（DFS树中的父结点除外）的深度，（c）DFS树中v的所有子结点的低位数。 在实现中，通常用递归函数来进行深度优先搜索，于是计算低位数可以这样处理。每发现一个新结点v时，把低位数初始为该结点的深度（即a）。对v的每个邻点，若是父结点，不管；若是父结点以外的已访问结点，且若该结点的深度较当前的低位数小，重新赋值v的低位数为该结点的深度（即b）；若是未访问结点，那么找到了一个子结点，于是递归调用搜索函数进行下一层搜索，返回时，若该子结点的低位数较小，则用它的更新v的低位数（即c）。 下面两幅图给出了一个例子，给出其DFS树（红色边），每个结点的深度和低位数。括号内为低位数，黄色结点为割点。 有了深度和低位数，如何判断割点和块呢？ 对于割点，判断条件很简单，若结点v有某一个子结点的低位数大于等于v的深度，则v是割点。 搜索的根结点比较特殊，它是割点的条件是在DFS树中有至少两个子结点。 对于块的标记可以按如下方法实现。首先注意到割点同时属于多个块，其他点则恰属于一个块。在深度搜索过程中，每从一个子结点返回，并且由子结点判断出其父结点v是割点时，就意味着找到一个新的块了。此时，把v及其所有子孙都标记为同一个块。标记之后，在DFS树中，把v的所有子孙删掉，但保留v。这样v的子孙就不会被重复标记。而v是割点，还可能属于另外一个块。 以上文的图为例。2(2)是个割点，从子结点3(2)返回是能判断出来，同时能发现一个块。而从子结点3(3)返回时也发现2(2)是割点，于是2(2)在另外一个块中也被标记了。 [后两个图用LibreOffice Draw制作] 2013年12月22日补充：关于寻找割点算法，可参看用深度优先搜索(DFS)确定图的割点。