編輯距離，扭曲

我正在嘗試使用動態編程來解決某些問題，但我遇到了一些麻煩。當我進行動態編程時，我通常會確定一個遞歸算法，然後從那裏進入我的動態解決方案。我有麻煩編輯距離，扭曲

的問題

這一次，假設你有兩個字符串：m和n，使得n.length比m.length更大，和n不包含字符「＃」。您希望以最小的成本將m變成與字符串n相同的長度的字符串。

成本被定義爲SUM（Penalty（m [i]，n [i]）），其中i在字符串char數組的索引中。

罰金被定義爲這樣

private static int penalty(char x,char y) { 
    if (x==y) { return 0;} 
    else if (y=='#') { return 4;} 
    else { return 2;} 
}

我能想到的唯一途徑是如下：

[0]如果m和n是相同的長度，返回米

[ 1]在任意索引m處插入＃的計算成本

[2]確定具有最小成本的字符串。讓該字符串爲m'

[3]在m'和n上再次運行該算法。

我不認爲這甚至是最優的遞歸算法，導致我相信我不是一個動態算法的正確軌道。

我已經閱讀了使用m.length x n.length矩陣進行正常編輯距離的方法，但是我沒有看到我可以如何輕鬆地將其轉換爲適合我的算法。

關於我的遞歸算法和我需要採取的步驟以達到動態解決方案的想法？

來源

2017-04-11 Michael Sila

以你的定義（蟒蛇）：

def penalty(x, y): 
    if x == y: 
     return 0 
    if y == '#': 
     return 4 
    return 2 

def cost(n, m): 
    return sum(penalty(a, b) for a, b in zip(n, m))

然後你就可以定義重新分配到m每個#成本最低的距離被包括在內。

def distance(n, m): 
    for _ in range(len(n) - len(m)): 
     m = min((m[:i]+'#'+m[i:] for i in range(len(m)+1)), key=lambda s: cost(n, s)) 
    return m 

>>> distance('hello world', 'heloworld') 
'he#lo#world'

來源

2017-04-11 04:47:36 AChampion

，我可以看到最優的原則在這裏工作的唯一方法是，如果你超過n成長長度解決問題。因此，動態規劃的解決方案是這樣的：

對於長度m.length()+1的每個連續子，解決問題，產生的提案清單新m。
選擇與相應子字符串的距離最小的提案作爲新的m，然後重複該過程。

您不需要在此算法中存儲除當前最優解之外的其他任何內容，當然不是距離矩陣。在我看來，你和這個解決方案非常接近，你只是錯過了「縮小n以獲得子問題」的一部分。

來源

2017-04-11 04:49:47 Sebastiaan

編輯距離，扭曲

回答

相關問題