在阵列中相邻1的最小翻转次数

Question

给定二进制矩阵(值为0或1),相邻的1表示"丘陵".另外,给定一些数字k,找到你需要"翻转"为1的最小数量0,以便形成至少大小的山丘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

您的问题与直线斯坦纳树问题密切相关。

\n\n

斯坦纳树使用线段将一组点连接在一起，从而最小化线段的总长度。线段可以在任意位置相交，不一定在集合中的点相交（因此它与最小生成树不同）。例如，给定等边三角形角上的三个点，欧几里得施泰纳树通过在中间相交来连接它们：

\n\n

\n\n

直线斯坦纳树是相同的，只不过您最小化总曼哈顿距离而不是总欧几里德距离。

\n\n

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

\n\n

已知直线斯坦纳树问题是 NP 完全问题，即使仅限于具有整数坐标的点。您的问题是一个概括，除了两个区别：

\n\n

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

\n\n

这意味着您的问题可能是也可能不是 NP 困难问题，具体取决于直线斯坦纳树问题是弱 NP 完全问题还是强 NP 完全问题。我无法在文献中找到这个问题的明确答案，而且除了学术文献之外，关于这个问题的信息也很少。据我所知，至少似乎不存在已知的伪多项式时间算法。

\n\n

鉴于此，您最有可能的选择是某种回溯搜索精确的解决方案，或者应用启发式方法来获得“足够好”的解决方案。维基百科描述的一种可能的启发式方法是计算直线最小生成树，然后尝试使用迭代改进方法改进 RMST 。RMST 本身给出的解在真实最佳值的 1.5 常数因子内。

\n