2

在今天的《卫报》（英国报纸）中，在 Chris Maslanka 第 43 页的“Pyrgic 谜题”部分，给出了以下谜题：

三位智者……去赫罗德做圣诞购物。Caspar 买了 Gold，Melchior 买了 Frankincense，Balthazar 买了一份Daily Myrrh。收银员输入了每件物品的欧元数，并打算将这三个数字相加，但是却将它们相乘。...令人惊奇的是，结果完全相同：65.52 欧元。三个总和是多少[我假设他的意思是三个数字]？

我的解释是：找到a、b和c使得a + b + c = abc = 65.52 （确切）其中a、b和c是不超过两位小数的正十进制数。因此a、b和c也必须小于 65.52（大约）。

因此，我的方法是：我将找到a、b和c的所有候选集，其中a + b + c = 6552 和a、b和c是 {1 ... 6550} 的整数（理论上我已经将所有操作数相乘为方便起见，减 100）。然后，对于所有候选集，通过将所有操作数除以 100 然后将它们相乘（使用任意精度算术）来满足另一个条件是微不足道的。

正如我所看到的，这是子集和问题的一个实例。所以我实现了一个脏（指数时间）算法，它找到了一个不同的解决方案：a=0.52，b=2，c=63。

好的，对于子集和问题有更好的算法，但你不认为这对于普通的卫报读者来说有点遥不可及吗？

第 40 页列出了答案：

这很容易，通过反复试验。猜猜每日没药的价格为 52 便士。但是乘以 0.52 大约是减半，所以我们需要一个和大约为 2；所以试试 2 X 63 X 0.52。等等瞧。这个答案是独一无二的吗？

好吧，我们知道答案是独一无二的（忽略 2、63 和 0.52 的其他排列）。

我想知道的是：这怎么可能“容易”？我将这个谜题描述为子集和问题的一个例子是否正确？我是否忽略了可用于简化解决方案的难题的某些特征？是否有人能够采用类似的“反复试验”方法，如果可以，他们可以带我完成吗？Chris Maslanka 是否对 NP 完全问题毫不畏惧？

4

1 回答 1

3

不，它不是子集和问题的一个实例，因为：

  1. 子集大小限制为 3，使其成为O(n^3)最坏情况的解决方案，使用天真的穷举搜索（而不是指数）
  2. 这里有额外的数据，数字的乘积。
  3. 您实际上并没有得到一个集合，所有整数的集合只是子集和的一个子问题，一个更容易的问题。

这里要理解的重要一点是：如果一个问题可以通过一个 NP-Hard 问题来解决——这并不意味着它也是 NP-Hard，反之亦然——如果你有一个问题，你可以解决一些NP-Hard问题（多项式），那么你的问题是NP-Hard。它被称为多项式归约1。

该方法很简单，因为您所要做的就是“猜测”（通过迭代所有候选者） 的值a，并且从中您可以推导出b, c- （2 个变量，两个方程，如果a已知）的可能解决方案 - 并且在每次迭代 - 它是），因此解决方案甚至是线性的 - 不仅仅是次指数。

它甚至可能被优化为使用二进制搜索的变体来获得亚线性优化，但我目前无法想到这种优化。

(1) 注意：这是一些直观的解释，而不是正式的定义。

于 2012-12-22T19:42:19.367 回答