Javaダイナミックプログラミング編集距離問題の例コード

動的計画プロセスは次のとおりです。各決定は現在の状態に依存し、状態が転送されます。決定シーケンスは変化する状態で生成されるため、このマルチステージ最適化意思決定プロセスは動的プログラミングと呼ばれます。

動的プログラミングは、実際には、固定アルゴリズムではなく、トピックのタイプの一般的な用語です。動的プログラミングの意味は、再帰的（または分割および征服）戦略を採用し、大きな問題のサブ問題を解決することにより、全体的なアプローチを解決することです。動的プログラミングの中心的なアイデアは、問題を複数のサブ問題に巧みに分割し、サブ問題を計算して問題に対する全体的な解決策を取得することです。サブ問題はより多くのサブ問題に分割される可能性があり、それにより、再帰的反復と同様の方法を使用して必要な問題を解決することができます。質問の説明：

シーケンスsとtの場合、それらの間の距離は次のように定義されます。2つのうちの1つで次の操作を数回実行すると、文字を削除します。 2、文字を挿入します。 3、文字を変更します。操作が実行されるたびに、カウントが1増加します。SとTの等しいシーケンスに変換する最小カウントは、編集距離（編集）または2つの類似性です。対応するアルゴリズムとその実装を提供してください。

分析：

シーケンスsとtの長さはそれぞれmとnであり、それらの間の編集距離が編集[m] [n]として表されると仮定します。次に、シーケンスを操作するときに次の状況があります。

a。 sとtの最終文字が等しい場合、上記の定義操作のいずれか（つまり、「編集」）は最終文字に必要ではありません。つまり、カウントは必要ありません。条件は満たされます：[M] [n] =編集[M-1] [n-1]編集。

b。 SとTの終了文字が等しくない場合、どちらの端の端を編集する必要があり、対応するカウントは1だけ増加します。

b1、sまたはtの終了を変更してtまたはsに等しくするには、[m] [n] =編集[m-1] [n-1] +1を編集します。

b2、sの最後の要素を削除してsとtを等しくし、[m] [n] =編集[m-1] [n] +1を編集します。

b3、tの最後の要素を削除してtとsを等しくし、[m] [n] =編集[m] [n-1] +1を編集します。

b4は、sの最後にtの尾要素を追加してsとtを等しくし、sの長さはm+1になりますが、この時点では、sとtの最終要素はすでに等しくなります。 Sの最初のM要素をTの最初のN-1要素と比較するだけであるため、[M] [n] =編集[M] [n-1] +1を編集するだけです。

b5、tの最後にsの尾要素を追加して、tとsを等しくします。現時点での状況はB4と同じで、満足のいく編集[M] [n] =編集[M-1] [n] +1;

c。特別なケースは、Sが空の場合、[0] [n] = nを編集することです。 tが空の場合は、[M] [0] = mを編集します。これは理解しやすいです。たとえば、シーケンス ""および "abc"の場合、両方の最小操作は3、つまりシーケンス "" 3つの挿入操作を実行するか、「ABC」は3削除操作を実行します。

したがって、上記の距離を編集する動的なプログラミング方程式を推測することは難しくありません。

したがって、文字列編集距離の動的プログラミングアルゴリズムの再帰的実装は、次のJavaコードで表現できます。

 public static int editdistance（string a、string b）{if（a == null || b == null）{return -1; } return editdistance（a、a.length（） -  1、b、b.length（）-1）; } public static int editdistance（string a、int m、string b、int n）{if（m <0 || n <0）{return 1; } else if（a.charat（m）== b.charat（n））{return editdistance（a、m -1、b、n -1）; } else {return math.min（math.min（editdistance（a、m -1、b、n） + 1、editdistance（a、m、b、n -1） + 1）、editdistance（a、m -1、b、n -1） + 1）; }}

アップデート：

同時に、編集距離の動的プログラミング方程式から、編集[M] [n]は編集[M -1] [n -1]から導き出されることがわかります。つまり、2次元配列を通過してから、バックトラッキングを介して現在の値を計算できます。

たとえば、文字列s = "sailn"およびt = "failing"の場合、2次元配列は以下として初期化されます。

s [0] = s、t [0] = f、次にs [0]！= t [0]、次に上記の2次元マトリックスに対応し、編集[1] [1] = min（編集[0] [0]、編集[0] [1]、編集[1] [0]） + 1 I.E. 1 = 1。

s [1] = a、t [1] = a、s [1] = t [1]の場合、それは2次元マトリックス、編集[2] [2] =編集[1] [1]に対応します。したがって、[2] [2] = 1。

したがって、2つの間の編集距離は編集[M] [n] =編集[5] [7] = 3です。

したがって、上記のアイデアによれば、動的プログラミングのバックトラッキングソリューションのJavaバージョンは次のように実行できます。

 public static int editdistance（string a、string b）{if（a == null || b == null）{return -1; } int [] [] matrix = new int [a.length（） + 1] [b.length（） + 1]; for（int i = 0; i <a.length（）+1; i ++）{for（int j = 0; j <b.length（）+1; j ++）{if（i == 0）{matrix [i] [j] = j; } else if（j == 0）{matrix [i] [j] = i; } else {if（a.charat（i -1）== b.charat（j -1））{matrix [i] [j] = matrix [i -1] [j -1]; } else {matrix [i] [j] = 1 + math.min（math.min（matrix [i -1] [j]、matrix [i] [j -1]）、matrix [i -1]）; }}} return matrix [a.length（）] [b.length（）]; }

要約します

上記は、Javaダイナミックプログラミングの編集距離問題サンプルコードに関するこの記事の内容全体です。私はそれが誰にでも役立つことを願っています。興味のある友人は、このサイトの他の関連トピックを引き続き参照できます。欠点がある場合は、それを指摘するためにメッセージを残してください。