如果将游戏地图划分为子图，如何最小化子图之间的边？
我有一个问题，我试图通过像 pacman 或 sokoban 这样的基于网格的游戏进行 A* 搜索，但我需要找到“附件”。我说的外壳是什么意思？给定作为软约束的每个子图的顶点数的最大尺寸和最小尺寸，具有尽可能少的切割边的子图。
或者你可以说我正在寻找子图之间的桥梁，但它通常是同样的问题。
例子
基于网格的游戏地图示例 http://dl.dropbox.com/u/1029671/map1.jpg
给定一个看起来像这样的游戏，我想做的是找到外壳，这样我就可以正确地找到它们的入口，从而获得一个很好的启发式方法来到达这些外壳内的顶点。
替代文字 http://dl.dropbox.com/u/1029671/map.jpg
所以我想要的是在任何给定的地图上找到这些彩色区域。
我的动机
我之所以费心这样做，而不仅仅是满足于简单的曼哈顿距离启发式的性能，是因为封闭启发式可以提供更优化的结果，而且我不必实际执行 A* 来获得一些适当的距离计算和也用于以后在玩推箱子类型游戏时在这些围栏内增加对手的竞争性阻挡。此外，封闭启发式可用于极小极大方法，以更正确地找到目标顶点。
可能的解决方案
该问题的一个可能解决方案是Kernighan Lin 算法：
function Kernighan-Lin(G(V,E)):
determine a balanced initial partition of the nodes into sets A and B
do
A1 := A; B1 := B
compute D values for all a in A1 and b in B1
for (i := 1 to |V|/2)
find a[i] from A1 and b[i] from B1, such that g[i] = D[a[i]] + D[b[i]] - 2*c[a][b] is maximal
move a[i] to B1 and b[i] to A1
remove a[i] and b[i] from further consideration in this pass
update D values for the elements of A1 = A1 / a[i] and B1 = B1 / b[i]
end for
find k which maximizes g_max, the sum of g[1],...,g[k]
if (g_max > 0) then
Exchange a[1],a[2],...,a[k] with b[1],b[2],...,b[k]
until (g_max <= 0)
return G(V,E)
我对这个算法的问题是它的运行时间为 O(n^2 * lg(n))，我正在考虑将 A1 和 B1 中的节点限制在每个子图的边界，以减少完成的工作量。
我也不理解算法中的 c[a][b] 成本，如果 a 和 b 之间没有边是假定为 0 或无穷大的成本，或者我应该根据一些启发式方法创建边。
你知道当 a 和 b 之间没有边时 c[a][b] 应该是什么吗？您认为我的问题适合使用多级方法吗？为什么或者为什么不？您对如何减少使用 kernighan-lin 算法完成我的问题的工作有一个好主意吗？