4

一度に1文字ずつ変えて、有効な英語の単語だけを使って単語を変えようとする「ワードゲーム」を聞いたことがあると思います。私はそれを解決するためにA*アルゴリズムを実装しようとしています（A *の理解を具体化するためだけに）。必要なものの1つは、最小距離のヒューリスティックです。

つまり、任意の文字列aを別の文字列bに変換できるこれら3つの突然変異のうちの1つの最小数：1）1つの文字を別の文字に変更する2）任意の文字の前後の場所に1つの文字を追加する3）任意の文字を削除する

例

aabca => abaca:
aabca
abca
abaca
= 2

abcdebf => bgabf:
abcdebf
bcdebf
bcdbf
bgdbf
bgabf
= 4

私は多くのアルゴリズムを試しました。毎回実際の答えを出すものが見つからないようです。実際、人間の推論でさえ最良の答えを見つけているかどうかわからないことがあります。

誰かがそのような目的のためのアルゴリズムを知っていますか？または多分私が1つを見つけるのを手伝うことができますか？

（明確にするために、私は、英語の妥当性を無視して、任意の文字列を他の文字列に変換できるアルゴリズムを求めています。）

4

3 に答える 3

6

最小の編集距離（またはレーベンシュタイン距離）が必要です：

2つの文字列間のレーベンシュタイン距離は、1つの文字列を別の文字列に変換するために必要な編集の最小数として定義され、許容される編集操作は1つの文字の挿入、削除、または置換です。1965年にこの距離を考慮したウラジミールレベンシュテインにちなんで名付けられました。

そして、編集シーケンスを決定するための1つのアルゴリズムは、ここの同じページにあります。

于 2010-05-13T23:40:33.557 に答える
2

「距離の編集」に関する優れたリファレンスは、S。Dasgupta、CH Papadimitriou、およびUV Vaziraniによるアルゴリズム教科書のセクション6.3であり、そのドラフトはここから無料で入手できます。

于 2010-05-15T22:34:03.450 に答える
1

適度なサイズの（小さい）辞書がある場合は、幅優先探索が機能する可能性があります。

したがって、単語が変化する可能性のあるすべての単語から始めて、次にすべての単語が変化する可能性があります（元の単語を除く）。次に、3番目のレベルに進みます...探している単語が見つかるまで。

発散する単語（ターゲットからさらに離れた単語）を削除することもできますが、そうすると、最短パスに到達するために発散状態を通過する必要がある場合に失敗する可能性があります。

于 2010-05-13T23:40:29.050 に答える