Могут ли алгоритмы грубой силы масштабироваться?

Question

У меня есть математическая задача, которую я решаю методом проб и ошибок (я думаю, это называется грубая сила), и программа работает нормально, когда есть несколько вариантов, но, поскольку я добавляю больше переменных / данных, это занимает все больше и больше времени. бежать.

Моя проблема в том, что, хотя прототип работает, он полезен с тысячами переменных и большими наборами данных; Итак, мне интересно, можно ли масштабировать алгоритмы грубой силы. Как мне подойти к ее масштабированию?

Я начал учиться и играть с 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);
            }
        }
    }   
}

Я новичок в программировании, и мне жаль, если я не правильно сформулировал этот вопрос. Это более общий вопрос.

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, описывая, что вы пытаетесь сделать, и запрашивая ввод. Возможно, сообщество может помочь вам решить вашу проблему более эффективно, чем вы изначально ожидали!

РЕДАКТИРОВАТЬ: Учитывая описание проблемы, которую вы пытаетесь решить, сейчас вы выполняете один цикл for для переменной от 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 ₁ , затем решаем задачу суммирования sum - c_1 x_1, используя только x ₂ , ..., x _n .

Пока это не кажется таким уж причудливым - на самом деле, это именно то, что вы делаете выше - но есть один прием, который мы можем использовать. Пока мы будем рекурсивно думать об этой проблеме, давайте подумаем о проблеме противоположным образом. Вместо того, чтобы начинать с sum и пытаться разбить его, что, если вместо этого мы начали с 0 и попытались собрать все, что могли?

Вот идея. Предположим, что мы уже знаем заранее все числа, которые мы можем сделать, используя только суммы x ₁ . Тогда для каждого числа k от 0 до sum включительно мы можем сделать k из x ₂ и x ₁ из любой комбинации, где k - c ₂ x ₂ - это то, что может быть сделано из комбинаций x ₁ . Но так как мы предварительно вычислили это, мы можем просто перебрать все возможные допустимые значения c ₂ , вычислить k - c ₂ x ₂ и посмотреть если мы знаем, как это сделать. Предполагая, что мы храним гигантскую таблицу булевых значений U x (k + 1), такую, что в записи таблицы [x, y] хранятся «можем ли мы суммировать первые значения y включительно таким образом, чтобы сумма точно составляла U ?,» мы можем заполнить таблицу эффективно. Это называется динамическое программирование и является мощным алгоритмическим инструментом.

Конкретнее, вот как это может работать. Учитывая k переменных, создайте таблицу значений T U x (k + 1). Затем установите T [0] [0] = true и T [x] [0] = false для всех x> 0. Здесь обосновано, что T [0] [0] означает «можем ли мы получить нулевую сумму, используя линейная комбинация первых нулевых переменных? и ответ определенно да (пустая сумма равна нулю!), но для любой другой суммы, не состоящей из линейной комбинации без переменных, мы определенно не можем это сделать.

Теперь, для i = 1 .. k, мы попытаемся заполнить значения T [x] [i]. Помните, что T [x] [i] означает «можем ли мы сделать x линейной комбинацией первых переменных i?» Ну, мы знаем, что мы можем сделать это, если есть некоторый коэффициент c, такой, что k - cx _i может быть получено с использованием линейной комбинации x ₁ , x ₂ , ..., x _{i - 1} . Но для любого c это просто, правда ли, что T [x - c x _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 ), который у вас был изначально.

Но как вы используете эту информацию, чтобы перечислить все возможные способы подведения итогов к цели? Хитрость заключается в том, чтобы понять, что вы можете использовать таблицу, чтобы не тратить огромное количество усилий на поиск каждой возможной комбинации, когда многие из них не будут работать.

Давайте посмотрим на пример. Предположим, что мы полностью вычислили эту таблицу и хотим перечислить все решения. Одна идея состоит в том, чтобы подумать о перечислении всех решений, где коэффициент последней переменной равен нулю, затем, когда последняя переменная равна единице, и т. Д. Проблема с подходом, который вы использовали ранее, заключается в том, что для некоторых коэффициентов не может быть никаких решений вообще. , Но с помощью таблицы, которую мы построили выше, мы можем исключить эти ветви. Например, предположим, что мы хотим посмотреть, есть ли какие-либо решения, которые начинаются с 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

Это рекурсивно перечислит все решения, которые работают, используя значения в таблице, которую мы только что создали, чтобы пропустить огромное количество потерянных усилий. Создав эту таблицу, вы можете разделить эту работу, разбив задачу на несколько компьютеров, каждый из которых перечислит подмножество общих решений и обработать их все параллельно.

Надеюсь, это поможет!

Answer 2

