3

2 つの単語リストの関数に興味があります。これは、それらの間の順序にとらわれない編集距離を返します。

つまり、引数は (たとえばスペースで区切られた) 単語の 2 つのリストになり、戻り値はリスト内の単語の編集 (またはレーベンシュタイン) 距離の最小合計になります。

"cat rat bat"との間の"rat bat cat"距離は 0 になります。 と の間の距離は"cat rat bat"と"fat had bad"の間の距離と"rat bat cat"同じ"had fat bad"になります。

私の直感 (コンピューター サイエンスの授業で育まれていない) では、ブルート フォースを使用する以外に解決策は見つかりません。

   |had|fat|bad|   a solution
---+---+---+---+ +---+---+---+
cat| 2 | 1 | 2 | |   | 1 |   |
---+---+---+---+ +---+---+---+
rat| 2 | 1 | 2 | | 3 |   |   |
---+---+---+---+ +---+---+---+
bat| 2 | 1 | 1 | |   |   | 4 |
---+---+---+---+ +---+---+---+

最初の行から始めて、列を選択し、既にアクセスした列に再度アクセスすることなく、次の行に移動します。すべての組み合わせを試すまで、これを何度も繰り返します。

私には、これは巡回セールスマンの問題に少し似ているように思えます。そうですか、どうすれば私の特定の問題を解決できますか?

4

2 に答える 2

8

左側のグリッドで既に示したように、単語のペアごとに編集距離を計算することから始めることができます。これは、多項式時間 (n^2 編集距離の計算) で簡単に実行できます。

次に、問題を「最小加重二部マッチング」、または同等に「最大加重二部マッチング」として説明できます。これは、多項式時間でも実行できます (巡回セールスマンよりも高速です)。http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Maximum_matchings_in_bipartite_graphsを参照してください。

于 2010-04-26T18:26:45.227 に答える
1

これは、レーベンシュタイン距離アルゴリズムを打ち破る絶好の機会のようです。このアルゴリズムは、探していること (2 つの文字列間の最小距離) を正確に実行し、非常に効率的です。巡回セールスマンのバリエーションである限り、これは問題の構造により多項式時間で解決できるため、ノーです。お役に立てれば。

于 2010-04-26T19:01:36.700 に答える