別の意味のある単語を構成するはずの繰り返しごとに各文字を変更することによって、ある単語を他の単語に変換するアルゴリズムですか？

Question

ある単語を他の単語に変更するアルゴリズムを作りたいと思います。例えば、与えられた単語は "MUD"で、 "BED"に変換する必要があります。反復ごとに1文字を変更することができますが、それは別の意味のある単語を形成するはずです。たとえば、「MUD」は「MAD」として変更できます。このように私は "ベッド"に "マッド"を変換する最短の道を見つける必要があります。

有効な単語を見つけるための別の方法が提供されています。 IsWord（）は、指定された文字列が有効であるかどうかにかかわらずブール結果を返すメソッドです。だからそれについて心配する必要はありません。

私はまた、効率やコード行などを心配する必要はありません。どのようにこのアルゴリズムを作るか考えている人はいますか？もしそうなら、私を助けてください。

ありがとうございました。

（私たちは木を使用してバイナリトラバーサルをしなければならないしなければならないことを知っているが、私は、このアルゴリズムでそれを使用する方法は考えていません）

Answer 1

word ladderと呼ばれています。 Wolfram Blogの投稿The Longest Word Ladder Puzzle Everをご覧ください。

Answer 2

は、グラフに次のように作成します。

各単語を1つのステップで1つの単語から別の単語に進むことができれば、ノードであり、2つのノードが接続されています。

元の単語と最後の単語の間の最短距離とパスを見つけます。

参照：最短経路の計算方法については、http://en.wikipedia.org/wiki/Shortest_path_problemを参照してください。

Answer 3

各繰り返しで、可能なすべての新しい単語をあなたが持っている単語の形にし、それらをリスト、集合などで収集します。あなたがすでに持っていた重複や単語を除外します。例：

1. (BED) 
2. (BAD, BET, ....) 
3. (MAD, BAN, ...., BUT, BOT, ....) 

空のリストで終わると、問題が解決されないか、検索された単語がリストに含まれます。

Answer 4

要素（文字列）を含むソートされたキューを持つことから始めます。 各要素には、対象単語に対する（ヒューリスティックに応じた）評価/距離があります。これはHamming Distanceです。ソートされたキューは、この距離を使用して、ターゲットに最も近い単語の上を押します。

あなたの最初の言葉を取り、それをキューに追加します。キューから最初の要素を抽出し、すべての子（1回の変換で取得できる単語）を展開し、それらをキューに入れます。これは、キューから取得した要素が検索対象の要素になるか、キューが空になるまで実行します。