使用VB求解华容道问题

新客网 XKER.COM 2004-11-24 来源：收藏本文

1、问题的提出
1.1“华容道”简介
“华容道”是一种中国古代的智力游戏玩具，在一个宽为4，长为5的矩形框中，有10个棋子，包括一个曹操，五虎上将，四个小卒，要求在各个棋子不重叠的情况下进行移动，最有将曹操从棋盘上方移动到下边中央为成功。由于五员大将可以横放也可以竖放，有许多种排列方法，因而可以形成非常复杂的棋局，人们还给常用的棋局起了很多好听的名字，例如下图就是“横刀立马”的布局图。

图1.1 “横刀立马”的布局

关于此问题的求解方法，现在已经有许多文章详细描述，本文不再一一描述，专门针对“广度优先算法”方式解题进行讨论。
1.2广度优先算法的讨论
我们知道，对于类似于“华容道”的问题，例如迷宫问题等，都可以归结为图论中图的遍历和最短路径问题。也就是说，从某一个具体状态开始作为图的起点，每走出任意一步以后得到的状态作为这个节点的延伸，只要保证每次走出的状态不和原来已经走过的状态相重复，那么就可以遍历所有由此原始状态可能到达的所有状态，从而形成一张完整的倒立放置的树图，如下图所示意。

图1.2 状态转化示意图

针对“华容道”问题，其实质在于如何快速构建这样一张状态树图，在数据量未知的情况下，保证快速找到最终的结果。要做到这一点，有许多算法，广度优先是其中比较流行的一种算法。其具体思路是：
由起点出发，先构建第一层的节点，然后依次构建第二层，第三层节点，在构建的过程中，为了保证数据不重复出现，需要对每一个新节点都和原来已经生成的所有节点进行比较，保证其不重复出现在图中。
问题则由此而产生，由于在每次增加新节点时，都需要和原来所有的节点进行比较以保证此节点不重复出现，随着节点数量的增加，每次需要进行的比较也不断增加，这样就需要进行大量的时间用于比较状态是否重复，从而形成算法效率的一个瓶颈。这也是有人认为广度优先算法效率低下的一个重要原因。
下面将讨论如何优化广度优先算法以提高效率。
2、广度优先算法的优化
我们现在假设已经找到了一条从起始点状态到最终结果状态的一条最短路径，那么我们显然可以得到如下的推论：
从起始点到此最短路径上的每一个具体状态，所走的路径都是针对此节点状态的最短路径。
也就是说，我们要找到从起点到终点的最短路径，只能够通过行走每个节点的最短路径来得到。
我们现在给图中的每一个节点，都标示上其对应的最短路径步数，形成如同下图的一张带有路径步数的节点状态树图。

图2.1 带有最短路径步数的状态树图

结合上图，我们可以很容易得到如下的结论：

在最短路径树图中，与任何级别为n的节点相连的节点，其级别必然在[n-1,n+1]之间。（结论1）

那么，从一个级别为n的节点出发，得到的所有节点，其级别也只能在(n-1,n+1)之间。因此，得到如下的结论：

要判断从一个原始级别为n的节点产生的节点是否在图中已经存在，仅需要判断图中[n-1,n+1]级别的节点集合中是否有此节点即可，如果没有，那么此节点就是新节点。（结论2）

请注意上面所描述的结论2，根据结论2，在对于新产生节点是否重复的判断问题上，仅需要由本级节点上溯到上二极即可，而不需要一直上溯到最开始的节点。

这样，通过缩小对于新产生节点是否存在的判断范围，我们达到了对于广度优先算法的优化目的。

3、结论

在广度优先算法的搜索过程中，如果按照最短路径的规则进行搜索，那么对于每次搜索产生的新节点状态，只需要在其上两层进行回溯判断，就可以判断新节点状态是否重复，从而达到快速搜索的目的。这种对于广度优先算法的优化同样可以用于其它类似问题的求解，例如“八皇后问题”，迷宫行走问题，最短交通路线问题等等。

上一篇：ASP.NET心得笔记下一篇：利用VB解决华容道问题的源代码

【收藏】【评论】【推荐】【投稿】【打印】【关闭】