algorithm - 是否总是存在蛮力方法？

Question

我经历了很多算法。我解决了很多编程问题并找到了解决单个问题的各种方法，可能从蛮力到最好的。

我想知道是否有任何问题无法使用蛮力方法解决但可以通过任何更好的方法解决？

Answer 1

如果已知解决方案存在（例如，如果它是一个优化问题）并且如果候选解决方案集是可枚举的（并且对于每个候选解决方案，您可以确定它是否正确，则存在蛮力算法或不）。

例如，无法确定的问题当然没有蛮力解决方案。

Answer 2

这取决于你的意思can。

对于几乎任何具有有限数量可能解决方案的问题，都有一个蛮力解决方案。给定足够的计算能力和/或时间，可以使用该解决方案来解决。

对于某些问题，实际上不可能使用蛮力解决方案，因为您没有足够的计算能力和/或时间。

在Euler Project的特定情况下，设计了许多问题，因此蛮力解决方案需要太多的计算能力和/或时间。例如，考虑到当前可用的计算机，一个问题可能被设计为需要一百万年的时间来计算，从而迫使您使用另一种方法来尽快完成它，从而使解决方案变得有用。

Answer 3

我想知道是否有任何问题无法使用蛮力方法解决但可以通过任何更好的方法解决？

是的。有时证明可判定性并非易事。

1) 平面度：

如何测试图形是否是平面的？天真地，你不能使用蛮力，因为你可以用无数种方法来绘制图形。

一旦你发现存在平面性的巧妙标准，算法就很简单了。

2）Presburger公式：

Presburger 算术中的公式是使用量词 ∀、∃、加法 +、常量（自然数）和逻辑运算符构建的。不允许有任何不同。量词的范围是自然数。

例子：

∀n ∃m (n = m + m) 或 (n = m + m + 1)

这个公式表达了每个整数都是偶数或奇数的事实。这是真的。

∃m ∀n ∃km + k = n

这个公式表达了存在最大自然数的事实。这是假的。

有没有一种算法可以决定一个公式是否正确？天真地，蛮力是行不通的，因为您需要检查所有自然数。不过，问题是可以确定的。

Answer 4

有很多问题是用蛮力解决不了的。

例如，看一下停止问题：您需要设计一个算法来接收程序和输入，如果程序在使用该输入运行时最终会停止，则返回“True”，否则返回“False”。

算法最终必须停止并告诉“假”或“真”。

不用说，但没有这样的算法。

编辑：

当您说“解决”时，我假设您的意思是计算解决。

我认为是的 - 看看以下问题：

给你循环：

而 (x < m)

x--

以及常数 m 和 k。并且您需要返回 < k 如果存在则循环将终止的最小 x ，否则返回“False”。使用蛮力算法，对于 k = 999 和 m = 1000，您将从 x = 999 开始（因为要求 x < k = 999）并且您将永远卡住。

您可以使用更好的方法 - 如果 m < k，则返回 m。否则，返回“假”。

Answer 5

显然是的，只要我们解决的是在某个离散空间上定义的问题并且存在非空解决方案集。

考虑以下：

1. 解决新问题的第一个算法是一种天真的蛮力方法。
2. 如果已经找到了，为什么有人还要寻找另一个？因为在离散问题中，蛮力意味着枚举输入值集，直到找到解决方案并具有 O(n!) 或 O( ^{an n} ) 计算复杂度。
3. 后者意味着它在实践中不可用并且需要更棘手的方法。或者，我们可能会寻找近似解而不是精确解，但这会引入收敛条件。
4. 最后有一个NP 完全问题类。

Answer 6

并不真地。蛮力的概念意味着尝试一切。因此，如果可以创建和重新创建某些东西以匹配，那么尝试所有可能的排列将导致找到另一个匹配项。