algorithm - 选择不相邻的单元格 : algorithm's time complexity

Question

有一个由 N 个 1x1 方格组成的区域，并且该区域的所有部分都是相连的(没有任何方格无法到达的方格)。
下面是一些面积的例子。

我想在这个区域中选择一些方块，并且两个相邻的方块不能一起选择(对角接触是不相邻的)。
我可以在时间复杂度 O(N) 内找到最大数量的选定方块吗？我该怎么办？
非常感谢。

Answer 1

你说的问题叫Maximum Independent Set .总的来说，它是 NP 难的，所以你不能指望一个有效的算法来找到最好的解决方案。
然而，最大独立集一般来说都是关于选择图中的顶点。您的问题是在网格中选择正方形；所以你的问题是最大独立集的一个特例。希望解决仅限于您的特定情况的最大独立集可能比解决所有一般问题更容易。
事实证明，网格图是二部图。限制于二部图的最大独立集很容易!
这是关于 cs.stackexchange 的重复问题:https://cs.stackexchange.com/questions/3022/maximum-independent-subset-of-2d-grid-subgraph .接受的答案链接了一些算法。
谷歌搜索“网格上的最大独立集”也给出了一些有趣的结果。