algorithm - 在二进制矩阵中找到最小成本

Question

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

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

我已经使用回溯并找到了O(2 ^ (n * n)). 有人可以帮我找到更有效的算法吗？

Answer 1

这个想法归功于 Greig、Porteous 和 Seheult。将矩阵视为容量有向图，其顶点对应于矩阵条目和从每个顶点到其四个邻居的弧，每个邻居的容量为b。引入另外两个顶点，一个源和一个接收器，以及容量为 a 的弧：从源到每个顶点，对应的条目为 0，从每个顶点到接收器，对应的条目为 1。找到最小割；变化后值为 0 的条目是切割源端的顶点，变化后值为 1 的条目是切割汇端的顶点。

这次削减的成本正是您的目标。在容量-a源弧中，穿过切口的弧对应于从 0 到 1 的变化。在容量-a到汇弧中，穿过切口的弧对应于从 1 到 0 的变化。b弧，穿过切口的弧对应于存在从 0 到 1 的弧的那些实例。

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) 中的问题。