分类目录归档:算法

量子计算机能快速求解推箱子关卡吗?

  作者:杨超 本文地址: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 … 继续阅读

发表在 推箱子, 数学, 算法, 计算机 | 留下评论

用深度优先搜索(DFS)确定图的割点

本文地址: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)确定图的割点。

发表在 推箱子, 算法 | 一条评论