找到包围2D网格上的区域的最短栅栏

Question

我有一个50 x 50的2D网格.网格单元可以具有以下三种状态之一:

1: "inside"
2: "empty"
3: "wall"

我的初始配置是一个网格,其中一些单元格(可能是其中的10%,大部分是连续的)标记为"内部".随机也有一些"墙"细胞.其他单元格是"空的".

我试图找到我可以围绕"内部"单元构建的最短栅栏,以便所有"内部"单元被围起来(围栏是通过将"空"单元改为"墙"单元构建的).如果我们对解决方案进行评分,那么最佳解决方案将最小化需要更改为"墙"单元的"空"单元的数量.

更严格地说,在最终配置中,存在约束,即对于每个"内部"单元,没有到达不通过"墙"单元的网格边缘的路径.就我而言,允许对角线移动.

我猜我可以做一些巧妙的涉及距离变换,或计算网格的拓扑骨架,但这对我来说并不是很明显.如果这是一个经典的优化问题,我不知道谷歌的条款.

是否有O(n ^ 2)算法来寻找最短的栅栏？

编辑:它不像找到"内部"单元格的凸包那么容易,因为预先存在的"墙"单元是自由的.想象一个"C"形的预先存在的墙块,在C的内部有所有"内部"单元格.大多数时候,用"墙"单元格完成C将比在所有墙上绘制凸包更便宜"内部"细胞.这就是使这个问题变得困难的原因.

Answer 1

真是个好问题!

正如@qwertyman所注意到的那样,问题是在"内部"单元和网格边界之间找到最小的顶点切口.虽然可以想象网格上的这个特殊问题可以有一个更容易的解决方案,但我不认为任何其他解决方案在所有情况下都能解决问题.

方形网格上的单元格可以看作最多有四个或最多八个邻居(@tobias_k和@hidefromkgb).如果我们忽视现有的(自由)墙单元,这就是4网格和8网格上典型的围栏:

并非在这两种情况下,都有更多的最小围栏,但这些矩形和八边形的边界框都很小,很容易找到.此外,它们是最小的围栏,最大的内部空间.

有两个并发症:免费预先存在的墙壁单元,以及多个小栅栏组件比一个大边界框便宜的可能性.

在最小的顶点切割问题中很好地解决了这两个并发症; 可以从图中删除预先存在的壁单元(并且内部单元可以与其他连接的内部单元合并,对于内部单元的每个连接组件仅留下一个内部单元).不幸的是,最小切割通常被认为是去除边缘而不是顶点!

我怀疑任何算法都比实现干净的顶点切割算法更容易.这是我们面临的问题:

在这个例子中,四个小栅栏比一个大栅栏便宜,但这取决于确切的比例.我们可以从一个大栅栏开始,尝试通过分区来改进它,就像@LazyMammal那样,或者分别对每个连接的组件进行隔离,但在任何一种情况下,这些情况都不是微不足道的.

这个也有问题:

我们要使用大型免费围栏吗？我们要分别围住每个小点吗？我们应该使用三个中等栅栏吗？无论我们是像@LazyMammal那样开始大而且分裂,还是从单个边界框开始加入它们,这些情况似乎都会出现一般最小削减正在解决的问题.

如果您对最佳解决方案的近似值没有问题,或者可能将自己限制在50×50网格的情况下并且可以快速排除这些复杂情况,那么可能有一些简单快速的方法吗？我不知道.

对于连接的内部单元格G,找到最便宜的围栏将如下工作:

• 找到从该组到边界的空单元格的最短"流"路径FL.

• 使用不在G或FL中的所有单元格在组中找到最便宜的"围栏"路径FE.尝试FL中的每个单元格作为起点,或者同时在FL和G的围栏中的任何单元格.空单元的成本是1,墙单元的成本是0,而不在G中的内单元的成本是0.你将不得不暂时沿FL切割网格以确保FE绕过G.

(但我不知道如何填充组中的空隙以连接其所有细胞 - 存在壁细胞.)

那么也许真正的问题是哪个内部细胞围在一起？连接的内部细胞必须保持连接,没关系.此外,如果任何最小的栅栏触摸,加入他们的组.除此之外,通过尝试不同的组合近似？

我不知道; 我认为大网格上的问题与一般的最小切割问题具有相同的复杂性和复杂性 - 所以如果你真的需要最优,那么解决这些问题.

相关:https://cstheory.stackexchange.com/questions/2877/(感谢qwertyman),https://en.wikipedia.org/wiki/Vertex_separator,其中包含"minimal"分隔符的不同概念.