距離を編集してひねります

Question

私は動的プログラミングを使って何かを解決しようとしていますが、何か問題があります。私が動的プログラミングに取り組むとき、私は通常再帰的アルゴリズムを決定し、そこでそこから私の動的ソリューションに進みます。 m、nは、そのようなことn.lengthがm.lengthより大きく、nは文字「＃が含まれていません：私は問題

トラブル

を抱えているこの時間は、次の2つの文字列を持っていると言います' 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は、同じ長さ、リターンmは

[います1]任意のインデックスに＃を挿入するコストを計算する

[2]最小コストを持つ文字列を決定する。その文字列をm 'とする。

[3] m'とnのアルゴリズムをもう一度実行する。

これは最適な再帰アルゴリズムではないと私は考えています。これは、私が動的アルゴリズムの正しい軌道にないと信じさせてくれます。

通常の編集距離にm.length x n.length行列を使用して読んだことがありますが、私のアルゴリズムに合うように簡単に変形する方法はわかりません。

私の再帰アルゴリズムの考え方と、ダイナミックソリューションに到達するために必要なステップは何ですか？

Answer 1

取ると、あなたの定義（のpython）：

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' 

Answer 2

あなたがnの成長長さ以上の問題を解決する場合、私はここで動作するように最適性原理を見ることができる唯一の方法です。だから、動的なプログラミングソリューションは、次のようになります。長さm.length()+1の各連続した部分文字列の場合

1. を、新しいmの提案のリストを得、問題を解決します。
2. 対応する部分文字列との最小距離が新しいmとしてプロポーザルを選択し、プロセスを繰り返します。

このアルゴリズムでは現在のところ最適な解以外のものは保存する必要はありませんが、確かに距離行列ではありません。このソリューションにもかなり近いように見えますが、「nを縮小して部分的な問題が発生しました。