因为CSDN不能上传图片，故效果有所折扣
原文连接：http://blog.sina.com.cn/fulaoshi 接着讨论这个问题：“为什么一团毛线，就可以让忒修斯顺利的找到牛头怪，并能成功返回迷宫出口呢？” 事实上，如果只有毛线是不可能的，至少无法保证忒修斯顺利找到牛头怪！ 当你在迷宫中遇到讨厌的岔路时，毛线只能让你知道回去该走哪条路，却无法告诉前方该如何选择。毛线只能保证忒修斯可以全身而退，却无法指引牛头怪的方向。 这当然不能怪毛线，作为一团没有任何智能的妇女用品，它只能做到这一步了。 那可怜的忒修斯在迷宫中面对每一处岔路，是如何选择正确方向的呢？很遗憾，在大多数情况下，他并没能做出正确的选择，但也没有像前人一样迷失在迷宫中被饿死，而是最终找到了牛头怪并铲除了它！人和人的差距为什么这么大捏？？因为在出发前，阿里阿德涅公主在他耳边悄悄的说了一个口诀。 正是这个口诀，揭开了深度优先搜索的全部秘密。 口诀的内容，现在听起来很像游戏秘籍，比如魂斗罗调30条命……“上上下下左左右右”！ 是的，你没听错，伟大的秘密就隐藏在这么简单的口诀中。 我来给大家解释一下，这个口诀指导了忒修斯进入迷宫后的行走规则，即：每当遇到岔路需要做出选择时，都优先选择往上走（如果上下左右不直观可以理解为东西南北），如果无法走【无法走的定义是：此路是死路，或此路上有毛线，代表已经走过了】，下一个选择是往下走，如果还不行就往左走，再不行就往右走。如果四个方向都不行捏？很简单，说明这个地儿来错了，顺着毛线退回到上一个岔路口，选择下一个方向再次尝试。（如果你没看明白一会儿有图例说明） 大家可能看出来了，这实际上是一个挺笨的方法，就是“前进->碰壁->转方向->前进->碰壁->转方向->前进->碰壁->后退->转方向->前进……”的不断重复，但有了这个口诀和毛线，忒修斯就算回绕一些弯路，但最终一定能找到牛头怪。 总结时间：忒修斯能安然无恙的进出迷宫、找到目标，靠的是毛线和口诀。 毛线：记录着每一个岔路口的选择，可以利用它退回到上一个路口重新选择方向。在编程中，往往会使用数据结构栈来实现（不明白栈操作的赶快百度一下啦），或者用一维数组也可以。 口诀：算法的关键，用流程图表示会比较清楚，可惜手头没有Visio之类的，哪位同学有兴趣可以画一个发给我啊。 下面用4幅图来说明这个过程： 第一幅图是简单的迷宫，左下角是入口，右上角是出口，接下来为方便演示，我们按照“右上左下”的优先级顺利来进行探索（即遇到岔路先选择走右面，不行选择上面，然后是左面，下面）。 图中的线条相当于毛线，记录这每一步的选择 因为先走右边，很快就走到了右下角，右边不能再走了，下一个选择是上边。上到顶发现右边、上边都不能再走了，选择左边，往前走发现到了死胡同，上下左都不能走，右边是走过的也不能走，该怎么办呢？ 唯一的选择就是沿着毛线退回到上一个路口重新做出选择，先退到路口A，刚才在路口A选择的方向是左边，下一个选择是下边，可下边是走过的不能走，只能继续后退。 退到路口B，刚才在路口B选择的是上边，下一个选择是左边，不行，再下一个是下边，也不行，继续后退。 退到路口C，刚才在路口C选择的是右边，下一个选择是上边，可以走，ok，掉转方向，let's go。 第四幅图就不用多上了，按照“右上左下”的优先顺序，很快找到了出口。 练习时间：请使用深度优先搜索原理走完下面的迷宫 注意：每次在岔路口选择都必须按照原则进行（不一定非要是“右上左下”，也可以是“上下左右”），不能人为的做出判断。 下面是我用画笔绘制的将行走过程模拟图 静态图片可能无法完全说明问题，强烈建议读者自己用画笔来画一画。 经过这个练习，你会发现，使用深度优先算法找到的一般并不是最短的路径，但它保证可以找到一条路径（如果迷宫没有问题的话），如果你坚持要找最短的，后面的广度优先算法会满足你的要求，这是后话。现在故事讲了、原理分析了、图也画了，该真刀真枪的上代码了， 请见下回分解
原文连接：http://blog.sina.com.cn/fulaoshi 接着讨论这个问题：“为什么一团毛线，就可以让忒修斯顺利的找到牛头怪，并能成功返回迷宫出口呢？” 事实上，如果只有毛线是不可能的，至少无法保证忒修斯顺利找到牛头怪！ 当你在迷宫中遇到讨厌的岔路时，毛线只能让你知道回去该走哪条路，却无法告诉前方该如何选择。毛线只能保证忒修斯可以全身而退，却无法指引牛头怪的方向。 这当然不能怪毛线，作为一团没有任何智能的妇女用品，它只能做到这一步了。 那可怜的忒修斯在迷宫中面对每一处岔路，是如何选择正确方向的呢？很遗憾，在大多数情况下，他并没能做出正确的选择，但也没有像前人一样迷失在迷宫中被饿死，而是最终找到了牛头怪并铲除了它！人和人的差距为什么这么大捏？？因为在出发前，阿里阿德涅公主在他耳边悄悄的说了一个口诀。 正是这个口诀，揭开了深度优先搜索的全部秘密。 口诀的内容，现在听起来很像游戏秘籍，比如魂斗罗调30条命……“上上下下左左右右”！ 是的，你没听错，伟大的秘密就隐藏在这么简单的口诀中。 我来给大家解释一下，这个口诀指导了忒修斯进入迷宫后的行走规则，即：每当遇到岔路需要做出选择时，都优先选择往上走（如果上下左右不直观可以理解为东西南北），如果无法走【无法走的定义是：此路是死路，或此路上有毛线，代表已经走过了】，下一个选择是往下走，如果还不行就往左走，再不行就往右走。如果四个方向都不行捏？很简单，说明这个地儿来错了，顺着毛线退回到上一个岔路口，选择下一个方向再次尝试。（如果你没看明白一会儿有图例说明） 大家可能看出来了，这实际上是一个挺笨的方法，就是“前进->碰壁->转方向->前进->碰壁->转方向->前进->碰壁->后退->转方向->前进……”的不断重复，但有了这个口诀和毛线，忒修斯就算回绕一些弯路，但最终一定能找到牛头怪。 总结时间：忒修斯能安然无恙的进出迷宫、找到目标，靠的是毛线和口诀。 毛线：记录着每一个岔路口的选择，可以利用它退回到上一个路口重新选择方向。在编程中，往往会使用数据结构栈来实现（不明白栈操作的赶快百度一下啦），或者用一维数组也可以。 口诀：算法的关键，用流程图表示会比较清楚，可惜手头没有Visio之类的，哪位同学有兴趣可以画一个发给我啊。 下面用4幅图来说明这个过程： 第一幅图是简单的迷宫，左下角是入口，右上角是出口，接下来为方便演示，我们按照“右上左下”的优先级顺利来进行探索（即遇到岔路先选择走右面，不行选择上面，然后是左面，下面）。 图中的线条相当于毛线，记录这每一步的选择 因为先走右边，很快就走到了右下角，右边不能再走了，下一个选择是上边。上到顶发现右边、上边都不能再走了，选择左边，往前走发现到了死胡同，上下左都不能走，右边是走过的也不能走，该怎么办呢？ 唯一的选择就是沿着毛线退回到上一个路口重新做出选择，先退到路口A，刚才在路口A选择的方向是左边，下一个选择是下边，可下边是走过的不能走，只能继续后退。 退到路口B，刚才在路口B选择的是上边，下一个选择是左边，不行，再下一个是下边，也不行，继续后退。 退到路口C，刚才在路口C选择的是右边，下一个选择是上边，可以走，ok，掉转方向，let's go。 第四幅图就不用多上了，按照“右上左下”的优先顺序，很快找到了出口。 练习时间：请使用深度优先搜索原理走完下面的迷宫 注意：每次在岔路口选择都必须按照原则进行（不一定非要是“右上左下”，也可以是“上下左右”），不能人为的做出判断。 下面是我用画笔绘制的将行走过程模拟图 静态图片可能无法完全说明问题，强烈建议读者自己用画笔来画一画。 经过这个练习，你会发现，使用深度优先算法找到的一般并不是最短的路径，但它保证可以找到一条路径（如果迷宫没有问题的话），如果你坚持要找最短的，后面的广度优先算法会满足你的要求，这是后话。现在故事讲了、原理分析了、图也画了，该真刀真枪的上代码了， 请见下回分解
解决方案 »
- 问个 THINK IN JAVA 的左移位运算问题
- 运用Java多线程和多媒体技术设计一个简单的益智类小游戏
- ibatis问题高手帮忙！
- 用eclipse时用packgae老是出错，请看：
- 问个问题，关于对象成员引用的，谁帮看下？
- 请教jboss3.2.3整合的一个问题
- 关于java调用exe的问题——急待解决方案，在线等待高人
- sdk 和j2re都需要安装吗?
- 从TXT文件到网页的中文显示问题。
- applet 与 sqlserver数据库
- 会使用JBuilder2006的高手请进，有关jtable和jtree,急！
- 在eclipse里,是不是,在程序中必须有一个类的名字,左边树的类名字一样.否则无法Run??
再如贪心算法，分支限界等，大部分都用到这深度优先策略
I服了U！