通過Needleman Wunsch表追溯

我正在嘗試通過完整的DP表做回溯。假設表格正確填寫了正確的值..如果需要，我可以發佈表格的片段。但這裏是我的代碼片段從回溯生成字符串通過Needleman Wunsch表追溯

def stringBuilder(array, xLine, yLine):   
    StringA, StringB = "", "" 
    i, j = len(xLine), len(yLine) 
    minCost = array[i][j] 
    while (i != 0 and j != 0): 
     minCost = min(array[i - 1][j], array[i][j - 1], array[i - 1][j- 1]) 
     if (minCost == array[i - 1][j - 1]): 
      StringA += xLine[i - 1] 
      StringB += yLine[j - 1] 
      array[i - 1][j - 1] = 0 
      i -= 1 
      j -= 1 
     elif (minCost == array[i][j - 1]): 
      StringA += '-' 
      StringB += yLine[j - 1] 
      array[i][j - 1] = 0 
      j -= 1 
     elif (minCost == array[i - 1][j]): 
      StringA += xLine[i - 1] 
      StringB += '-' 
      array[i - 1][j]= 0 
      i -= 1

我的邏輯是，它總是期待通過此表並找到最小值試圖要回的0部分的成本表。 j應該是0並且循環退出。 NW算法的特別之處在於缺口，刪除，交換的值可以是他們想要的任何數字，而不僅僅是-1,0等。

根據檢查回溯的腳本，我錯了。儘管我知道我正在填寫表格，因爲另一個測試腳本證實了這一點。

來源

2017-02-22 Dringo

嗨，可能這個問題是有多個相鄰的廣場與同'minCost'？如果是這種情況，您的最終排列方式將會有所不同，具體取決於您通過if語句檢查的順序 – nbryans

問題僅僅是您正在反向生成字符串？如果是這樣，然後添加StringA = StringA [:: - 1]和StringB = StringB [:: - 1] –

再次感謝你nbryans，我擺弄順序和循環如何終止，並找出我自己的。但是對於它的價值，我沒有包括它，但我最終倒過了弦。我發佈解決方案下面 – Dringo

如果不同的動作的費用是不同的，那麼你的數組中填充看起來類似代碼：

其中C0，C1，C2是不同的成本。

在這種情況下，回溯代碼也需要如下把這些費用：

if (minCost == array[i - 1][j - 1]+C2): 
     StringA += xLine[i - 1] 
     StringB += yLine[j - 1] 
     array[i - 1][j - 1] = 0 
     i -= 1 
     j -= 1 
    elif (minCost == array[i][j - 1]+C1): 
     StringA += '-' 
     StringB += yLine[j - 1] 
     array[i][j - 1] = 0 
     j -= 1 
    elif (minCost == array[i - 1][j]+C0): 
     StringA += xLine[i - 1] 
     StringB += '-' 
     array[i - 1][j]= 0 
     i -= 1

一種方式來仔細檢查你的算法是計算的回溯步驟的實際成本。在你目前的實施中，我預計回溯成本會高於你計算的成本（因爲回溯忽略了成本）。

來源

2017-02-22 20:40:07

啊，這不是很大，但它確實導致我最終的解決方案，謝謝！ – Dringo

想通了，並沒有佔從小區轉移的成本與細胞

解決方案：

def stringBuilder(array, costBook, xLine, yLine): 
    StringA, StringB = "", "" 
    i, j = len(xLine), len(yLine) 
    totalCost = array[i][j] 
    while (i != 0 or j != 0): 
    if (array[i][j] == array[i][j - 1] + int(costBook['-' + yLine[j - 1]])): 
     StringA += '-' 
     StringB += yLine[j - 1] 
     array[i][j] = 0 
     j -= 1 
    elif (array[i][j] == array[i - 1][j] + int(costBook[xLine[i - 1] + '-'])): 
     StringA += xLine[i - 1] 
     StringB += '-' 
     array[i][j] = 0 
     i -= 1 
    elif (array[i][j] == array[i - 1][j - 1] + int(costBook[xLine[i - 1] + yLine[j - 1]])): 
     StringA += xLine[i - 1] 
     StringB += yLine[j - 1] 
     array[i][j] = 0 
     i -= 1 
     j -= 1

再次

來源

2017-02-22 20:50:51 Dringo

通過Needleman Wunsch表追溯

回答

相關問題