最小编辑距离 算法原理

问题

最小编辑距离 Minimum Edit Distance
关于两个字符串s1,s2的差别,可以通过计算他们的最小编辑距离来决定。
设A、B为两个字符串,狭义的编辑距离定义为把A转换成B需要的最少删除(删除A中一个字符)、插入(在A中插入一个字符)和替换(把A中的某个字符替换成另一个字符)的次数,用ED(A,B)来表示。直观来说,两个串互相转换需要经过的步骤越多,差异越大。
例如 s1 = “12433” 和 s2 = “1233”;
则可以通过在s2中间插入4得到12433与s1一致。
即 d(s1,s2) = 1 (进行了一次插入操作)

性质

计算两个字符串s1+c1, s2+c2的编辑距离有这样的性质:

1.   d(s1,"") = d("",s1) = |s1|
     d("c1","c2") = c1 == c2 ? 0 : 1;
2.   d(s1+c1,s2+c2) = min(  d(s1,s2)+ c1==c2 ? 0 : 1 ,
                            1 + d(s1+c1,s2),
                            1 + d(s1,s2+c2)  );

第一个性质是显然的。
第二个性质: 由于我们定义的三个操作来作为编辑距离的一种衡量方法,于是对c1,c2可能的操作只有:

1.  把c1变成c2
2.  s1+c1后删除c1              d = (1 + d(s1, s2 + c2))
3.  s1+c1后插入c2              d = (1 + d(s1 + c1, s2))

对于2和3的操作可以等价于:
_2.   s2+c2后添加c1        d = (1 + d(s1, s2 + c2))
_3.   s2+c2后删除c2        d = (1 + d(s1 + c1, s2))

因此可以得到计算编辑距离的性质2。

复杂度分析

从上面性质2可以看出计算过程呈现这样的一种结构(假设各个层用当前计算的串长度标记,并假设两个串长度都为 n )
可以看到,该问题的复杂度为指数级别 3 的 n 次方,对于较长的串,时间上是无法让人忍受的。
分析: 在上面的结构中,我们发现多次出现了 (n-1,n-1), (n-1,n-2)……。换句话说该结构具有重叠子问题。再加上前面性质2所具有的最优子结构。符合动态规划算法基本要素。因此可以使用动态规划算法把复杂度降低到多项式级别。

动态规划求解

首先为了避免重复计算子问题,添加两个辅助数组。
一. 保存子问题结果。
M[ |s1| ,|s2| ] , 其中M[ i , j ] 表示子串 s1(0->i) 与 s2(0->j) 的编辑距离
二. 保存字符之间的编辑距离.
E[ |s1|, |s2| ] , 其中 E[ i, j ] = s1[i] = s2[j] ? 0 : 1
三. 新的计算表达式
根据性质1得到

M[ 0,0] = 0;
M[ s1i, 0 ] = |s1i|;
M[ 0, s2j ] = |s2j|;

根据性质2得到

M[ i, j ]   = min(  m[i-1,j-1] + E[ i, j ] ,
                    1 + m[i, j-1] ,
                    1 + m[i-1, j]  );

复杂度
从新的计算式看出,计算过程为

      i=1 -> |s1|
             j=1 -> |s2|
                    M[i][j] = ……

因此复杂度为 O( |s1| * |s2| ) ,如果假设他们的长度都为n,则复杂度为 O(n^2)

改进

当s[i]和s[j]相等时,代价为0,必然为最小值,所以首先判断两字符是否相等,若相等则直接判定M[i][j]=M[i-1][j-1],判断下个。这样可以省很多计算。

工具宏:直接用一个宏来完成“求取三者最小值”的功能。不同于递归,宏定义消耗很小,完全可以放心使用。

#ifndef _MIN(xyz)
#define _MIN(xyz) ((x<y)?((x<z)?x:z):((y<z)?y:z))
#endif // _MIN(xyz)

[转]如何用Python写一个贪吃蛇AI

作者:Hawstein
出处:http://hawstein.com/posts/snake-ai.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

前言

这两天在网上看到一张让人涨姿势的图片,图片中展示的是贪吃蛇游戏, 估计大部分人都玩过。但如果仅仅是贪吃蛇游戏,那么它就没有什么让人涨姿势的地方了。 问题的关键在于,图片中的贪吃蛇真的很贪吃XD,它把矩形中出现的食物吃了个遍, 然后华丽丽地把整个矩形填满,真心是看得赏心悦目。作为一个CSer, 第一个想到的是,这东西是写程序实现的(因为,一般人干不出这事。 果断是要让程序来干的)第二个想到的是,写程序该如何实现,该用什么算法? 既然开始想了,就开始做。因为Talk is cheap,要show me the code才行。 (从耗子叔那学来的)

