通过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表追溯

回答

相关问题