algorithm - 寻找有界子图之间的最小割集

Question

如果游戏 map 被划分为子图，如何最小化子图之间的边？

我有一个问题，我正在尝试通过吃 bean 或推箱子等基于网格的游戏进行 A* 搜索，但我需要找到“附件”。外壳是什么意思？尽可能少的子图 cut edges尽可能给定每个子图的顶点数的最大尺寸和最小尺寸作为软约束。
或者你可以说我正在寻找子图之间的桥梁，但这通常是同一个问题。

---

例子

Gridbased gamemap example http://dl.dropbox.com/u/1029671/map1.jpg

给定一个看起来像这样的游戏，我想做的是找到围栏，这样我就可以正确地找到它们的入口，从而获得一个很好的启发式方法来到达这些围栏内的顶点。

alt text http://dl.dropbox.com/u/1029671/map.jpg

所以我想要的是在任何给定的 map 上找到这些彩色区域。

---

我的动力

我费心这样做而不只是满足于简单的曼哈顿距离启发式算法的性能的原因是，封闭式启发式算法可以提供更优的结果，而且我不必实际执行 A* 来获得一些合适的结果距离计算以及以后在玩推箱子类型的游戏时在这些围栏内添加对手的竞争性阻挡。封闭式启发式也可用于极小极大方法，以更正确地找到目标顶点。

可能的解决方案

该问题的可能解决方案是 Kernighan Lin 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 算法为我的问题完成的工作，您有什么好主意吗？

Answer 1

不确定这个问题，但也许你可以使用最大流/最小割对偶。

max-flow 有专门高效的算法你可以用它来解决原始问题。

然后您需要使用 here 中描述的技术获得对偶 解决方案.

PS:如果您需要运筹学行话方面的帮助，请告诉我。