蛮力算法可以扩展吗？

Question

我有一个数学问题,我通过反复试验解决(我认为这被称为暴力),当有一些选项时程序工作正常,但是当我添加更多变量/数据时,运行时间越来越长.

我的问题是,虽然原型工作,它对数以千计的变量和大数据集很有用; 所以,我想知道是否有可能扩展蛮力算法.我该如何进行缩放？

我开始学习和玩Hadoop(和HBase); 虽然它看起来很有希望,但我想验证我正在尝试做的事情并非不可能.

如果它有帮助,我用Java编写程序(并且如果可能的话可以使用它),但最终将它移植到Python,因为我觉得它更舒服.

更新:为了提供更多洞察力,我想我会添加一个简化版本的代码来实现这个想法.基本上如果我知道总和是100,我试图找到可以等于它的所有变量组合.这很简单,在我的版本中我可能会使用更大的数字和更多的变量.它是Diophantine,我相信没有算法可以在没有蛮力的情况下解决它.

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);
            }
        }
    }   
}

我是编程的新手,如果我没有正确地构思这个问题,我很抱歉.这是一个普遍的问题.

Answer 1

通常,您可以使用big-O表示法来分析其增长率,从而量化算法的扩展程度.当你说你的算法通过"蛮力"工作时,它不清楚它将在多大程度上扩展.如果你的"暴力"解决方案通过列出所有可能的子集或一组数据的组合来工作,那么它几乎肯定不会扩展(它将分别具有渐近复杂度O(2 ⁿ)或O(n!)).如果您的暴力解决方案通过查找所有元素对并检查每个元素来工作,那么它可以很好地扩展(O(n ²)).但是,如果没有关于算法如何工作的更多信息,则很难说.

你可能想看看这篇关于big-O的优秀帖子,作为如何推理你的程序的长期可扩展性的起点.通常来说,任何具有增长率O(n log n),O(n),O(log n)或O(1)的东西都能很好地扩展,任何具有增长率O(n ²)或O(n ³)的东西将扩大到一定程度,任何增长率为O(2 ⁿ)或更高的东西都不会扩展.

另一个选择是查找你试图解决的问题,看看它是如何进行深入研究的.众所周知,有些问题有很好的解决方案,如果你的问题是其中之一,可能值得看看别人提出的问题.也许有一个非常干净,非暴力的解决方案可以很好地扩展!推测其他一些问题根本没有可扩展的算法(所谓的NP难问题).如果是这种情况,那么您应该非常确信无法获得可扩展的方法.

最后,您可以随时在Stack Overflow上询问一个新问题,描述您正在尝试做什么并要求输入.也许社区可以帮助您比最初预期的更有效地解决您的问题!

编辑:鉴于您要解决的问题的描述,现在您正在为每个变量执行一个循环,从0到您尝试定位的数字.该算法的复杂度为O(U ^k),其中k是变量的数量,U是总和.这种方法根本不会很好地扩展.在上述情况下引入每个新变量将使algori2thm运行速度慢100倍,如果你想要100个变量肯定不会很好地扩展!

但是,我认为有一个相当不错的算法,其运行时为O(U ² k),它使用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

因此,这给出了一个有趣的想法,即如何生成所有可能的方法来总结目标.我们的想法是修复第一个系数,然后生成所有可能的方法来完成剩下的总和.换句话说,我们可以递归地思考这个问题.如果我们按顺序将变量列为x ₁,x ₂,...,x _n,那么我们可以尝试修复x _1的某个特定系数,然后sum - c_1 x_1使用x ₂,...,x 求解求和的问题_n.

到目前为止,这似乎并不那么花哨 - 实际上,这正是你上面所做的 - 但我们可以使用一个技巧.只要我们以递归方式考虑这个问题,让我们以相反的方式思考问题.sum如果我们从0开始尝试建立我们可以做的所有事情,而不是开始并试图将其分解？

这是个主意.假设我们已经事先知道了我们可以使用x _1的总和得到的所有数字.然后,对于0和sum(包括0和0)之间的每个数字k ,我们可以从任何组合中的x ₂和x _1中取出k,其中k-c ₂ x ₂是可以由x ₁的组合构成的.但是由于我们已经预先计算了这个,我们可以迭代c _2的所有可能的合法值,计算k - c ₂ x ₂,看看我们是否知道如何制作它.假设我们存储一个巨大的U x(k + 1)布尔值表,这样表条目[x,y]存储"我们可以总结前y个值,包括在内,总结精确到U？",我们可以有效地填写表格.这称为动态编程,是一种功能强大的算法工具.

更具体地说,这是如何工作的.给定k个变量,创建一个U x(k + 1)表T值.然后,设置T [0] [0] =真,并且对于所有x> 0,T [x] [0] =假.这里的基本原理是T [0] [0]表示"我们可以使用a得到零和第一个零变量的线性组合？" 答案肯定是肯定的(空的总和是零!),但对于任何其他没有变量的线性组合的总和,我们绝对无法做到.

现在,对于i = 1 .. k,我们将尝试填充T [x] [i]的值.请记住,T [x] [i]的意思是"我们可以将x作为第一个i变量的线性组合吗？" 好吧,我们知道如果存在一些系数c,我们可以这样做,使得k - cx _i可以使用x ₁,x ₂,...,x _{i - 1}的线性组合来制作.但对于任何c,这只是T [x - cx _i ] [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(U ² k),这比你原来的O(U ^k)算法要好.

但是,您如何使用此信息列出总结目标的所有可能方法？这里的诀窍是要意识到你可以使用这个表来避免在其中许多组合无法工作时浪费大量精力搜索每个可能的组合.

我们来看一个例子吧.假设我们完全计算了这个表,并希望列出所有解决方案.一个想法是考虑列出所有解决方案,其中最后一个变量的系数为零,然后当最后一个变量为1时,等等.之前的方法的问题是,对于某些系数,可能根本没有任何解决方案.但是根据我们上面构建的表格,我们可以删除那些分支.例如,假设我们想要查看是否有任何解决方案以x _k开头,系数为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

递归地将列出所有有效的解决方案,使用我们刚刚构建的表中的值来跳过大量的浪费.一旦你构建了这个表,就可以通过将任务分配给多台计算机来分配这项工作,让每个计算机列出整个解决方案的子集,并将它们全部并行处理.

希望这可以帮助!