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

Question

Given a binary matrix (values of 0 or 1), adjacent entries of 1 denote “hills”. Also, given some number k, find the minimum number of 0's you need to “flip” to 1 in order to form a hill of at least size k.

编辑:为澄清起见，相邻表示左右上下的邻域。对角线不算相邻。例如，

[0 1
0 1]

是一座大小为 2 的山，

[0 1
1 0]

定义 2 个大小为 1 的山，

[0 1
1 1]

定义 1 个大小为 3 的山

[1 1
1 1]

定义 1 个大小为 4 的山。

另外为了澄清起见，大小由相邻的 1 点形成的区域定义。

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

如果选择某些路径会降低另一条边的成本，并且解决此问题的解决方案(我能想到的)太接近于蛮力解决方案，则此方法会失败。

Answer 1

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

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

直线 Steiner 树是相同的，除了你最小化总数 Manhattan distance而不是总欧氏距离。

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

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

• 测量曼哈顿距离时的“负 1”部分。我怀疑这种细微差别是否足以将问题归入较低复杂度的类别，尽管我没有证据给你。
• 整数点的坐标受矩阵大小的限制(正如 Albert Hendriks 在评论中指出的那样)。这很重要——这意味着 pseudo-polynomial time对于直线斯坦纳树问题，您的问题将是多项式时间。

这意味着你的问题可能是也可能不是 NP-hard，这取决于直线斯坦纳树问题是否是 weakly NP-complete或 strongly NP-complete .我无法在文献中找到明确的答案，除了学术文献之外，没有太多关于这个问题的信息。据我所知，至少似乎没有已知的伪多项式时间算法。

鉴于此，您最有可能的选择是某种 backtracking search以获得精确的解决方案，或应用启发式方法来获得“足够好”的解决方案。一种可能的启发式 as described by Wikipedia是计算一个 rectilinear minimum spanning tree然后尝试使用 iterative improvement method 改进 RMST . RMST 本身给出了真实最优解的 1.5 常数因子内的解。