c++ - 通过贪心算法找到最小移动数

Question

有一个二维网格，其中包含随机单元格中的巧克力。在一次移动中，我可以取出一行或一列中包含的所有巧克力。取出所有巧克力所需的最小移动次数是多少？

示例：含有巧克力的细胞是：

0 0
1 1
2 2

分钟。移动次数=3

0 0
1 0
0 1

最小移动次数=2

我想这个问题有一个贪婪的算法解决方案。但是如何解决这个问题呢？

Answer 1

对于这个特定问题，它不是 NP 难的。它可以在多项式时间内求解。解决方案如下：

将二维网格转换为二分图。左侧包含节点表示行，右侧包含节点表示列。对于每个包含巧克力的单元格，假设它的坐标是 (x,y)，添加一条连接 row_x 和 column_y 的边。二分图建立后，使用匈牙利算法得到最大匹配。由于在二分图中，最大匹配的答案等于最小顶点覆盖，所以答案正是您想要的。

匈牙利算法是 O(V*E) 算法。更多细节请参考匈牙利算法

有关二分图的更多信息，请参阅二分图，您可以在此处找到最大匹配等于最小顶点覆盖的原因。

PS：既不是贪心问题，也不是动态规划问题。这是一个图形问题。

Answer 2

我认为这是经典Set Cover问题的变体，被证明是 NP 难的。

因此，贪心算法只能得到一个近似值，而不能得到最优解。