基于二维地图的连通路径快速查找算法

马春艳 崔鹏 金明日

摘 要：连通路径的关键问题是快速查找算法的问题，传统的算法往往效率不高，本文针对游戏连连看的连通路径问题，阐述了不同于以往的快速查找算法，该算法同时适用于在笛卡尔坐标系中的二维坐标平面内寻找在两次折线以内的连通路径，并明确给出了每次转折点的坐标，可以快速寻找出任意两点的连通路径。

关键词：连通路径；二维地图；快速算法

在各种应用中，经常面对两点的连通路径问题，以往的路径连通算法多为迭代式路径探索，直到寻找到满足条件的路径为止，这种算法的优点是算法简单，代码量少，但是缺点也是显著的，迭代次数太大，效率很低，尤其是当二维地图的信息量很大時，数据计算量非常惊人。本文阐述了游戏连连看的路径快速寻找算法，提高了算法的效率。

1 连连看游戏的连通路径规则

第一，两个结点图片内容相同；第二，两个结点图片所在的坐标之间可以在两次折线以内（包括两次）无障碍连通。

典型的连通路径如下：

2 快速算法

（1）首先确定要连通的两个结点以及他们在地图中的坐标，如下：A（3，4）和B（11，7）

⑵计算结点A的左、上、右、下四个方向上的空位直线排列组合，计算采用由结点中心坐标向四周延伸的方法，这样有助3 结论

在二维地图中寻找任意两点之间的连通路径问题，采用探路和迭代并不一定是最佳选择，根据需求的特点完全可以设计出简洁，快速高效的算法，可以提高应用程序的执行效率，使用户达到更好的体验。

[参考文献]

[1]王霄，等.基于多连通域Voronoi图的螺旋扫描路径算法.农业机械学报.2006.

[2]吴昊，等.几种电力网络图的连通路径拓扑算法研究.电力系统保护与控制.2009.

[3]王英杰，等.基于有效路径集合的节点间连通度估计方法研究.武汉理工大学学报.2009.

[4]2009 Thomas H.Cormen，Charles E.Leiserson，等.Intriduction Algorithms，Second Edition.北京：机械工业出版社.2006.

[5]龚劬.图论与网络最优化算法.重庆：重庆大学出版社.