Самый длинный общий ответ

Question

Я пытаюсь написать рекурсивный алгоритм, который находит самую длинную общую подпоследовательность из двух списков, как описано в http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Похоже, что рекурсия никогда не заканчивается, и я не могу понять, что я делаю Wrond

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

Любая помощь в выяснении этого приветствуется. Спасибо.

Answer 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 до 4 ГБ.