开始之前,让我们再欣赏一下那只让人涨姿势的贪吃蛇吧:( 如果下面的动态图片浏览效果不佳的话,可以右键保存下来查看)

语言选择

Life is short, use python! 所以,根本就没多想,直接上python。

最初版本

先让你的程序跑起来

首先,我们第一件要做的就是先不要去分析这个问题。 你好歹先写个能运行起来的贪吃蛇游戏,然后再去想AI部分。这个应该很简单, cc++也就百来行代码(如果我没记错的话。不弄复杂界面,直接在控制台下跑), python就更简单了,去掉注释和空行,5、60行代码就搞定了。而且,最最关键的, 这个东西网上肯定写滥了,你没有必要重复造轮子, 去弄一份来按照你的意愿改造一下就行了。

简单版本

我觉得直接写perfect版本不是什么好路子。因为perfect版本往往要考虑很多东西, 直接上来就写这个一般是bug百出的。所以, 一开始我的目标仅仅是让程序去控制贪吃蛇运动,让它去吃食物,仅此而已。 现在让我们来陈述一下最初的问题:

在一个矩形中,每一时刻有一个食物,贪吃蛇要在不撞到自己的条件下,
找到一条路(未必要最优),然后沿着这条路运行,去享用它的美食

我们先不去想蛇会越来越长这个事实,问题基本就是,给你一个起点(蛇头)和一个终点( 食物),要避开障碍物(蛇身),从起点找到一条可行路到达终点。 我们可以用的方法有:

  • BFS
  • DFS
  • A*

只要有选择,就先选择最简单的方案,我们现在的目标是要让程序先跑起来, 优化是后话。so,从BFS开始。我们最初将蛇头位置放入队列,然后只要队列非空, 就将队头位置出队,然后把它四领域内的4个点放入队列,不断地循环操作, 直到到达食物的位置。这个过程中,我们需要注意几点:1.访问过的点不再访问。 2.保存每个点的父结点(即每个位置是从哪个位置走到它的, 这样我们才能把可行路径找出来)。3.蛇身所在位置和四面墙不可访问。

通过BFS找到食物后,只需要让蛇沿着可行路径运动即可。这个简单版本写完后, 贪吃蛇就可以很欢快地运行一段时间了。看图吧:(不流畅的感觉来自录屏软件@_@)

为了尽量保持简单,我用的是curses模块,直接在终端进行绘图。 从上面的动态图片可以看出,每次都单纯地使用BFS,最终有一天, 贪吃蛇会因为这种不顾后果的短视行为而陷入困境。 而且,即使到了那个时候,它也只会BFS一种策略, 导致因为当前看不到目标(食物),认为自己这辈子就这样了,破罐子破摔, 最终停在它人生中的某一个点,不再前进。(我好爱讲哲理XD)

BFS+Wander

上一节的简单版本跑起来后,我们认识到,只教贪吃蛇一种策略是不行的。 它这么笨一条蛇,你不多教它一点,它分分钟就会挂掉的。 所以,我写了个Wander函数,顾名思义,当贪吃蛇陷入困境后, 就别让它再BFS了,而是让它随便四处走走,散散心,思考一下人生什么的。 这个就好比你困惑迷茫的时候还去工作,效率不佳不说,还可能阻碍你走出困境; 相反,这时候你如果放下手中的工作,停下来,出去旅个游什么的。回来时, 说不定就豁然开朗,土地平旷,屋舍俨然了。

Wander函数怎么写都行,但是肯定有优劣之分。我写了两个版本,一个是在可行的范围内, 朝随机方向走随机步。也就是说,蛇每次运动的方向是随机出来的, 总共运动的步数也是随机的。Wander完之后,再去BFS一下,看能否吃到食物, 如果可以那就皆大欢喜了。如果不行,说明思考人生的时间还不够,再Wander一下。 这样过程不断地循环进行。可是就像“随机过程随机过”一样,你“随机Wander就随机挂”。 会Wander的蛇确实能多走好多步。可是有一天,它就会把自己给随机到一条死路上了。 陷入困境还可以Wander,进入死胡同,那可没有回滚机制。所以, 第二个版本的Wander函数,我就让贪吃蛇贪到底。在BFS无解后, 告诉蛇一个步数step(随机产生step),让它在空白区域以S形运动step步。 这回运动方向就不随机了,而是有组织有纪律地运动。先看图,然后再说说它的问题:

没错,最终还是挂掉了。S形运动也是无法让贪吃蛇避免死亡的命运。 贪吃蛇可以靠S形运动多存活一段时间,可是由于它的策略是:

