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

Question

给定二进制矩阵（值为0或1），相邻的1表示“山丘”。另外，给定一些数字k，则找到至少需要翻转0的最小数量，以形成大小为k的山丘。 编辑: 为了澄清，相邻表示左右上下邻居。 对角线不算作相邻。例如，

[0 1 0 1]

是大小为2的一个山丘，

[0 1 1 0]

定义了大小为1的2个山丘，

[0 1 1 1]

定义了大小为3的1个山丘，并且

[1 1 1 1]

定义了大小为4的1个山丘。

此外，澄清一下，大小由相邻的1组成的区域定义。

我的初始解决方案涉及将每个现有山丘转换为图的节点，并将代价设置为到每个其他节点的最小路径。然后，执行DFS（或类似的算法）以查找最小成本。

这在选择某些路径降低另一个边缘的成本的情况下失败，而解决这个问题的解决方案（我能想到的）与暴力解决方案过于接近。

- The Monkey

---

邻接是如何定义的？左右上下，还是包括角落？ - Thomas Cohn

那么如何定义山丘呢？大小为2的山丘是否有两个垂直相邻的1（像尖峰一样）？您需要向我们展示一个具有一些这样的“山丘”的示例矩阵。 - Jim Mischel

已更新。对于不明确之处表示抱歉。 - The Monkey

一个带有一个在上方和一个在左侧的 1 的 1（总共三个 1）有多少山丘和大小？ - גלעד ברקן

看起来像是对于 Steiner 树问题的修改。 - DAle

Answer 1

你的问题与直线Steiner树问题密切相关。 Steiner树是使用线段将一组点连接在一起，使线段的总长度最小。线段可以在任意位置相遇，不一定在集合中的点上（因此它与最小生成树不同）。例如，给定一个等边三角形的三个角上的三个点，欧几里得Steiner树通过在中间相遇将它们连接在一起：

一个矩形斯坦纳树与之相同，只是你需要最小化总曼哈顿距离而不是总欧几里得距离。

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

矩形斯坦纳树问题已知是NP完全问题，即使限制在整数坐标点上也是如此。你的问题是一个泛化问题，除了两个区别:

• 曼哈顿距离测量中的“减1”部分。我怀疑这种微妙的差异是否足以将问题降到更低的复杂度类别，尽管我没有证据可以证明。
• 您整数点的坐标受矩阵大小的限制（正如Albert Hendriks在评论中指出的那样）。这很重要-这意味着pseudo-polynomial time对于直角斯坦纳树问题来说是多项式时间，而对于您的问题则不一定是NP难问题。

这意味着您的问题可能是NP难问题，也可能不是，这取决于直角斯坦纳树问题是弱NP完全还是强NP完全。我无法在文献中找到明确的答案，并且除了学术文献外，关于该问题的信息很少。至少看起来，据我所知，没有已知的伪多项式时间算法。

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

- kaya3

---

在矩形斯泰纳树和OP问题之间有一个更重要的区别：OP问题使用密集矩阵表示，而斯泰纳树使用稀疏矩阵表示。换句话说，OP问题类似于2D矩形斯泰纳树，但整数坐标被O(log n)限制。 - Albert Hendriks

@AlbertHendriks 那是个好观点。你能解释一下O(log n)的限制吗？ - kaya3

@AlbertHendriks 是的，那似乎是正确的，谢谢！我已经编辑过了。我找不到一个明确的答案来确定它是弱 NP 完全问题还是强 NP 完全问题，但实际上，如果没有明确的答案，那么就没有已知的伪多项式时间算法可以改编成 OP 问题的多项式时间算法。所以我认为我的结论仍然成立，但我对此有些不确定，因为我可能在文献中漏掉了一些东西。 - kaya3

请原谅我的愚钝，感谢您的解释，但我仍然不明白为什么我们需要斯坦纳树的想法。例如，如果 k = 4，我们有一个大小为2的山丘离另一个像素只有一个像素的距离，以及1000个大小为2的山丘星座，每个山丘星座都比任何其他山丘都要远超过一个像素，我们可以通过连接距离单个像素一个像素的那个山丘来解决问题。斯坦纳树在这里如何使用？ - גלעד ברקן

@גלעדברקן 重点不在于您可以使用直角斯坦纳树算法解决所有制造山丘问题的情况；相反，情况正好相反。您可以使用制造山丘算法来（有点）解决直角斯坦纳树问题，因为它（大致上）是制造山丘问题的一个特殊情况。这意味着，在一般情况下，制造山丘至少与查找斯坦纳树一样困难，这提供了关于哪种算法可能或可能不起作用的一些信息（例如，任何贪婪算法肯定不是精确的）。 - kaya3

Answer 2

一个山由四个连续的1序列组成：

正确的序列由r个“位”组成，上升序列有u个位，依此类推。

大小为k的山是k = 1 + r + l + u + d（1个中心+序列），其中每个值都是0 <= v < k。

问题是组合问题。对于每个单元格，应测试满足前述关系的所有可能的{r，l，u，d}组合。

在测试单元格中的组合时，必须计算组合中每个值中现有1的数量，它们不会“翻转”。这也将提前跳过一些其他组合。

- Ripi2

---

1. 你正在限制问题，“相邻的1表示‘山峰’”与你的陈述不同：“一个山峰由四个1序列组成”。
2. 这个问题有组合解决方案，并不意味着你必须枚举所有组合，除非你证明了这一点。

- fjardon

想象一下 1 的正方形。根据 OP 的说法，这是一个大小为 4 的山丘。但不符合您的定义。 - fjardon

@fjardon 也许你是对的，也许不是。原帖中的示例并没有清楚地说明对角线。而“相邻”的定义也不够明确。 - Ripi2

引用原帖：“相邻指左右上下的邻居”。因此，很明显，大小为1的正方形是大小为4的山丘。 - fjardon

@fjardon 抱歉，我只能理解“左”或“右”或“上”或“下”，而不能像“左+上”这样组合。但是这句话并不排除您的观点。 - Ripi2