6

如果将硬币放在一个网格上，并且只能翻转整行或整列，我们如何翻转硬币以获得最小的反面数量。

我尝试使用贪婪解决方案，在该解决方案中，我翻转尾部数量大于头部的行或列，并重复该过程，直到数字没有变化。但是我发现这种方法在某些时候并没有给我一个最佳的解决方案。

HHT
THH
THT

例如，如果硬币像上面那样放置，我按照下面的方式翻转硬币，得到的值是 3，但实际上答案是 2。

1. Flip the row 3
HHT
THH
HTH
2. Then there exists no row or column where the number of tails are greater than that of heads.
3. But if I flip the column 3, row 3, column 1, there exists a solution whose value is 2.
THH
HHT
HHH

所以，我认为上述算法不起作用。我应该使用什么方法和算法？

4

4 回答 4

6

首先让我们注意到，将同一行或列翻转两次或更多次是没有意义的（更好的解决方案总是将行/列翻转零次或一次），并且我们翻转行或列的顺序是无关紧要的，所以我们可以将解决方案描述为长度为 2N 的位数组。每行一位，每列一位。如果我们翻转该行/列一次，则打开，如果我们翻转它零次，则关闭。

所以我们需要搜索 2^(2N) 个可能的解决方案，更喜欢具有更多零的解决方案。

其次，让我们注意到，对于一种解决方案，硬币有四种可能的状态：

  1. 硬币未翻转（0 次翻转）
  2. 硬币被它的行翻转（1次翻转）
  3. 硬币被它的柱子翻转（1次翻转）
  4. 硬币被它的行和列翻转（2次翻转）

请注意，状态 1 和 4 导致硬币的原始价值

还要注意状态 2 和 3 的结果与硬币的原始价值相反

首先将硬币的原始状态表示为二进制矩阵 (B)。2N 位字段作为 2 个二进制向量 (R, C)，尾的总数作为 f(B, R, C) 的函数，总比特数作为函数 g(· V_1, · V_2)

因此，您的目标是使 f >= 最小化，同时最小化 g。

想想如果我们首先修复我们的 R 配置（我们将翻转哪些行），我们如何解决仅针对 C 的问题（我们将翻转哪些列）？换句话说，考虑更简单的问题，即只允许翻转列，不允许翻转行。你会如何解决这个问题？（提示：DP）你现在能把这个策略延伸回完整的问题吗？

于 2013-06-23T14:51:59.500 回答
0

不确定完整的算法，但您绝对应该在这里尝试利用的一件事是您的问题中存在大量对称性。

许多不同的硬币配置实际上是等效的，因此您可以旋转、镜像您的配置而不会改变问题。最重要的是，由于您可以通过翻转所有行来反转整个集合，因此寻找最小的尾部数量等同于寻找最小的正面数量。

在你的情况下，这将是

HHT
THH
THT

HTT
TTH
TTT

通过翻转中间列，你就完成了（如果你真的需要，你当然必须翻转所有东西）。

于 2013-06-23T14:19:22.827 回答
0

一个明显的解决方案是尝试翻转行或列的所有可能性。有O(2^(2N))这样的可能性。O(N^2 * 2^N)但是，我们可以通过贪婪+蛮力的组合来解决问题。

生成翻转行的所有可能性O(2^N)（采取给你最小尾巴的解决方案。

这应该有效。稍后我将添加有关原因的更多详细信息。

于 2013-06-23T14:38:37.187 回答
0

一种方法是使用http://en.wikipedia.org/wiki/Branch_and_bound，交替考虑新的垂直线和新的水平线。您还可以删除一些对称性 - 如果您翻转所有水平线和所有垂直线，您最终会回到您开始的位置，因此使用分支和绑定您可能会任意假设最左边的垂直线永远不会翻转.

HHT
THH
THT

在这个例子中，如果我们假设最左边的垂直线没有翻转，那么如果我们在最低的水平线上分支，我们就知道最左边的最低硬币的价值，所以我们有两个可能的部分解决方案 - 其中一个已知硬币固定在尾部，一种固定在头部。如果我们首先递归尝试扩展单个已知硬币为正面的部分解，并发现我们可以将其扩展为不产生反面的解，那么我们可以丢弃通过扩展另一个产生的所有部分解，因为所有它的后代必须至少有一条尾巴。

接下来，我将在最左边的一条垂直线上分支，这将给我们另一个已知的硬币，并继续水平和垂直交替分支。

如果存在近乎完美的解决方案或表格非常小​​，这将是一种找到精确解决方案的可行方法。否则，您将不得不提前停止它或让它跳过可靠的解决方案以在合理的时间内完成问题，并且您可能不会得到确切的最佳答案。

于 2013-06-23T15:35:09.537 回答