По определению, алгоритмы грубой силы глупы. Вам было бы намного лучше с более умным алгоритмом (если он у вас есть). Усовершенствованный алгоритм сократит объем работы, которая должна быть выполнена, надеюсь, до такой степени, что вы сможете сделать это без необходимости «масштабирования» на несколько машин.

Независимо от алгоритма, наступает момент, когда требуемый объем данных или вычислительная мощность настолько велики, что вам потребуется использовать что-то вроде Hadoop. Но обычно мы здесь говорим о больших данных. В наши дни вы уже можете многое сделать на одном компьютере.

Answer 3

Алгоритм решения этой проблемы закрыт для процесса, который мы изучаем для ручного математического деления или также для преобразования из десятичного в другое основание, такое как восьмеричное или шестнадцатеричное - за исключением того, что два примера ищут только одно каноническое решение.

Чтобы рекурсия закончилась, важно упорядочить массив данных.Чтобы быть эффективными и ограничивать количество рекурсий, также важно начинать с более высоких значений данных.

Конкретно, вот рекурсивная реализация Java для этой проблемы - с копией вектора результата coeff длякаждая рекурсия, как и ожидалось в теории.

import java.util.Arrays;

public class Solver
{
    public static void main(String[] args)
    {
        int target_sum = 100;
        // pre-requisite: sorted values !!
        int[] data = new int[] { 5, 10, 20, 25, 40, 50 };
        // result vector, init to 0
        int[] coeff = new int[data.length];
        Arrays.fill(coeff, 0);
        partialSum(data.length - 1, target_sum, coeff, data);
    }

    private static void printResult(int[] coeff, int[] data) {
        for (int i = coeff.length - 1; i >= 0; i--) {
            if (coeff[i] > 0) {
                System.out.print(data[i] + " * " + coeff[i] + "   ");
            }
        }
        System.out.println();
    }

    private static void partialSum(int k, int sum, int[] coeff, int[] data) {
        int x_k = data[k];
        for (int c = sum / x_k; c >= 0; c--) {
            coeff[k] = c;
            if (c * x_k == sum) {
                printResult(coeff, data);
                continue;
            } else if (k > 0) {
                // contextual result in parameters, local to method scope
                int[] newcoeff = Arrays.copyOf(coeff, coeff.length);
                partialSum(k - 1, sum - c * x_k, newcoeff, data);
                // for loop on "c" goes on with previous coeff content
            }
        }
    }
}

Но теперь этот код находится в особом случае: последнее значение теста для каждого коэффициента равно 0, поэтому копия не требуется.

КакДля оценки сложности мы можем использовать максимальную глубину рекурсивных вызовов как data.length * min({ data }).Конечно, он не будет хорошо масштабироваться, и ограниченным фактором является память трассировки стека (опция -Xss JVM).Код может завершиться с ошибкой переполнения стека для большого набора data.

Чтобы избежать этих недостатков, полезен процесс «отмены рекурсии».Он состоит в замене стека вызовов метода программным стеком для хранения контекста выполнения для последующей обработки.Вот код для этого:

import java.util.Arrays;
import java.util.ArrayDeque;
import java.util.Queue;

public class NonRecursive
{
    // pre-requisite: sorted values !!
    private static final int[] data = new int[] { 5, 10, 20, 25, 40, 50 };

    // Context to store intermediate computation or a solution
    static class Context {
        int k;
        int sum;
        int[] coeff;
        Context(int k, int sum, int[] coeff) {
            this.k = k;
            this.sum = sum;
            this.coeff = coeff;
        }
    }

    private static void printResult(int[] coeff) {
        for (int i = coeff.length - 1; i >= 0; i--) {
            if (coeff[i] > 0) {
                System.out.print(data[i] + " * " + coeff[i] + "   ");
            }
        }
        System.out.println();
    }

    public static void main(String[] args)
    {
        int target_sum = 100;
        // result vector, init to 0
        int[] coeff = new int[data.length];
        Arrays.fill(coeff, 0);

        // queue with contexts to process
        Queue<Context> contexts = new ArrayDeque<Context>();
        // initial context
        contexts.add(new Context(data.length - 1, target_sum, coeff));

        while(!contexts.isEmpty()) {
            Context current = contexts.poll();
            int x_k = data[current.k];
            for (int c = current.sum / x_k; c >= 0; c--) {
                current.coeff[current.k] = c;
                int[] newcoeff = Arrays.copyOf(current.coeff, current.coeff.length);
                if (c * x_k == current.sum) {
                    printResult(newcoeff);
                    continue;
                } else if (current.k > 0) {
                    contexts.add(new Context(current.k - 1, current.sum - c * x_k, newcoeff));
                }
            }
        }
    }
}

С моей точки зрения, трудно быть более эффективным в однопоточном выполнении - для механизма стека теперь требуются копии массива коэффициентов.