寻找最小割集有限子图之间 [英] 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.

由于游戏看起来像这样，我想要做的就是找​​到外壳，这样我可以准确地找到入口给他们，从而获得良好的启发，这些机箱内达到顶点。

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.

所以，我想是找到这些颜色的区域在任何给定的地图。

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的林算法：

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.

你知道什么是C [A] [B]应该是当有A和B之间没有边？ 你觉得我的问题是适合使用多层次的方法？为什么或为什么不？ 你有关于如何减少与Kernighan的林算法所做的工作我的问题是个好主意？

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.

有专业和高效的算法为最大流，你可以用它来解决了原始的。

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

然后需要获得的双的使用该技术的解决方案中描述的这里。

You then need to obtain the dual solution using the technique described here.

PS：让我知道如果你需要帮助运筹学的术语的

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

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