戏说深度优先算法（起源）

今天来说说深度优先搜索，属于搜索回朔类的算法，相对比较有趣。



    关于这个算法的最早传说出现在古希腊时代：



    没落贵族的忒修斯（没落到被选为了祭品），爱上了残暴国王弥诺斯的女儿阿里阿德涅公主，而未来的岳父却决定把可怜的忒修斯送到克里特岛喂牛头怪。

  

    这个特里克岛可是国王的呕心沥血之作，岛上最著名的建筑就是地下迷宫，据说被扔进去了谁都绕不出来，就算你运气好，找到正确的路，还有一头凶猛的牛头怪养在必经之路上，送到岛上作为祭品的人从来没能活着回来。



     按常理忒修斯也难逃厄运，但后来的故事印证了两个亘古不变的真理：1，女人是不可靠的，女儿也不例外   2，穷小子要翻身，就得靠女人



     在忒修斯出发前，小伙子费劲脑汁与阿里阿德涅公主又见了最后一面，在这次历史性的会晤中，公主送给了穷小伙两件足以挽救其性命的礼物：一团毛线和一把据说唯一能杀死牛头怪的剑。



     公主送毛线自然不是要教夫君打毛衣，而是指导他：“把线头系于迷宫入口处，一路放线团，一边进入到迷宫，杀掉牛头怪，再循着线团走出迷宫”。



     果然，忒修斯按照公主的方法顺利走到了迷宫中央，经过一番搏斗杀死了牛头怪，并沿着毛线退出了迷宫。按理说后续应该是个大团圆的结局：忒修斯回到王国迎娶公主，三两年后国王病逝忒修斯继承王位，于是国王与王后过上了幸福的生活。



     不过古希腊的剧作家个个都是苦大仇深，不爱写大团圆的结尾，一般都要主人公死光光或落下终身残疾才成。这个故事的详细结局可以自行搜索，反正可怜的算法大师、深度优先搜索算法的缔造者阿里阿德涅公主最后跳入大海喂鲨鱼了。



     这个故事大家在小时候肯定都或多或少的知道，现在我们作为一名算法爱好者，应该考虑一个在原著中被忽略的很重要的细节：为什么一团毛线，就可以让忒修斯顺利的找到牛头怪，并能成功返回迷宫出口呢？



     请大家思考，吃午饭去了，回来再写。

注1：不会贴图，完整版请看 http://blog.sina.com.cn/fulaoshi
注2：入门贴，一些问题未作深入讨论，比如关于深度优先是否可以找到最优解问题

接着讨论这个问题：“为什么一团毛线，就可以让忒修斯顺利的找到牛头怪，并能成功返回迷宫出口呢？”



     事实上，如果只有毛线是不可能的，至少无法保证忒修斯顺利找到牛头怪！



     当你在迷宫中遇到讨厌的岔路时，毛线只能让你知道回去该走哪条路，却无法告诉前方该如何选择。毛线只能保证忒修斯可以全身而退，却无法指引牛头怪的方向。



     这当然不能怪毛线，作为一团没有任何智能的妇女用品，它只能做到这一步了。



     那可怜的忒修斯在迷宫中面对每一处岔路，是如何选择正确方向的呢？很遗憾，在大多数情况下，他并没能做出正确的选择，但也没有像前人一样迷失在迷宫中被饿死，而是最终找到了牛头怪并铲除了它！人和人的差距为什么这么大捏？？因为在出发前，阿里阿德涅公主在他耳边悄悄的说了一个口诀。



     正是这个口诀，揭开了深度优先搜索的全部秘密。



     口诀的内容，现在听起来很像游戏秘籍，比如魂斗罗调30条命……“上上下下左左右右”！



     是的，你没听错，伟大的秘密就隐藏在这么简单的口诀中。



     我来给大家解释一下，这个口诀指导了忒修斯进入迷宫后的行走规则，即：每当遇到岔路需要做出选择时，都优先选择往上走（如果上下左右不直观可以理解为东西南北），如果无法走【无法走的定义是：此路是死路，或此路上有毛线，代表已经走过了】，下一个选择是往下走，如果还不行就往左走，再不行就往右走。如果四个方向都不行捏？很简单，说明这个地儿来错了，顺着毛线退回到上一个岔路口，选择下一个方向再次尝试。（如果你没看明白一会儿有图例说明）



     大家可能看出来了，这实际上是一个挺笨的方法，就是“前进->碰壁->转方向->前进->碰壁->转方向->前进->碰壁->后退->转方向->前进……”的不断重复，但有了这个口诀和毛线，忒修斯就算回绕一些弯路，但最终一定能找到牛头怪。



     总结时间：忒修斯能安然无恙的进出迷宫、找到目标，靠的是毛线和口诀。



     毛线：记录着每一个岔路口的选择，可以利用它退回到上一个路口重新选择方向。在编程中，往往会使用数据结构栈来实现（不明白栈操作的赶快百度一下啦），或者用一维数组也可以。



     口诀：算法的关键，用流程图表示会比较清楚，可惜手头没有Visio之类的，哪位同学有兴趣可以画一个发给我啊。



     下面用4幅图来说明这个过程：

    



    第一幅图是简单的迷宫，左下角是入口，右上角是出口，接下来为方便演示，我们按照“右上左下”的优先级顺利来进行探索（即遇到岔路先选择走右面，不行选择上面，然后是左面，下面）。

   



图中的线条相当于毛线，记录这每一步的选择



    因为先走右边，很快就走到了右下角，右边不能再走了，下一个选择是上边。上到顶发现右边、上边都不能再走了，选择左边，往前走发现到了死胡同，上下左都不能走，右边是走过的也不能走，该怎么办呢？



    唯一的选择就是沿着毛线退回到上一个路口重新做出选择，先退到路口A，刚才在路口A选择的方向是左边，下一个选择是下边，可下边是走过的不能走，只能继续后退。



    退到路口B，刚才在路口B选择的是上边，下一个选择是左边，不行，再下一个是下边，也不行，继续后退。



    退到路口C，刚才在路口C选择的是右边，下一个选择是上边，可以走，ok，掉转方向，let's go。



    第四幅图就不用多上了，按照“右上左下”的优先顺序，很快找到了出口。



    练习时间：请使用深度优先搜索原理走完下面的迷宫

   

    

    注意：每次在岔路口选择都必须按照原则进行（不一定非要是“右上左下”，也可以是“上下左右”），不能人为的做出判断。



    下面是我用画笔绘制的将行走过程模拟图

   





    静态图片可能无法完全说明问题，强烈建议读者自己用画笔来画一画。



    经过这个练习，你会发现，使用深度优先算法找到的一般并不是最短的路径，但它保证可以找到一条路径（如果迷宫没有问题的话），如果你坚持要找最短的，后面的广度优先算法会满足你的要求，这是后话。现在故事讲了、原理分析了、图也画了，该真刀真枪的上代码了， 请见下回分解。

长见识了，不过后面的口诀部分没耐心看了

其实不需要那么复杂，只需要沿着墙壁一直靠右走就行了，总会碰到牛怪的。

前提是没有环