通過遞歸調用尋找路徑：最佳字符串對齊

Question

因此，我曾試着問過這個問題，但我想我並不十分清楚我所尋找的是什麼。我正在製作一個最佳的字符串對齊算法，it's really just a dynamic programming problem。所以我決定遞歸地寫它。該程序由兩部分組成：

• 查找兩個單詞之間的「編輯距離」，其中根據某些關聯成本最小化對齊。例如，對齊同一個字母的成本爲0，對齊兩個元音的成本爲0.5，但對齊間隔的字母的成本爲1.
• 可視化對齊：即將字符串放在對方的頂部，使字符和間隙最佳對齊。

我覺得我的編輯距離起作用了。我獲得了與同齡人相同的價值觀，似乎沒有即時的問題。然而，我很難弄清楚如何恢復匹配，插入和刪除的順序來可視化對齊。我的問題來自於我有一個遞歸函數，它至少需要三次遞歸調用。所以，我最終得到的是比所需要的更長的序列，因爲每次遞歸調用都會附加一個「移動」（匹配，插入，刪除），這可能不會被使用，因爲它不是最便宜的。

這裏是我的代碼：

newseq = [] 
@memoize 
def opt(a, b): 
    global newseq # Visual Alignment 'move' sequence 
    gap = 1 # Gap cost 
    if not a: 
     return len(b) 
    if not b: 
     return len(a) 

    if a and b: 
     p1 = a[0] in v # First letters vowells? 
     p2 = b[0] in v 
     if a[0] == b[0]: # First letters equal each other? 
      alpha = 0 
     elif p1^p2: # Vowel and Consonant? 
      alpha = 1.2 
     elif p1 and p2: # Vowel and Vowel? 
      alpha = 0.5 
     else:   # Consonant and Consonant? 
      alpha = 0.6 

    r1 = opt(a[1:], b[1:]) + alpha 
    r2 = opt(a[1:], b) + gap 
    r3 = opt(a, b[1:]) + gap 
    # Reset newseq 
    newseq = newseq[:-3] 

    # Takes min of recursive calls, and gives associated 'move' 
    res = min((r1, 'Match'),  # Match 
       (r2, 'Insertion'), # Insertion 
       (r3, 'Deletion'), # Deletion 
       key = lambda x: x[0]) 

    newseq.append(res[1]) 
    return res[0] 

所以是的，我知道我有什麼不工作。我的全球newseq變量當前的長度爲1，因爲我試圖通過刪除遞歸調用期間發生的所有附加操作來重置它。 如何設置一種方法來記錄與此遞歸算法組成最佳對齊的「移動」序列？

編輯：這裏是我的memoize的裝飾功能：

def memoize(f): 
    cache = {} 
    def decorated_function(*args): 
     if args in cache: 
      return cache[args] 
     else: 
      cache[args] = f(*args) 
      return cache[args] 
    return decorated_function 

Answer 1

1）傳遞通過您的遞歸函數堆棧（或其他集合）的說法。 2）當你遞歸地調用自己的時候，也可以將你正在採取的步驟（例如使用枚舉的步驟類型和ints/chars/strings /不管表明它在做什麼）推到堆棧上。

3）當您從2）中的呼叫返回時，彈出堆棧並重復2）。

4）當您有解決方案時，您可以存儲與其結果/分數相關聯的堆棧。