私はこの編集距離の問題のバリエーションに出くわしました：
ある単語から別の単語への最短経路を見つけます。たとえば、storm-> powerのように、isValidWord()関数を使用して各中間単語を検証します。単語の辞書への他のアクセスがないため、グラフを作成できません。
私はこれを理解しようとしていますが、それ自体は距離に関連する問題ではないようです。多分単純な再帰を使用しますか？しかし、それでは、自分が正しい方向に進んでいることをどうやって知るのでしょうか。
他の誰かがこれを面白いと思いますか？助けてくれるのを楽しみにしています、ありがとう！
これは、ことばの梯子として知られているルイス・キャロルのパズルです。ドナルド・クヌースは、スタンフォード・グラフベースでこれをカバーしています。これもまた
幅優先探索として表示できます。単語の辞書にアクセスする必要があります。そうしないと、検索する必要のあるスペースが膨大になります。有効な単語にアクセスできる場合は、単語のすべての順列を生成し、isValidWord（）を使用してそれをフィルタリングできます（Norvigの「スペルコレクターの書き方」は編集の生成に関する優れた説明です）。
現在いる場所とできる場所の間の編集距離を最小化することで、検索をガイドできます。たとえば、検索するすべてのノードのスペースを生成し、最小編集距離で並べ替えます。ターゲットに最も近い（たとえば、編集距離を最小化する）リンクを最初にたどります。この例では、「電力」に最も近いノードをたどります。
これも面白いと思ったので、ここにHaskellの実装があります。これはかなりうまく機能します。コメントには、非常に優れた視覚化を備えたClojureバージョンへのリンクがあります。
両面から同時に検索できます。つまり、嵐の中で文字を変更してisValidWord（）を実行し、パワーの文字を変更してisValidWord（）を実行します。これらの2つの単語が同じである場合、パスが見つかりました。