连连看游戏中的配对路径搜索

in  algorithm, thinking  , , ,

在连连看游戏中，两个图案可以消去的条件是：

  1. 两者图案相同。
  2. 两种直接存在一条通路，它是一条只经过没有图案的地方、且转折点不超过2个的折线。满足此条件的两个图案被称为是可相连的。

要判断条件1非常容易，所以主要考虑怎样判断条件2。举一个具体的例子如下，图中空格表示没有图案的地方，字母和#表示图案，-+|表示路径。

          
 ### ##A# 
 # ### |# 
 +-----+# 
 A#######

在这个例子中，A和A是可相连的。图中所给出的路径含有两个转折点。

对于此类问题，能否给出一个普遍的判断方法？在实际问题中（例如在连连看游戏里），如果判定两个图案是可相连的，还要指出一条具体的路径。

凡是遇到寻找路径的问题，首先想到的都是搜索算法。基本的搜索算法有DFS(深度优先搜索)和BFS(宽度优先搜索)。

经过一番思索，我认为运用BFS的思路，可以更加高效地求解这个特定的问题。具体的做法是：

  1. 以图中的起点为起点，向上下左右四个方向作射线。把射线上的所有点做上标记"0"，直到遇到如下情况为止： 1. 地图的边界(也标记上"0")； 2. 非空的格子位置(也标记上"0")； 3. 已经标记了数字的格子(不要标记了)。
  2. 分别以第1步中标记了"0"的空格子为起点，按照同样的规则作射线，标记"1"。
  3. 分别以第2步中标记了"1"的空格子为起点，按照同样的规则作射线，标记"2"。
  4. 最后检查图中的终点位置是否做了标记。如果做了标记，说明起点到终点是可相连的，并且转折点的个数等于标记的数字。如果没有标记，说明起点到终点不可相连。

这个算法实质上是限制了BFS的迭代次数，如果像2, 3这样的步骤被不停的重复，那么最终得到的就是从起点出发，不限转折次数，可达的所有位置。

即便是使用DFS，也可以把“转折点不超过两个”作为剪枝条件，相当于限制了搜索深度。上述算法的高效性主要体现在，它保证每个格子至多访问一次。而DFS只能确保每个路径至多产生一次。一般说来，两点之间可能会存在多条路径，所以DFS要做的尝试工作比BFS要多。

朴素的DFS算法在两点不可相连时是最糟糕的，试想如下的场景：

                 
  A              
     #######     
     #     #     
     #  A  #     
     #     #     
     #######

虽然肉眼一看便知，两点是不可相连的。但是由一堆半导体零件构成的电路并没有我们这么敏锐的脑瓜子、嘴皮子、笔杆子(好像哪里不对)；它还是得千方百计想遍、千山万水走遍、千辛万苦吃遍、千言万语……跑题了，总之就是每一条路径都走一遍，才发现原来都走不通。

连连看的游戏的规则是转折点不能超过2个。这个条件比较强，再加上连连看游戏的地图本来就不大，在实际的游戏程序中，采取什么样的算法，可能不是非常关键的问题。两种算法的比较，我还没有做过精确的的分析或者实验。可以确定的是，如果地图扩大，或者放宽转折点个数的要求，那么BFS的做法可以维持原有的效率，而朴素DFS的搜索效率则会急剧下降。(地图扩大或者放宽转折点的要求，也许就意味着这个算法从游戏中走出来，进入到工业中，作为某种大规模的实际问题的模型。)

有意思的是，如果对转折点的个数没有任何要求，那么BFS和DFS的效率是一样的。(这是一个基础的图遍历问题。)DFS算法在这里具有高效率是因为它使用了记忆化的方法，保证不会再走之前走过的格子。所以我想，在有转折点个数限制的情况下，如果适当运用一些记忆化的手段(例如，维护每个格子的“已知的可达路径的最小转折点数”信息)，应该也可以增强DFS的剪枝能力，从而提高搜索效率。但是应该能看到，BFS算法中，不需要刻意维护这个数据；它是在BFS的过程中自然而然得到的。所以就算法本质而言，BFS更加匹配这个特定的问题。

分享