Самая длинная общая подпоследовательность

Я пытаюсь написать рекурсивный алгоритм, который находит самую длинную общую подпоследовательность двух списков, как описано в 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;
        }
    }
}

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


java recursion infinite lcs
person Ares    schedule 19.10.2013    source источник
comment
Я попытался отладить его. Похоже, он отлично работает с небольшими списками, но при использовании его с большими списками (~ 1000 элементов) он просто продолжает работать. Я понимаю, что это неэффективно, и некоторые шаги выполняются несколько раз, но он работает уже почти сутки непрерывно.   -  person Ares    schedule 20.10.2013
comment
Я также попробовал ваш код с небольшими списками целых чисел вместо элементов ActionType. Это работало нормально, поэтому я предполагаю, что это просто вопрос сложности/глубины рекурсии. Вы уже получили переполнение стека или оно просто не заканчивается?   -  person sebastian_oe    schedule 20.10.2013
comment
Я думаю, что ваш алгоритм в конечном итоге завершится, но для больших входных данных, вероятно, потребуется некоторое время. Для входных данных размера n и m это должно занять O(n*m) времени. Для n=m=1000 я бы не ожидал, что это займет больше часа, но трудно сказать, что такое постоянный фактор, без некоторого тестирования.   -  person Mark Elliot    schedule 20.10.2013
comment
Будет ли использование динамического программирования лучшим вариантом? Я не уверен, что хранить более 1000^2 списков — хорошая идея.   -  person Ares    schedule 20.10.2013
comment
@Ares прибивает это; вы действительно хотите изучить кэширование, так как это будет многократно пересчитывать одни и те же возвращаемые значения. Ищите запоминания.   -  person Dean J    schedule 20.10.2013

Ответы (1)


arrow_upward
1
arrow_downward

Вопрос был в сложности. Внедрение запоминания сократило время выполнения с более чем суток до нескольких секунд.

Вот обновленный алгоритм:

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 ГБ.

person Ares    schedule 21.10.2013