前言
-
再次体会递归的逻辑，以及堆栈这种抽象的数据结构（可以用来避免堆栈的效率问题）。
-
从迷宫问题，推广到一大类问题—–最短路径问题的解法
-
具体问题抽象化，使用四元组进行表示迷宫问题：
-
在工程上和理论上解决迷宫问题的异同
-
具体问题抽象化，使用四元组进行表示迷宫问题
- 花体字母V:
其中花体字母V表示一个岔路口的集合，具体讲在这个例子中V＝｛A，B，C，……，N｝。花体字母D表示岔路口之间直接的路径，也就是说，如果从A－B是一条直接的通路，那么线段AB就在D中。S和E是两个特殊的岔路口，分别表示入口和出口。
-
数学的表示是一种，商业的表示、法律的表示、医学的表示都是。所谓职业化，就是要用职业的语言表述问题。
-
\2. 一条路径P是前后相连的一组线段，比如P可以等于（B到C，C到D，D到L）。
-
\3. 我们的问题是找一个特殊的路径P，起点为S，终点为E，如果找到了，就输出这条路径，如果没有找到，就输出“迷宫走不通”的信息。
为什么要把这个问题数学化呢？一来把问题的已知条件和所需要完成的目标搞清楚，二来方便大家在同一个共识上交流和一起工作。学习数学主要的目的是能够抽象化问题，而不是做加减乘除。
今天加减乘除早交给了计算机去完成，而抽象化问题的能力依然属于人类自身。没有这个能力，当计算机出现后，会算简单算术的人就失业了，但是能够抽象化问题，并且解决问题的人就因为有了计算机就如虎添翼了。
程序 解决迷宫问题
明确了问题，接下来就要解决问题。我们把周一介绍的法老找到的用绳子走迷宫的想法用下面比较准确的语言表述一下，学过计算机的人其实很容易把这段话变成程序，不过我还是建议你对照迷宫图片来看下面的部分：
- \1. 在当前的岔路口，用左手原则，顺时针寻找下一个还没有走的路径。
- 如果能找到，则沿着下一个路径走到相邻的岔路口。比如在D这个位置，DE已经走过了，DL就是下一个还没有走的路径。沿着这个路径，就走到了L这个岔路口。
- 如果已经不存在还没有走过的路径，那么就在这个岔路口放一颗豆子，表示已经来过，此路不通，以后不要试了。然后返回到上一个路口。比如我们在D这个位置，DE和DL都走过了，这时，就在D放一颗豆子，然后回到上一个路口，比如说是C。
-
\2. 如果当前的岔路口是E，即出口，就成功了。打印相应的路径就好。如果当前的岔路口已经有了一颗豆子，说明走到了原来失败的地点，就不要再试验了，原路返回。
- \3. 当从某一条路径返回后，把这条路径打上一个叉叉，表示已经尝试过了，走不通，下次可以从紧挨着这条路径的右边一条再试验。比如从D回到了C，把CD打个叉子，下次就从CD右边的CJ接着往前试。
在计算机算法中，把上述1，2，3写成一个模块，在有的编程语言中这种模块被称为函数，有些被称为过程，反正都是一回事。这个模块可以来回来去地使用，我们不妨把它称为“顺时针探路”。
最后，只要从入口开始调用“顺时针探路”这个过程即可。如果一直没有走通，这个过程执行一遍会回到起点S，那就失败了。
把上面这个描述变成计算机的程序语言，这个程序就写好了。
采用堆栈解决递归的效率问题
上述算法整个的结构是递归的，也就是说，一开始在入口S调用“顺时针探路”这个过程，在这个过程里面，走到A这个岔口时，从A开始继续调用“顺时针探路”这个过程……直到找到路径或者不断返回，直到失败。这就如同我们小时候听到的一个故事，从前有个山，山里有个庙，庙里有个老和尚在讲故事，讲的是什么故事呢，“从前有个山……”。
所不同的是，上述算法比那个古老的故事多了三个条件。
-
\1. 如果讲到某一次的时候，有一个出口能出去，故事就讲完了。
-
\2. 它有一个到头的地方，到了那个地方，故事就返回了。
-
\3. 如果返回到开头还没有看到出口，故事就失败了。
这个原则就是递归。
使用堆栈这种数据结构 来提升效率
一些学习计算机的读者问，递归的做法是否效率低？其实递归更多地是一种思维方式，真到了需要实现的时候，其实有办法规避递归的低效率问题。
具体到这个问题，我们可以把一路走过来的岔路口记在一个本子上，从上到下，一行一个写清楚。如果走到死胡同，往回退，每退一步，就把相应的岔路口从本子上划掉。就这样，遇到新的就写上，退回去就划掉，这其实就自动地实现了递归功能，并不复杂。
当然，在程序中并不要使用小本子，而是使用我写给你的第98封来信中说过的堆栈这种数据结构。在任何时候遇到一个难题，先想办法找到争取的解决方法，至于解决方案中涉及到效率的问题，第二步再想想有没有办法提高效率。
科学和工程的差别。
如果你在大学学计算机课程，老师出了这道题，只要你把上面我们讨论的想法写成一个程序，交给大学的老师，你一定会得到A。
但是，如果你把同样的程序不作丝毫修改，作为产品的一部分提交给公司，相应的产品很可能出错，而一旦出错，是很难检查的，因此你需要增加很多冗余的信息。一方面帮助出错的时候查错，另一方面不断进行验证，以免出错。比如每一个真实的岔路口是有坐标的，单纯从算法来讲，它们是冗余信息，不需要考虑，但是这些看似冗余的信息可能有用。
虽然我们总是力图将算法设计得无误，程序写得无误，在这样理想的情况下，不需要这些坐标信息也能完成走迷宫的任务，但是，绝对无错的设计和绝对无错的程序几乎见不到。加入坐标之后，如果程序在递归迭代时出错了，把岔路口的次序搞乱了，通过坐标很容易发现这件事。
工程需要为测试增加设计
一个能够真正商品化的计算机程序，里面不仅包含执行相应功能的代码，而且包含很多测试和调试的代码，以免程序出错，找不到原因。通常，调试程序的时间是写程序的三四倍，甚至更多，因此，多花30%的时间写调试代码非常重要。类似地，商用的、性能可靠的半导体芯片设计，里面有大量的测试电路，它们不提供任何实用的功能，只是为了测试芯片的好坏。在半导体设计中，这些电路叫DFT（Design For Testing），即为测试增加的设计。
中国半导体和美国最大的一个差距就在于中国人做事比较急，在设计半导体芯片时，懒得设计看似没有功能性作用的测试电路。这样，芯片做出来之后，很难知道哪一片是好的，哪一片有问题，常常等到用户的产品和设备出了问题，才知道相应的芯片有问题。我国芯片的龙头企业展讯公司早期有一段时间芯片的合格率就是上不去，而且问题发现不了。
2008年后，这个问题一下子解决了，原因是公司从博通请了李力游当CEO，李力游有着丰富的半导体设计经验，一看展讯当时的芯片缺了DFT一环，将它补上。这样，芯片出厂时好坏是知道的，坏的扔了就完了，不至于让整个设备出问题。从这两个例子，我们能看出科学和工程的区别。
从迷宫问题引申出来的问题，即最短路径问题。
我们在迷宫问题中，只要找到一套路径就算完成任务了，没有考虑到路径的长短。如果我们要考虑路径的长度，该怎么做呢？
- 首先，我们还是要清晰地定义问题，什么是路径的长短？
- 比如在互联网的传输中，所谓路径长短通常是指经过了多少个服务器，而不在于经过的光纤的长短。
- 具体到迷宫这张图，从A到D，经过B，C，长度就是3，如果经过B，J，K，L，长度就是5。但是，如果我们真的走迷宫，或者在城市里骑自行车，少一公里就是一公里。
接下来，就是要将我们之前介绍的图的遍历算法稍作修改，每一步记录下到目前为止从起始点到当前点的最短路径。具体的算法我们这里就省略了，我们只是强调，这几个算法本身的相通性。最佳路径，或者说最短路径的算法，在很多场合都有应用，这些我们以后还会讲到。
总结一下今天的内容：
-
\1. 将问题抽象化，并且进行职业化的表述很重要。这不仅可以帮助我们举一反三，而且便于和同行交流。
-
\2. 我们看到了如何从一个问题延伸到另一个问题，这样就可以建立起知识的网络。
-
\3. 工程和科学不同，科学主要专注于原理，工程需要考虑非常多的实际问题，包括测试和容错。
思考题：根据你的经验举一个例子，说明专业人士在表述专业问题时和业余人士有什么不同。
祝近安
See Also
- newpost
/Users/devzkn/bin//newpost The_extension_of_Maze_algorithms_and_their_relationship_to_recursion 迷宫算法的扩展以及它们和递归的关系:科学和工程思维的不同 -t GoogleMethodology #原来""的参数，需要自己加上""
转载请注明：pua1203的博客 > The_extension_of_Maze_algorithms_and_their_relationship_to_recursion