while 没有按下ESC键:
    if 蛇与食物间有路径:
        走起,吃食物去
    else:
        Wander一段时间

问题就出在蛇发现它自己和食物间有路径,就二话不说跑去吃食物了。 它没有考虑到,你这一去把食物给吃了后形成的局势(蛇身布局), 完全就可能让你挂掉。(比如进入了一个自己蛇身围起来的封闭小空间)

so,为了能让蛇活得久一些,它还要更高瞻远瞩才行。

高瞻远瞩版本

我们现在已经有了一个比较低端的版本,而且对问题的认识也稍微深入了一些。 现在可以进行一些比较慎密和严谨的分析了。首先,让我们罗列一些问题: (像头脑风暴那样,想到什么就写下来即可)

  • 蛇和食物间有路径直接就去吃,不可取。那该怎么办?
  • 如果蛇去吃食物后,布局是安全的,是否就直接去吃?(这样最优吗?)
  • 怎样定义布局是否安全?
  • 蛇和食物之间如果没有路径,怎么办?
  • 最短路径是否最优?(这个明显不是了)
  • 那么,如果布局安全的情况下,最短路径是否最优?
  • 除了最短路径,我们还可以怎么走?S形?最长?
  • 怎么应对蛇身越来越长这个问题?
  • 食物是随机出现的,有没可能出现无解的布局?
  • 暴力法(brute force)能否得到最优序列?(让贪吃蛇尽可能地多吃食物)

