Как оптимизировать этот алгоритм рекурсивного возврата? - PullRequest
Новая
       8

Как оптимизировать этот алгоритм рекурсивного возврата?

0 голосов
/ 10 июня 2019

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

Исключение в потоке "main" java.lang.OutOfMemoryError: Превышен предел накладных расходов GC

для больших чисел. 

public static void findAllSolutionMethod(int NTotal, ArrayList<ArrayList<Integer>> solutions,
        ArrayList<Integer> currentSolution, int lower, int upper) {

    // success base case
    if (NTotal == 0) {
        ArrayList<Integer> copy = new ArrayList<Integer>();
        // creates deep copy 
        for (int i = 0; i < currentSolution.size(); i++) {
            copy.add(currentSolution.get(i));
        }
        // add to solutions arraylist
        solutions.add(copy);
        return;
    }

    // invalid number base case (number added too big)
    else if (NTotal < 0) {
        return;
    }

    else {
        // iterates through range of numbers
        for (int i = lower; i <= upper; i++) {
            currentSolution.add(i);
            findAllSolutionMethod(NTotal - i, solutions, currentSolution, lower, upper);
            currentSolution.remove(currentSolution.size() - 1);
        }
    }
}

Можно ли как-нибудь оптимизировать этот код, чтобы он не занимал так много места?

1 Ответ

0 голосов
/ 10 июня 2019

Это довольно легко, если вы рекурсивно называете дерево. Напишите решение на бумаге, наберите bfs и вы увидите способ оптимизации. 

public static List<int[]> findPermutations(int sum, int low, int high) {
    final Function<Node, int[]> getPath = node -> {
        int[] arr = new int[node.depth()];
        int i = arr.length - 1;

        while (node != null) {
            arr[i--] = node.val;
            node = node.parent;
        }

        return arr;
    };

    List<int[]> res = new LinkedList<>();
    Deque<Node> queue = new LinkedList<>();

    for (int i = low; i <= high; i++) {
        queue.clear();
        queue.add(new Node(low));

        while (!queue.isEmpty()) {
            Node node = queue.remove();

            if (node.sum == sum)
                res.add(getPath.apply(node));
            else {
                for (int j = low; j <= high; j++) {
                    if (node.sum + j <= sum)
                        queue.add(new Node(j, node.sum + j, node));
                    else
                        break;
                }
            }
        }
    }

    return res;
}

private static final class Node {

    private final int val;
    private final int sum;
    private final Node parent;

    public Node(int val) {
        this(val, val, null);
    }

    public Node(int val, int sum, Node parent) {
        this.val = val;
        this.sum = sum;
        this.parent = parent;
    }

    public int depth() {
        return parent == null ? 1 : (parent.depth() + 1);
    }

    @Override
    public String toString() {
        return val + " (" + sum + ')';
    }

}

Демо-версия: 

findPermutations(4, 1, 3).forEach(path -> System.out.println(Arrays.toString(path)));

Выход: 

[1, 3]
[1, 1, 2]
[1, 2, 1]
[1, 1, 1, 1]
[2, 2]
[2, 1, 1]
[3, 1]
...