前言
这周我们来讲计算机算法中的一大类问题，·遍历问题·。
- “遍历”这个专业名词听起来有点高冷，但实际上它就是把所有东西找一遍的专业说法而已，我们在生活和工作中经常会遇到这样的问题。
- 比如我在之前写给你的第141封信介绍Google下载所有网页的机器人，它所面临的就是遍历问题，也就是把互联网上所有的网页找一遍。
- 解决遍历问题的关键:
- 一是需要找全，别落下什么。
- 二是需要效率高，不要老做无用功。
- 相应的计算机算法其实就是围绕着这两个关键点设计的，而在设计那些算法的过程中，很多聪明人显示出的智慧对我们的工作很有启发作用。为了让“遍历”这个问题容易理解，我们还是先从一个古老的游戏做起，就是走迷宫的游戏。为了方便你对迷宫有进一步的认识，
对于任何一个迷宫，怎样走能确保走出来呢？
相传古埃及有一位法老在幼年发明了一种方法，能够做到这一点。在那个传说中，这位少年被放到了一个迷宫中，被要求走出来。这位天才少年带了一根很长的绳子一头拴在迷宫的入口，然后采用下面的走法走出了迷宫。
先说两个大原则：
- 大原则1：他走到哪里就把绳子拖到哪里，也就是说，绳子记录了他从入口经历各个分岔口之后到当前位置的行走的路线。
- 大原则2：无论是遇到新的岔路口，还是回到上一个岔路口，都先走“尚未进入的最左边的岔路”。 有了这两个大原则，再说具体的走法：
1、起始的走法：
带着绳子进入到迷宫后，来到第一个岔口（如果有两个以上，就选择最左边的先走），在这个岔口，走进最左边的分岔，让绳子随着自己沿着岔路往前走，在遇到新的岔口的时候，还是沿着最左边走，直到走到死胡同的时候往后退，每次往后退时，退到上一个岔口，我们不妨称之为岔口X。这时进入左边第二个岔道（因为第一个已经走完了，证明是死胡同了）。
2.递进走法：
当进入到第二个岔道后，重复第一步的过程，直到走不下去退回来，又走回到岔口X，这时进入左边第三个岔口。然后再重复上述过程，直到遇到死胡同往后退，或者运气好已经走出去了。这样就把岔口X所能到达的所有岔路都“遍历”一遍了。
3、回溯走法
当把岔口X所能到达的所有岔路都试了一遍，还没有走通时，沿着绳子往回走，走回到X的前一个岔路口Y。重复上述这三步。 上述方法能够保证解决任何迷宫问题。当我们不断重复上述三个步骤后，会有两个结果，第一个结果是走出去了，第二个是回到了出发点。前一个结果说明迷宫走得通，第二个说明走不通。不管哪一个结果，这个迷宫都算走完了。
但事实上，这个笨办法是唯一能够确保走出任何迷宫的方法。
很多聪明人试图忽略掉那些看似不可能的分支，然而最后能走通的路径，常常隐藏在那些看似不可能的地方。 事实上，任何试图省略一些岔路的人，走的冤枉路会多很多。
那根绳子特别重要，因为它记录了你是从哪里来，哪些岔路已经走过，避免了你来回来去走重复路。
带一个长绳子可能不现实，事实上只要带一小口袋豆子或者什么其它的标志物，
- 在每一个路口做一个标记即可。每开始进入一个新的岔口，在那个地方放一粒豆子，等到前面走不通回溯到这个路口时，将豆子捡起来，放入下一个岔口即可。
三个总结：
- 走迷宫只要坚持每次遇到岔口，就走左边尚未走过的分支，一定能走出去。这个方法由于每次都是先走左边的岔路，因此也叫做
左手算法，或者顺时针算法。当然你每次走右边也可以，那就是逆时针算法，道理是一样的。 -
一些看似是笨办法的做法其实并不笨，因为如果在这个过程中有些工作看似能省掉，其实省不掉，试图抄近路或者盲目试错，其结果都是不必要的重复和返工。世界上很多事情，不怕按部就班做得慢，就怕来回来去兜圈子和返工。
我们人的生活轨迹其实就是一个迷宫。凡事我们应该允许犯一次错误，但是应该有一个本子（如同上面例子中的绳子），记录我们在哪里犯了错误，将来遇到同样的情况，不犯第二次。如果没有这根绳子或者一个本子，同样的错误会不断犯下去的。- 明天我们聊聊遍历算法的普遍意义和一些等价问题。 思考题：如果你新到一个大公司上班，办公楼很大，你如何最快地记住经常要去的地方怎么走？
See Also
- newpost
/Users/devzkn/bin//newpost The_maze_problem_of_Egyptian_Pharaohs 埃及法老的迷宫问题:左手算法---遍历 -t GoogleMethodology #原来""的参数，需要自己加上""
-
Previous
sendMsg -
Next
How_to_abstract_a_theoretical_problem_with_universal_value_from_specific_problems
