在有界子图之间找到最小割集

Question

如果将游戏地图划分为子图，如何最小化子图之间的边缘？

我有一个问题，我正在尝试在基于网格的游戏（如吃豆人或推箱子）中进行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算法对我的问题所需的工作量？

- Tore

---

我不明白你是如何在第二张图片中准确地上色的。你的标准是什么？为什么黄色的斑块没有被细分？你是如何定义图形的？一个顶点是一个点，它的邻居是向北、南、东、西方向的（最多）四个点？ - ziggystar

是的，这就是我定义图形的方式，每个正方形（顶点）都有它的北、东、南和西邻居。图片只是为了说明，你可以将黄色、红色、黑色等分成几个闭合区域，这只是最大/最小顶点数约束规定了细分性质。因此，如果我的最小约束是8个顶点，那么黄色闭合区域将满足约束条件，但如果最小约束是4个，则它可能会停在盒子下面。我想要找到一种适用于多个地图和闭合区域的通用算法。 - Tore

您想将地图划分为子图。子图的大小必须遵守某些限制（最大、最小大小），并且分区之间的边数应最小化？ - ziggystar

那正是我想要做的。 - Tore

Kernighan Lin 在使用它处理 K 个不同的子图时给了我一些奇怪的解决方案。我认为这是因为我将图形分成 K 个子图的方式不同造成的。 - Tore

Answer 1

不确定问题是什么，但也许您可以使用最大流/最小割对偶性。

有专门且高效的算法可用于max-flow，您可以使用它们来解决原始问题。

然后，您需要使用此处描述的技术获取对偶解决方案。

附注：如果您需要帮助处理运筹学术语，请告诉我。

- baol

Answer 2

也许可以查看维基百科上的这个链接以获取更多阅读材料。

在数学中，图分割问题包括将一个图形分成若干部分，使得每个部分大小大致相同且部分之间的连接较少。

图分割

- ziggystar