在二进制矩阵中寻找最小成本

Question

考虑一个 n * n 的二进制矩阵。每个单元格最多有4个邻居（如果存在）。 如果它们是邻居并且它们的值不相等，则我们称这个矩阵的两个单元格不兼容。 我们为每一对不兼容的单元格支付 $b。此外，我们可以更改该单元格的值并支付 $a。

问题是找到此矩阵的最小成本。

我已经使用回溯法，并找出了一个O(2 ^ (n * n))的算法。 有人能帮我找到一个更有效的算法吗？

- Stranger

---

你是在寻找最优解吗？还是可以使用启发式算法？似乎遗传算法和/或爬山算法可以快速带来不错的结果。 - amit

@Jack Newton，你能提供任何二进制矩阵的图像吗？矩阵如何由4个邻居而不是8个组成？ - Muthu Ganapathy Nathan

我认为他指的是上方、左侧、右侧和下方的邻居。 - Aravind

@EAGER_STUDENT 这只是因为将邻域定义为4连通而不是8连通。也就是说，邻居是上下和两侧的单元格，而不是沿对角线的单元格。请参见此链接。（它讨论的是像素，但是相同的概念适用。） - Imre Kerr

你对算法有多熟练？听起来这个问题可能需要动态规划的解决方案，但这需要一定的专业知识和/或阅读能力。 - cgledezma

Answer 1

这个想法源于 Greig、Porteous 和 Seheult。将矩阵视为容量有限的有向图，其中每个顶点对应于矩阵条目，并且从每个顶点到其四个邻居之间存在弧，每个弧都具有容量 b 。引入两个额外的顶点 - 源和汇 - 并且容量为 a 的弧：从源到具有相应0条目的每个顶点，以及从具有相应1条目的每个顶点到汇。找到最小割；变化后值为0的条目是割的源侧的顶点，而变化后值为1的条目是割的汇侧的顶点。

这个割的代价恰好是你的目标。对于从源到汇的容量为a的弧，穿过割的那些弧对应于从0到1的更改。对于容量为 a 的到汇弧，穿过割的那些弧对应于从1到0的更改。对于容量为 b 的弧，穿过割的那些弧对应于存在从0到1的弧的那些情况。

- David Eisenstat

Answer 2

我建议您重新构思回溯算法，以使用动态规划来修剪回溯树。这是我提出的设计逻辑：

在决定是否更改单元格时，先前分配的单元格如何并不重要，只有累积成本才重要，因此您可以为每个单元格和每个可能的累积成本跟踪已找到的最小结果。这样，每当您再次找到相同的配置时，您将保存答案。

因此，您的dp矩阵应该类似于：

dp[top_bound][n][n];

在进行回溯之前，您应该执行以下操作：

if(dp[acc_cost][this_i][this_j] != -1)
    return dp[acc_cost][this_i][this_j];

// Perform your calculations
// ...

dp[acc_cost][this_i][this_j] = result;
return result;

在这里，我假设-1是结果中的无效值，如果不是，则选择任何无效值并将矩阵初始化为它。由于该矩阵的大小为n * n * top_bound，因此正确实现的DP应该在O（n * n * top_bound）内解决问题。

- cgledezma