在有界子图之间寻找最小割集 [英] Finding minimum cut-sets between bounded subgraphs

问题描述

我遇到了一个问题，我试图通过像吃豆子或推箱子这样的基于网格的游戏进行 A* 搜索，但我需要找到外壳".我说的外壳是什么意思?给定最大尺寸和最小数字尺寸的子图，尽可能少 切割边作为软约束的每个子图的顶点数.
或者你可以说我正在寻找子图之间的桥梁，但它通常是相同的问题.

I have a problem, Im trying to make A* searches through a grid based game like pacman or sokoban, but i need to find "enclosures". What do i mean by enclosures? subgraphs with as few cut edges as possible given a maximum size and minimum size for number of vertices for each subgraph that act as a soft constraints.
Alternatively you could say i am looking to find bridges between subgraphs, but its generally the same problem.

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

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

Given a game that looks like this, what i want to do is find enclosures so that i can properly find entrances to them and thus get a good heuristic for reaching vertices inside these enclosures.

替代文字 http://dl.dropbox.com/u/1029671/map.jpg

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

So what i want is to find these colored regions on any given map.

让我费心这样做而不只是满足于简单曼哈顿距离启发式的性能的原因是外壳启发式可以提供更优化的结果，我实际上不必做 A* 来获得一些正确的结果距离计算，以及稍后在玩推箱子类游戏时在这些围场内增加对手的竞争性阻挡.此外，外壳启发式算法可用于更恰当地寻找目标顶点的极小极大方法.

The reason for me bothering to do this and not just staying content with the performance of a simple manhattan distance heuristic is that an enclosure heuristic can give more optimal results and i would not have to actually do the A* to get some proper distance calculations and also for later adding competitive blocking of opponents within these enclosures when playing sokoban type games. Also the enclosure heuristic can be used for a minimax approach to finding goal vertices more properly.

该问题的一个可能解决方案是 Kernighan Lin 算法:

A possible solution to the problem is the 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 中的节点限制在每个子图的边界以减少完成的工作量.

My problem with this algorithm is its runtime at O(n^2 * lg(n)), i am thinking of limiting the nodes in A1 and B1 to the border of each subgraph to reduce the amount of work done.

我也不明白算法中的 c[a][b] 成本，如果 a 和 b 之间没有边是假设成本为 0 或无穷大，或者我应该基于某些创建边启发式.

I also dont understand the c[a][b] cost in the algorithm, if a and b do not have an edge between them is the cost assumed to be 0 or infinity, or should i create an edge based on some heuristic.

当 a 和 b 之间没有边时，你知道 c[a][b] 应该是什么吗?您认为我的问题适合使用多级方法吗?为什么或者为什么不?对于如何减少使用 kernighan-lin 算法为我的问题所做的工作，您有什么好主意吗?

Do you know what c[a][b] is supposed to be when there is no edge between a and b? Do you think my problem is suitable to use a multi level method? Why or why not? Do you have a good idea for how to reduce the work done with the kernighan-lin algorithm for my problem?

推荐答案

不确定问题，但也许您可以使用最大流量/最小切割对偶性.

Not sure of the question, but perhaps you can use the max-flow/min-cut duality.

您可以使用针对 max-flow 的专门且高效的算法解决原始问题.

There are specialized and efficient algorithms for the max-flow that you can use to solve the primal.

然后您需要使用这里.

PS:如果您需要有关运筹学的帮助行话，请告诉我.

PS: let me know if you need help with Operations Research jargon.

这篇关于在有界子图之间寻找最小割集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！