2

これは、私の以前の質問をより具体的で簡単に表現できるようにすることを目的としています。

一般的な文字の長さの辞書から単語のリストを取得します。
このリストを並べ替えて、隣接する単語間でできるだけ多くの文字を共通に保つにはどうすればよいですか？

例1：

AGNI, CIVA, DEVA, DEWA, KAMA, RAMA, SIVA, VAYU
reorders to:  
AGNI, CIVA, SIVA, DEVA, DEWA, KAMA, RAMA, VAYU

例2：

DEVI, KALI, SHRI, VACH
reorders to:
DEVI, SHRI, KALI, VACH

最も単純なアルゴリズムは次のように思われます。何かを選択してから、最短距離を検索しますか？
ただし、DEVI-> KALI（1コモン）はDEVI-> SHRI（1コモン）と同等です
。最初の一致を選択すると、リスト全体で共通ペアが少なくなります（4対5）。

これは、完全なTSPよりも単純なはずですか？

4

5 に答える 5

3

あなたがやろうとしているのは、完全な重み付きグラフで最短のハミルトン経路を計算することです。ここで、各単語は頂点であり、各エッジの重みは、これら2つの単語間で異なる文字の数です。

たとえば、グラフのエッジは次のように重み付けされます。

     DEVI KALI SHRI VACH
DEVI X 3 3 4
KALI 3 X 3 3
SHRI 3 3 X 4
VACH 4 3 4 X

次に、お気に入りのTSP解決アルゴリズムを選択するだけで、準備は完了です。

于 2008-11-28T17:17:01.193 に答える
1

私の擬似コード：

  • 各ノードが単語を表すノードのグラフを作成します
  • すべてのノード間に接続を作成します（すべてのノードが他のすべてのノードに接続します）。各接続には、一般的な文字数である「値」があります。
  • 「値」が0の接続を削除します。
  • 最も高い値の接続を優先してグラフをウォークします。同じ値の接続が2つある場合は、両方を再帰的に試してください。
  • この特定の結果の単語間の距離の合計とともに、ウォークの出力をリストに保存します。使用した接続を単純に合計できるかどうか、ATMが100％確実かどうかはわかりません。自分で見て。
  • すべての出力から、値が最も高いものを選択します。

この問題はおそらくNP完全であり、辞書が大きくなるにつれてアルゴリズムの実行時間が耐えられなくなることを意味します。今のところ、それを最適化する方法は1つしかありません。グラフをいくつかの小さなグラフに切り取り、それぞれでコードを実行してから、リストに参加します。すべての順列を試してみるほど完璧な結果にはなりませんが、実行時間ははるかに良くなり、最終的な結果は「十分に良い」可能性があります。

[編集]このアルゴリズムはすべての可能な組み合わせを試行するわけではないため、完璧な結果を見逃す可能性があります。極大に巻き込まれる可能性さえあります。たとえば、値が7のペアがありますが、このペアを選択した場合、他のすべての値は1に下がります。このペアを使用しなかった場合、他のほとんどの値は2になり、全体的な最終結果がはるかに良くなります。

このアルゴリズムは、完璧さをスピードと引き換えにしています。世界最速のコンピューターを使用している場合でも、考えられるすべての組み合わせを試すには何年もかかる場合、ランタイムを制限する方法を見つける必要があります。

辞書が小さい場合は、すべての順列を作成して、最良の結果を選択するだけです。それらが特定の境界を超えて成長する場合、あなたは運命にあります。

別の解決策は、2つを混合することです。欲張りアルゴリズムを使用して、おそらくかなり良い「島」を見つけてから、「完全検索」を使用して小さな島を並べ替えます。

于 2008-11-26T08:50:25.957 に答える
0

これは、再帰的なアプローチで実行できます。擬似コード：

Start with one of the words, call it w
FindNext(w, l) // l = list of words without w
  Get a list l of the words near to w
  If only one word in list
    Return that word
  Else
    For every word w' in l do FindNext(w', l') //l' = l without w'

スコアを追加して、一般的なペアをカウントし、「より良い」リストを優先することができます。

于 2008-11-26T08:33:51.403 に答える
0

この問題には、n-ary グレイ コードという名前があります。英字を使用しているため、n = 26 です。グレイ コードに関するウィキペディアの記事では、問題について説明し、いくつかのサンプル コードが含まれています。

于 2008-11-26T11:45:48.927 に答える
0

BK-Treesを見てみるとよいでしょう。これにより、互いに一定の距離にある単語を効率的に見つけることができます。完全なソリューションではありませんが、おそらく 1 つのコンポーネントです。

于 2008-11-26T10:15:52.430 に答える