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

Question

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

我有一个问题,我试图通过像pacman或sokoban这样的基于网格的游戏进行A*搜索,但我需要找到"附件".外壳是什么意思？用尽可能少子图切割边缘尽可能给出的每个充当软约束的子图的顶点的数目的最大尺寸和最小尺寸.
或者你可以说我希望找到子图之间的桥梁,但它通常是同样的问题.

---

例

基于网格的游戏地图示例http://dl.dropbox.com/u/1029671/map1.jpg

鉴于一个看起来像这样的游戏,我想要做的是找到外壳,以便我可以正确地找到它们的入口,从而获得一个良好的启发式,以达到这些外壳内的顶点.

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

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

---

我的动机

我打扰这样做的原因并不仅仅是坚持使用简单的曼哈顿距离启发式的表现,因为外壳启发式可以提供更优化的结果,我不必实际做A*以获得适当的距离计算和当玩sokoban类型的游戏时,也可以在以后为这些围栏中的对手添加竞争阻挡.外壳启发式也可用于最小化方法,以更正确地找到目标顶点.

可能解决方案

该问题的可能解决方案是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算法完成的工作有一个好主意吗？

Answer 1

也许看看维基百科上的这个链接以进一步阅读。

数学中的图划分问题包括将图划分为多个部分，使得各个部分的大小大致相同，并且各个部分之间几乎没有连接。

图分区