只要去想,问题还挺多的。这时让我们以面向过程的思想,带着上面的问题, 把思路理一理。一开始,蛇很短(初始化长度为1),它看到了一个食物, 使用BFS得到矩形中每个位置到达食物的最短路径长度。在没有蛇身阻挡下, 就是曼哈顿距离。然后,我要先判断一下,贪吃蛇这一去是否安全。 所以我需要一条虚拟的蛇,它每次负责去探路。如果安全,才让真正的蛇去跑。 当然,虚拟的蛇是不会绘制出来的,它只负责模拟探路。那么, 怎么定义一个布局是安全的呢? 如果你把文章开头那张动态图片中蛇的销魂走位好好的看一下, 会发现即使到最后蛇身已经很长了,它仍然没事一般地走出了一条路。而且, 是跟着蛇尾走的!嗯,这个其实不难解释,蛇在运动的过程中,消耗蛇身, 蛇尾后面总是不断地出现新的空间。蛇短的时候还无所谓,当蛇一长, 就会发现,要想活下来,基本就只能追着蛇尾跑了。在追着蛇尾跑的过程中, 再去考虑能否安全地吃到食物。(下图是某次BFS后,得到的一个布局, 0代表食物,数字代表该位置到达食物的距离,+号代表蛇头,*号代表蛇身, -号代表蛇尾,#号代表空格,外面的一圈#号代表围墙)

# # # # # # # 
# 0 1 2 3 4 # 
# 1 2 3 # 5 # 
# 2 3 4 - 6 # 
# 3 + * * 7 # 
# 4 5 6 7 8 # 
# # # # # # # 

经过上面的分析,我们可以将布局是否安全定义为蛇是否可以跟着蛇尾运动, 也就是蛇吃完食物后,蛇头和蛇尾间是否存在路径,如果存在,我就认为是安全的。

OK,继续。真蛇派出虚拟蛇去探路后,发现吃完食物后的布局是安全的。那么, 真蛇就直奔食物了。等等,这样的策略好吗?未必。因为蛇每运动一步, 布局就变化一次。布局一变就意味着可能存在更优解。比如因为蛇尾的消耗, 原本需要绕路才能吃到的食物,突然就出现在蛇眼前了。所以,真蛇走一步后, 更好的做法是,重新做BFS。然后和上面一样进行安全判断,然后再走。

接下来我们来考虑一下,如果蛇和食物之间不存在路径怎么办? 上文其实已经提到了做法了,跟着蛇尾走。只要蛇和食物间不存在路径, 蛇就一直跟着蛇尾走。同样的,由于每走一步布局就会改变, 所以每走一步就重新做BFS得到最新布局。

好了,问题又来了。如果蛇和食物间不存在路径且蛇和蛇尾间也不存在路径, 怎么办?这个我是没办法了,选一步可行的路径来走就是了。还是一个道理, 每次只走一步,更新布局,然后再判断蛇和食物间是否有安全路径; 没有的话,蛇头和蛇尾间是否存在路径;还没有,再挑一步可行的来走。

上面列的好几个问题里都涉及到蛇的行走策略,一般而言, 我们会让蛇每次都走最短路径。这是针对蛇去吃食物的时候, 可是蛇在追自己的尾巴的时候就不能这么考虑了。我们希望的是蛇头在追蛇尾的过程中, 尽可能地慢。这样蛇头和蛇尾间才能腾出更多的空间,空间多才有得发展。 所以蛇的行走策略主要分为两种:

1. 目标是食物时,走最短路径
2. 目标是蛇尾时,走最长路径

那第三种情况呢?与食物和蛇尾都没路径存在的情况下, 这个时候本来就只是挑一步可行的步子来走,最短最长关系都不大了。 至于人为地让蛇走S形,我觉得这不是什么好策略,最初版本中已经分析过它的问题了。 (当然,除非你想使用最最无懈可击的那个版本,就是完全不管食物, 让蛇一直走S,然后在墙边留下一条过道即可。这样一来, 蛇总是可以完美地把所有食物吃完,然后占满整个空间,可是就很boring了。 没有任何的意思)

上面还提到一个问题:因为食物是随机出现的,有没可能出现无解的局面? 答案是:有。我运行了程序,然后把每一次布局都输出到log,发现会有这样的情况:

# # # # # # # 
# * * * * * # 
# * * - 0 * # 
# * * # + * # 
# * * * * * # 
# * * * * * # 
# # # # # # # 

其中,+号是蛇头,-号是蛇尾,*号是蛇身,0是食物,#号代表空格,外面一圈# 号代表墙。这个布局上,食物已经在蛇头面前了,可是它能吃吗?不能! 因为它吃完食物后,长度加1,蛇头就会把0的位置填上,布局就变成:

# # # # # # # 
# * * * * * # 
# * * - + * # 
# * * # * * # 
# * * * * * # 
# * * * * * # 
# # # # # # # 

此时,由于蛇的长度加1,蛇尾没有动,而蛇头被自己围着,挂掉了。可是, 我们却还有一个空白的格子#没有填充。按照我们之前教给蛇的策略, 面对这种情况,蛇头就只会一直追着蛇尾跑,每当它和食物有路径时, 它让虚拟的蛇跑一遍发现,得到的新布局是不安全的,所以不会去吃食物, 而是选择继续追着蛇尾跑。然后它就这样一直跑,一直跑。死循环, 直到你按ESC键为止。

由于食物是随机出现的,所以有可能出现上面这种无解的布局。当然了, 你也可以得到完满的结局,贪吃蛇把整个矩形都填充满。

上面的最后一个问题,暴力法是否能得到最优序列。从上面的分析看来, 可以得到,但不能保证一定得到。

最后,看看高瞻远瞩的蛇是怎么跑的吧:

矩形大小10*20,除去外面的边框,也就是8*18。Linux下录完屏再转成GIF格式的图片, 优化前40多M,真心是没法和Windows的比。用下面的命令优化时, 有一种系统在用生命做优化的感觉:

convert output.gif -fuzz 10% -layers Optimize optimised.gif

最后还是拿到Windows下用AE,三下五除二用图片序列合成的动态图片 (记得要在format options里选looping,不然图片是不会循环播放的)

Last but not least

如果对源代码感兴趣,请戳以下的链接: Code goes here

另外,本文的贪吃蛇程序使用了curses模块, 类Unix系统都默认安装的,使用Windows的童鞋需要安装一下这个模块, 送上地址: 需要curses请戳我

以上的代码仍然可以继续改进(现在加注释不到300行,优化一下可以更少), 也可用pygame或是pyglet库把界面做得更加漂亮,Enjoy!

如何编写一个可靠的linux守护进程

linux服务端程序都需要提供7 * 24不间断的服务,如何保证工作进程一直不退出或者不被kill掉,常见的方法就是启动一个守护进程来检测工作进程的状态,如果发现工作进程退出,就再fork一个出来。一般的实现见下面一段代码:
Continue reading “如何编写一个可靠的linux守护进程”

CVPR2009 best paper(暗通道优先单图去雾算法)

作者:何恺明

那是2009年4月24日的早上,我收到了一封不同寻常的email。发信人是CVPR 2009的主席们,他们说我的文章获得了CVPR 2009的最佳论文奖(Best Paper Award)。我反复阅读这封邮件以确认我没有理解错误。这真是一件令人难以置信的事情。

CVPR的中文名是计算机视觉与模式识别会 议,是计算机视觉领域最顶尖的国际会议之一。今年的CVPR共收到约1450篇投稿,其中393篇文章被接收,接收率为26%。只有一篇文章被选为今年的 最佳论文。这是CVPR创立25年以来首次由中国人获得这个奖项。这篇文章是我在微软亚洲研究院形象计算组实习的时候完成的,也是我个人真正意义上写的第 一篇论文。
Continue reading “CVPR2009 best paper(暗通道优先单图去雾算法)”