algorithm - 在矩阵中获得相邻1的最小翻转次数

编辑:为澄清起见，neighbor表示左-右-上-下邻域。对角线不会而不是视为相邻。例如，
[0 1 0 1]
是二号山之一
[0 1 1 0]
定义2个大小为1的山丘
[0 1 1 1]
定义大小为3的1个山丘，并且
[1 1 1 1]
定义大小为4的1个山丘。

同样为了澄清起见，大小由相邻的1的 Blob 形成的面积定义。

我最初的解决方案与将每个现有的山转换为图的节点有关，而成本则是到达其他节点的最小路径。然后，执行DFS(或类似算法)以找到最低成本。

如果选择某些路径降低了另一条边的成本，而解决此问题的解决方案(我能想到的)与暴力解决方案过于接近，则此方法将失败。

最佳答案

您的问题与rectilinear Steiner tree problem密切相关。

Steiner tree使用线段将一组点连接在一起，从而使线段的总长度最小。线段可以在任意位置相遇，而不必在集合中的点相遇(因此，它与minimum spanning tree不同)。例如，给定一个等边三角形的角上的三个点，欧氏Steiner树通过在中间相遇来连接它们:



直线型Steiner树是相同的，只是您将总Manhattan distance而不是总欧几里德距离最小化。

在您的问题中，您不是通过将山丘与线段连接在一起，而线段的长度是通过欧几里得距离来测量的，而是通过添加像素来连接山丘。您需要翻转以连接数组中两个单元的总数为0，等于两个单元之间的曼哈顿距离，减去1。

直线型斯坦纳树问题is known to be NP-complete，即使仅限于具有整数坐标的点。您的问题是一个概括，只有两个区别:

测量曼哈顿距离时的“减1”部分。我怀疑这种微妙的区别是否足以将问题带入一个较低的复杂度类别，尽管我没有为您提供证明。

整数点的坐标以矩阵的大小为界(正如Albert Hendriks在评论中指出的那样)。这很重要-这意味着直线Steiner树问题的pseudo-polynomial time将是您问题的多项式时间。

这意味着您的问题可能不是NP难题，这取决于直线Steiner树问题是weakly NP-complete还是strongly NP-complete。在文献中，我找不到确切的答案，除了学术文献以外，关于该问题的信息也很少。据我所知，至少确实没有已知的伪多项式时间算法。

鉴于此，您最可能的选择是使用某种backtracking search作为精确解决方案，或者应用启发式方法以获得“足够好”的解决方案。一种可能的启发式as described by Wikipedia是计算rectilinear minimum spanning tree，然后尝试使用iterative improvement method改进RMST。 RMST本身可以在真正最佳值的1.5的恒定因子内提供解决方案。

关于algorithm - 在矩阵中获得相邻1的最小翻转次数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50722967/