我有一个数学问题，我通过反复试验来解决(我认为这称为蛮力)，当有几个选项时，程序运行良好，但是当我添加更多变量/数据时，它需要越来越长的运行时间。
我的问题是，尽管原型(prototype)可以工作，但它对数千个变量和大型数据集很有用；所以，我想知道是否可以扩展蛮力算法。我该如何扩展它？
我开始学习和玩 Hadoop (和 HBase)；虽然看起来很有希望，但我想验证我正在尝试做的事情并非不可能。
如果有帮助，我用 Java 编写了程序(如果可能的话，可以使用它)，但最终将它移植到 Python，因为我觉得它更舒服。
更新:为了提供更多见解，我想我会添加一个简化版本的代码来理解这个想法。基本上，如果我知道总和是 100，我会尝试找到可能等于它的变量的所有组合。这很简单，在我的版本中，我可能会使用更大的数字和更多的变量。这是丢番图，我相信没有算法可以在没有蛮力的情况下解决它。
int sum = 100;
int a1 = 20;
int a2 = 5;
int a3 = 10;
for (int i = 0; i * a1 <= sum; i++) {
for (int j = 0; i * a1 + j * a2 <= sum; j++) {
for (int k = 0; i * a1 + j * a2 + k * a3 <= sum; k++) {
if (i * a1 + j * a2 + k * a3 == sum) {
System.out.println(i + "," + j + "," + k);
}
}
}
}
我是编程新手，如果我没有正确地提出这个问题，我很抱歉。这更像是一个普遍的问题。
最佳答案
通常，您可以通过使用大 O 符号来分析算法的增长率来量化算法的可扩展性。当你说你的算法通过“蛮力”工作时，不清楚它会扩展到什么程度。如果您的“蛮力”解决方案通过列出一组数据的所有可能的子集或组合来工作，那么它几乎肯定不会扩展(它将分别具有渐近复杂度 O(2n) 或 O(n!))。如果您的蛮力解决方案通过查找所有元素对并检查每个元素来工作，则它可以合理地扩展(O(n2))。但是，如果没有关于您的算法如何工作的更多信息，就很难说。
你可能想看看 this excellent post about big-O作为如何推理程序长期可扩展性的起点。通常来说，任何具有 O(n log n)、O(n)、O(log n) 或 O(1) 增长率的东西都可以很好地扩展，任何增长率为 O(n2) 或 O(n3) 的东西都可以扩展在一定程度上，任何增长率为 O(2n) 或更高的东西都不会扩展。
另一种选择是查找您正在尝试解决的问题，以了解它的研究情况。众所周知，有些问题有很好的解决方案，如果您是其中之一，那么可能值得看看其他人提出了什么。也许有一个非常干净的非蛮力解决方案，可以很好地扩展!推测其他一些问题根本没有可扩展的算法(所谓的 NP-hard problems )。如果是这种情况，那么您应该非常确信没有办法获得可扩展的方法。
最后，您可以随时在 Stack Overflow 上提出一个新问题，描述您正在尝试做什么并征求意见。也许社区可以比您最初预期的更有效地帮助您解决问题!
编辑:鉴于您尝试解决的问题的描述，现在您正在为每个变量执行一个 for 循环，从 0 到您尝试定位的数字。该算法的复杂度为 O(Uk)，其中 k 是变量的数量，U 是总和。这种方法将不是 完全可以很好地扩展。在上面的例子中引入每个新变量会使 algori2thm 运行速度慢 100 倍，如果你想要 100 个变量，这肯定不会很好地扩展!
但是，我认为有一个相当不错的算法，其运行时间为 O(U2k)，它使用 O(Uk) 内存来解决问题。直觉是这样的:假设我们想把 1、2、4 相加得到 10。有很多方法可以做到这一点:
2 * 4 + 1 * 2 + 0 * 1
2 * 4 + 0 * 2 + 2 * 1
1 * 4 + 3 * 2 + 0 * 1
1 * 4 + 2 * 2 + 2 * 1
1 * 4 + 1 * 2 + 4 * 1
1 * 4 + 0 * 2 + 6 * 1
0 * 4 + 5 * 2 + 0 * 1
0 * 4 + 4 * 2 + 2 * 1
0 * 4 + 3 * 2 + 4 * 1
0 * 4 + 2 * 2 + 6 * 1
0 * 4 + 1 * 2 + 8 * 1
0 * 4 + 0 * 2 + 10 * 1
关键的观察是我们可以将所有这些写成总和，但更重要的是，作为总和中的每一项都不大于前一项的总和:
2 * 4 + 1 * 2 + 0 * 1 = 4 + 4 + 2
2 * 4 + 0 * 2 + 2 * 1 = 4 + 4 + 1 + 1
1 * 4 + 3 * 2 + 0 * 1 = 4 + 2 + 2 + 2
1 * 4 + 2 * 2 + 2 * 1 = 4 + 2 + 2 + 1 + 1
1 * 4 + 1 * 2 + 4 * 1 = 4 + 2 + 1 + 1 + 1 + 1
1 * 4 + 0 * 2 + 6 * 1 = 4 + 1 + 1 + 1 + 1 + 1 + 1
0 * 4 + 5 * 2 + 0 * 1 = 2 + 2 + 2 + 2 + 2
0 * 4 + 4 * 2 + 2 * 1 = 2 + 2 + 2 + 2 + 1 + 1
0 * 4 + 3 * 2 + 4 * 1 = 2 + 2 + 2 + 1 + 1 + 1 + 1
0 * 4 + 2 * 2 + 6 * 1 = 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
0 * 4 + 1 * 2 + 8 * 1 = 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
0 * 4 + 0 * 2 + 10 * 1 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
所以这给出了一个有趣的想法，即如何生成所有可能的方法来总结目标。这个想法是固定第一个系数，然后生成所有可能的方法来使和的其余部分工作。换句话说，我们可以递归地思考这个问题。如果我们按照x1, x2, ..., xn 的顺序列出变量，那么我们可以尝试为x1 固定一些特定的系数，然后解决求和
sum - c_1 x_1 的问题。仅使用 x2, ..., xn。到目前为止，这看起来并不那么花哨——事实上，这正是你在上面所做的——但我们可以使用一个技巧。只要我们要递归地思考这个问题，让我们以相反的方式思考这个问题。而不是以
sum 开头并试图分解它，如果我们从 0 开始并尝试构建我们可以构建的所有东西呢？这是想法。假设我们已经预先知道仅使用 x1 的总和就可以得出的所有数字。然后对于 0 和
sum 之间的每个数字 k ，包括在内，我们可以从 x2 和 x1 的任何组合中生成 k，其中 k - c2 x2 是可以从 x1 的组合中生成的东西。但是因为我们已经预先计算了这个，我们可以迭代 c2 的所有可能的合法值，计算 k - c2 x2，看看我们是否知道如何制作它。假设我们存储了一个巨大的 U x (k + 1) bool 值表，这样表条目 [x, y] 存储“我们可以总结第一个 y 值，包括，以精确地总结为 U 的方式？，”我们可以有效地填写表格。这称为动态规划，是一种强大的算法工具。更具体地说，这可能是如何工作的。给定 k 个变量，创建一个 U x (k + 1) 值表 T。然后，为所有 x > 0 设置 T[0][0] = true 和 T[x][0] = false。这里的基本原理是 T[0][0] 表示“我们可以使用第一个零变量的线性组合？”答案肯定是肯定的(空和为零!)，但是对于由 no 组成的任何其他和，没有变量的线性组合，我们绝对无法做到。
现在，对于 i = 1 .. k，我们将尝试填充 T[x][i] 的值。还记得 T[x][i] 的意思是“我们可以让 x 作为前 i 个变量的线性组合吗？”好吧，我们知道我们可以这样做，如果存在某个系数 c 使得 k - c xi 可以使用 x1, x2, ..., xi - 1 的线性组合得到。但是对于任何 c，这只是 T [x - c xi][i - 1] 为真。因此我们可以说
for i = 1 to k
for z = 0 to sum:
for c = 1 to z / x_i:
if T[z - c * x_i][i - 1] is true:
set T[z][i] to true
检查循环，我们看到外循环运行了 k 次，内循环运行了
sum每次迭代次数，最里面的循环也最多运行 sum每次迭代次数。他们的产品是(使用我们上面的符号)O(U2 k)，这比您最初使用的 O(Uk) 算法要好得多。但是您如何使用这些信息列出所有可能的方法来总结目标？这里的诀窍是要意识到您可以使用该表来避免在搜索每个可能的组合时浪费大量精力，因为其中许多组合都不起作用。
让我们看一个例子。假设我们已经完全计算了这个表并且想要列出所有解决方案。一个想法是考虑列出最后一个变量的系数为零的所有解决方案，然后当最后一个变量为 1 时，等等。您之前使用的方法的问题是对于某些系数可能根本没有任何解决方案.但是使用我们上面构建的表，我们可以修剪掉这些分支。例如，假设我们想看看是否有任何以 xk 开头的系数为 0 的解。这意味着我们要问是否有任何方法可以对前 k - 1 个变量的线性组合求和，以便这些值的总和是
sum .当且仅当 T[sum][k - 1] 为真时，这是可能的。如果为真，那么我们可以递归地尝试以总和为 sum 的方式将系数分配给其余的值。 .如果不是，那么我们跳过这个系数并继续下一个。递归地，这看起来像这样:
function RecursivelyListAllThatWork(k, sum) // Using last k variables, make sum
/* Base case: If we've assigned all the variables correctly, list this
* solution.
*/
if k == 0:
print what we have so far
return
/* Recursive step: Try all coefficients, but only if they work. */
for c = 0 to sum / x_k:
if T[sum - c * x_k][k - 1] is true:
mark the coefficient of x_k to be c
call RecursivelyListAllThatWork(k - 1, sum - c * x_k)
unmark the coefficient of x_k
这将递归地列出所有有效的解决方案，使用我们刚刚构建的表中的值来跳过大量浪费的工作。一旦你建立了这个表，你可以通过将任务分给多台计算机来分配这项工作，让它们每台列出总解决方案的一个子集，并并行处理它们。
希望这可以帮助!
关于algorithm - 蛮力算法可以扩展吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7265576/