问选择不相邻单元格:算法的时间复杂度
EN

Stack Overflow用户

提问于 2020-08-31 17:35:59

回答 1查看 76关注 0票数 5

有一个由N个1x1正方形组成的区域，并且区域的所有部分都是相连的(任何正方形都没有不可访问的正方形)。这里有一些面积的例子。

我想选择这个区域中的一些方块，并且不能同时选择两个相邻的方块(对角接触不是相邻的)。

我能在时间复杂度O(N)内找到选定方块的最大数量吗？我该怎么做呢？

非常感谢。

发布于 2020-08-31 17:45:41

您正在讨论的问题称为Maximum Independent Set。一般来说，它是NP难的，所以你不能指望一个有效的算法来找到最优解。

然而，最大独立集在所有一般性中都是关于选择图中的顶点的。你的问题是在网格中选择正方形；所以你的问题是最大独立集的一个特殊情况。希望仅限于您的特定情况的解决最大独立集可能比解决所有一般情况更容易。

事实证明，网格图是二部图。而限制在二部图上的最大独立集是很容易的！

在cs.stackexchange上有一个重复的问题：https://cs.stackexchange.com/questions/3022/maximum-independent-subset-of-2d-grid-subgraph。被接受的答案链接了一些算法。

谷歌搜索“网格上的最大独立集”也会给出一些有趣的结果。

票数 4

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/63668325

复制

相似问题

问选择不相邻单元格:算法的时间复杂度EN