| 昨天，在女人火把过桥问题中，对图的搜索并不完美，是典型的穷举算法思想，希望能生成一棵以起点为根的“全分支树”。 |
1、按照邻接关系直接搜索
这典型的穷举搜索思想，从 A 开始，依次按照邻接关系，遍历整个图
但是，一旦
邻接关系中存在环路，程序即陷入死循环，比如：
A > B > C > A
不幸，火把问题就存在环路
否决 ！
2、深度优先搜索 DFS
仍然是穷举搜索思想，仍然是从 A 开始，依次按照邻接关系，遍历整个图
和方法 1 不同的是，访问过的节点做上标记，下次就不再访问了。
优点：
1）解决了环路的问题
2）只要存在路线，肯定能找到
缺点：
1）不能保证路线是最短距离
2）只能找到一条路线
否决！
3、广度优先搜索 BFS
和 DFS 基本上一样，只不过
无路可走需要回退的时候，DFS 是后进先出，BFS 是先进先出而已。
优点：
1）解决了环路的问题
2）只要存在路线，肯定能找到
3）找到的路线是最短距离（注意：这里说的距离，并不是权的和，仅仅指 A 到 F 的步骤）
缺点：
1）不能保证路线具有最小权
2）只能找到一条路线
否决
4、全分支树法
将 A 作为根，从根开始，依次将邻接点添加为自己的孩子（注意：邻接在父辈中出现过则放弃），直到生成完整的树。
依然是穷举和暴力的思想，这棵树必然包括所有的路线。
优点：
1）思路简单
2）能找到所有路线
3）能找到所有最短路线
缺点：
1）只能应用在节点数目较少、邻接不复杂的情况下
在火把问题中，节点数目为30，邻接比较复杂，个人测试了一下，到第 6 层就开是出现明显的延迟，不要说到达 30 了
否决！
5、部分分支树法
依然是穷举和暴力的思想，在方法 4 的基础上添加一个层数条件限制，超过层数则停止该分支的生长
优点：
1）只要层数设定够大，就能找到最短路线
缺点：
1）不能保证找到所有路线
2）不能保障找到所有最短路线
3）如果 A F 距离太远，就要设定较大的层数，有可能无法生成树
我在解决过桥问题时，就是用到了这种方法，设定了层数为5 ，并且找到了 2 条最短路线和 37 条其他路线（不包括环路）
然而这只是我运气好，因为最短路线就在第五层上，如果需要到达第三十层，这种方法就失效了。
另外，37条其他路线，仍然不是全部路线，还是没有达到我的目标。
否决！
6、不断增长的、明确终点的、最小生成树法
什么是生成树：如果图中任意删除一条边，就会出现一个孤立节点；添加任意一条边，则会出现环路，这个图就是一个生成树。
所谓最小生成树，就是指生成树所有的边权值总和最小。
最小生成树保证了我们可以从图中一点到达另外任意一点、没有环路、且所有边的权值总和最小
而我们的过桥问题，与最小生成树还有点不同，
不但给出了起点，而且有明确的终点，一下减少了很多运算
首先，一些节点组合根本不存在生成树
其次，一些节点组合虽然存在生成树，但构造过程中，终点要被提前加入（为了保证最小），则停止继续构造，一下节省了很多步骤
第三、一些节点组合虽然存在生成树，但构造过程中，出现分叉（为了保证最小），则停止继续构造，一下节省了很多步骤
最后，如果你不想找到所有路线，在构造生成树的过程中，如果超过了当前最小权值，则停止继续构造，又节省了很多步骤
下面以 ABCDEF 来说明算法步骤，其中 A 是起点， F 是终点
1 构造 AF 之间的最小生成树，存在，则记录
2 依次构造 ABF ACF ADF AEF，存在，则记录；如果构造过程中，F 节点被提前加入，或者出现分叉，则停止继续构造
3 依次构造 ABCF ABDF ABEF ACDF ACEF ADEF ，存在，则记录；如果构造过程中，F 节点被提前加入，或者出现分叉，则停止继续构造
4 依次构造 ABCDF ABCEF ADCEF ，存在，则记录；如果构造过程中，F 节点被提前加入，或者出现分叉，则停止继续构造
5 依次构造 ABCDEF ，存在，则记录；如果构造过程中，F 节点被提前加入，或者出现分叉，则停止继续构造
算法完成
注意：说
构造 ABCDF
的最小生成树，最后得出的
顺序不一定是 ABCDF
，因为要保证最小，这就是为什么 F 有可能被提前加入，或者出现分叉。
对应到过桥问题，一共 30 个节点，去除起始点，就是 28 个节点，一共要构造生成树的数目是（C 表示组合）：
C(28,1)+C(28,2)+C(28,3)+C(28,4)+C(28,5)+...........+C(28,26)+C(28,27)+C(28,28)
这个
数量级也就在亿次左右，比全分支树宇宙级的计算量，显得微不足道了。
针对这道题的特殊情况，我们
还可以进一步减少组合的数量
1、有 4 个节点只同出发点邻接，再不同其他任何点相连，这 4 个点可以排除
2、还有 4 个点只同目标点邻接，再不同其他任何点相连，这 4 个点也可以排除
这样就成了 20 个节点，数量一下降到了一
百万左右
3、起始点有 10 个邻居，去掉 4 个孤立的，另外 6 个邻居，每棵生成树至少包括一个，否则就无法出发
这个规则对目标点也适用，这样，组合数量又少了不少。
4、最小生成树变大的时候，每次加入的节点数目必须是偶数，而且火把在左、在右的节点数目必须相同
这个条件一限制，数量即估计就到十万了
5、如果你想找的是最短时间，那每次过河肯定是两个人，返回是肯定一个人（只有这样才能保证时间最短），
这样，就可以减少一些节点的邻接点，又减少了很多计算量
总之，最后用普通台式机就可找到全部可能的路线了，从而达到了我的目的。
结论：穷举法、暴力法只能用在场景简单的情况下，复杂情况还是要具体分析，寻找最优解法。
这两天不想再写任何程序了，从方法1 一直写到方法5 ，累着了，呵呵。
哪位兄弟要是有兴趣、有精力，可以把方法6 实现以下，相关数据在
上一篇帖子中都有，再或者等过几天还是我来写。
总之，直到知道总共有多少条路线，以及每个路线的具体走法，这个问题才算最终有了完美的解决。
本文转自左洸博客园博客，原文链接：http://www.cnblogs.com/myqiao/archive/2009/07/26/1531451.html，如需转载请自行联系原作者
