1

我正在尝试编写一个递归算法来查找两个列表的最长公共子序列，如http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#LCS_function_defined中所述

似乎递归永远不会结束，我无法弄清楚我在做什么错

public static List<ActionType> getLongestSequence(List<ActionType> list1, List<ActionType> list2) {
    return getLongestSequence(list1, list2, list1.size(), list2.size());
}

public static List<ActionType> getLongestSequence(List<ActionType> list1, List<ActionType> list2, int list1index, int list2index) {

    if (list1index == 0 || list2index == 0) {
        return new ArrayList<ActionType>();
    }

    if (list1.get(list1index-1).equals(list2.get(list2index-1))) {
        List<ActionType> retVal = getLongestSequence(list1, list2, list1index-1, list2index-1);
        retVal.add(list1.get(list1index-1));
        return retVal;
    } else {
        List<ActionType> ret1 = getLongestSequence(list1, list2, list1index, list2index-1);
        List<ActionType> ret2 = getLongestSequence(list1, list2, list1index-1, list2index);

        if (ret1.size() > ret2.size()) {
            return ret1;
        } else {
            return ret2;
        }
    }
}

任何解决此问题的帮助表示赞赏。谢谢你。

4

1 回答 1

1

这个问题很复杂。实施记忆将运行时间从一天以上减少到几秒钟。

这是更新的算法：

public static List<ActionType> getLongestSequence(List<ActionType> list1, List<ActionType> list2) {
    lcsMemorize = new HashMap<Integer, List<ActionType>>();
    return getLongestSequence(list1, list2, list1.size(), list2.size());
}

public static List<ActionType> getLongestSequence(List<ActionType> list1, List<ActionType> list2, int list1index, int list2index) {

    List<ActionType> retVal = lcsMemorize.get(list1index + list2index * 1000000);

    if (retVal != null) {
        return retVal;
    } else if (list1index == 0 || list2index == 0) {
        retVal = new ArrayList<ActionType>();
    } else if (list1.get(list1index-1).equals(list2.get(list2index-1))) {
        List<ActionType> returned = getLongestSequence(list1, list2, list1index-1, list2index-1);

        retVal = new ArrayList<ActionType>(returned);
        retVal.add(list1.get(list1index-1));
    } else {
        List<ActionType> ret1 = getLongestSequence(list1, list2, list1index, list2index-1);
        List<ActionType> ret2 = getLongestSequence(list1, list2, list1index-1, list2index);

        if (ret1.size() > ret2.size()) {
            retVal = ret1;
        } else {
            retVal = ret2;
        }
    }

    lcsMemorize.put(list1index + list2index * 1000000, retVal);

    return retVal;
}

笔记：

在我的运行中，原始列表的长度为 1100 - 1300 个元素，并且 ActionType 是一个枚举。这种方法使用大量内存。我不得不将 JVM 堆大小增加到 4GB。

于 2013-10-21T06:43:54.260 回答