最長公共Subseqence

我想寫一個遞歸算法，找出兩個列表的最長公共子序列，如http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#LCS_function_defined 最長公共Subseqence

描述看來，遞歸永遠不會結束，我不能找出我在做什麼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; 
     } 
    } 
}

任何幫助搞清楚這一點是值得讚賞的。謝謝。

來源

2013-10-19 Ares

我確實嘗試調試它。它似乎與小列表正常工作，但在大列表（〜1000個元素）上使用它時，它只是繼續運行。我知道這樣做效率低下，有些步驟多次執行，但它已連續運行了近一天。 – Ares

我也試過你的代碼，用ints而不是ActionType項目的小列表。它運行良好，所以我認爲這只是一個複雜性/遞歸深度的問題。你已經得到了堆棧溢出，還是沒有完成？ –

我認爲你的算法最終會完成，但對於大量輸入可能需要一段時間。對於大小爲'n'和'm'的輸入，它應該花費'O（n * m）'時間。對於'n = m = 1000'，我不會指望超過一個小時，但很難說沒有經過一些測試，常數因子是多少。 –

這個問題很複雜。實現記憶將運行時間從一天以上減少到幾秒鐘。

這裏是更新算法：

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年元素長，操作類型是一個枚舉。這種方法使用了大量的內存。我必須將JVM堆大小增加到4GB。

來源

2013-10-21 06:43:54 Ares

最長公共Subseqence

回答

相關問題