如果游戏地图被划分为子图，如何最小化子图之间的边？
我有一个问题，我试图通过基于网格的游戏（如 pacman 或 sokoban）进行 A* 搜索，但我需要找到“外壳”。外壳是什么意思？子图尽可能少切边 http://en.wikipedia.org/wiki/Cut_(graph_theory)尽可能给定每个子图的顶点数量的最大尺寸和最小尺寸，作为软约束。
或者你可以说我正在寻找子图之间的桥梁，但它通常是同样的问题。
Example
基于网格的游戏地图示例http://dl.dropbox.com/u/1029671/map1.jpg http://dl.dropbox.com/u/1029671/map1.jpg
给定一个看起来像这样的游戏，我想要做的是找到外壳，以便我可以正确找到它们的入口，从而获得到达这些外壳内的顶点的良好启发式。
替代文本 http://dl.dropbox.com/u/1029671/map.jpg http://dl.dropbox.com/u/1029671/map.jpg
所以我想要的是在任何给定的地图上找到这些彩色区域。
我的动机
我之所以费心这样做，而不仅仅满足于简单的曼哈顿距离启发式的性能，是因为封闭式启发式可以给出更优化的结果，而且我不必实际执行 A* 来获得一些适当的距离计算和也可用于以后在玩推箱子类型游戏时在这些围栏内添加对对手的竞争性阻挡。此外，封闭启发式可用于极小极大方法，以更正确地查找目标顶点。
可能的解决方案
该问题的一个可能的解决方案是Kernighan Lin 算法 http://en.wikipedia.org/wiki/Kernighan%E2%80%93Lin_algorithm :
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 算法解决我的问题所做的工作，您有好主意吗？
