递归搜索的记忆

Question

我正在尝试解决一个问题，在该问题中，您必须计算在给定特定参数的情况下可以制作的可能条形码的数量。我递归地解决了这个问题，并且每次都能得到正确的答案。但是，我的程序非常慢。我尝试使用一种我读到的称为记忆化的技术来纠正此问题，但在给定特定输入（例如：10、10、10）时，我的程序仍然会爬行。这是 java.

中的代码

有人知道我做错了什么吗？

import java.util.Scanner;

//f(n, k, m) = sum (1 .. m) f(n - i, k - 1, m)

public class BarCode { public static int[][] memo;

public static int count(int units, int bars, int width) {
    int sum = 0;
    if (units >= 0 && memo[units][bars] != -1) //if the value has already been calculated return that value
            return memo[units][bars];

    for (int i = 1; i <= width; ++i) {
        if (units == 0 && bars == 0)
            return 1;
        else if (bars == 0)
            return 0;
        else {
            sum += count(units - i, bars - 1, width);
        }
    }
    if (units > -1)
        memo[units][bars] = sum;

    return sum;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    //while (in.hasNext()) {
        int num = in.nextInt();
        int bars = in.nextInt();
        int width = in.nextInt();
        memo = new int[51][51];
        for (int i = 0; i < memo.length; ++i) {
            for (int j = 0; j < memo.length; ++j)
                memo[i][j] = -1;
        }
        int sum = 0;
        sum += count(num, bars, width);
        System.out.println(sum);
    //}
    in.close();
}
}

TL:DR 我对递归搜索的记忆太慢了。求助！

Answer 1

您的记忆化实施看起来是有效的。它可能对某些人有所帮助，但真正的问题在于您对算法的选择。

根据我对您的代码的粗略检查，对您的计数方法的调用平均会循环 width 次。每次循环时，它都会通过再次调用 count 来更深一层。看起来它还会从第一层向下循环 bars 层。如果我的几根苏格兰威士忌手指的渐近分析是正确的，这将导致一个具有 O(width^bars) 运行时复杂度的算法。随着您增加输入参数，尤其是条形，您的应用程序计算答案所需的步数将大大增加（在条形的情况下呈指数增长）。

您的记忆将减少所需的重复计算次数，但每个被记忆的值仍然需要至少计算一次以便记忆提供帮助。所以不管有没有记忆，你仍然在处理非多项式的时间复杂度，这总是意味着性能不佳。

您可能需要考虑寻找更有效的方法。与其尝试计算条形码组合的数量，不如尝试使用组合学来尝试计算它。例如，我可以尝试找出小写字符串的数量（仅使用字符 a-z）我可以通过生成所有小写字符串并计算它们的数量来生成长度为 n 的字符串，但这将有一个指数时间复杂，性能不佳。另一方面，我知道基本组合学告诉我，我可以创建的字符串数量的公式是 26^n（每个位置有 26 个选择，n 个位置），计算机可以轻松快速地对其进行计算。

寻找计算条形码数量的类似方法。

Answer 2

您从记忆中排除了 count 调用中 单位 < 0 的所有结果：

if (units > -1)
    memo[units][bars] = sum;

这会导致对这些值进行大量不必要的 count 调用。

要包括所有情况，您可以使用 HashMap，其键从 units 和 bars 值生成。我使用了从 units 和 bars 生成的字符串，如下所示：

//f(n, k, m) = sum (1 .. m) f(n - i, k - 1, m)

public class BarCode {
    public static Map<String, Integer>  memo    = new HashMap<>();

    public static int count(int units, int bars, int width) {
        int sum = 0;

        final String key = units + " " + bars;
        Integer memoSum = memo.get(key);
        if (memoSum != null) {
           return memoSum.intValue();
        }

        for (int i = 1; i <= width; ++i) {
            if (units == 0 && bars == 0)
                return 1;
            else if (bars == 0)
                return 0;
            else {
                sum += count(units - i, bars - 1, width);
            }
        }

        memo.put(key, Integer.valueOf(sum));

        return sum;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int bars = in.nextInt();
        int width = in.nextInt();
        memo = new HashMap<>();
        int sum = 0;
        sum += count(num, bars, width);
        System.out.println(sum);
        in.close();
    }
}

例如，对于输入值“10 10 10”，地图中保存了 415 个条目，count 的调用次数从超过 600 万次减少到 4,150 次。

递归搜索的记忆

Memoization of a Recursive Search

java

recursion

memoization