5

申し訳ありませんが、次のアルゴリズムのアルゴリズムまたは問題の名前がわかりません。私は問題を述べ、次に私が試したことを述べます。おそらく誰かが私を正しい方向に向けることができます.

あなたがアイテムのバッグを持っていると想像してください（注文されていない、重複は許可されています）。実際には、この緩和が役立つ場合に備えて、バッグには 2 ～ 20 個のアイテムが含まれる場合があります。

目標は、バッグ内のすべてのアイテムを任意の順序で含む最小の長さのチェーン (チェーンの概念が異なる場合の順序付けられたリンク リスト) を見つけることです。

チェーンは、開始トークン (バッグに存在しない) とそれに続く任意の数のアイテムと、それに続く終了トークン (これもバッグに存在しない) で構成されます。

チェーンは、n 個のタプル (順序が重要です) をつなぎ合わせることによって形成されます。さらに緩和するために、n の値はすべてのタプルで同じであるとしましょう。実際には、n = 3 で作業しています。要素が重複している場合、チェーンは連結ではなく「ブレンド」される場合があります。たとえば、(a,b,c) と (c,d,e) を考えてみましょう。は (a,b,c,d,e) のように結合できます。同様に、(a,b,c) と (b,c,d) を結合して (a,b,c,d) にすることもできます。一部のタプルでは最初の位置に開始トークンがあり、一部のトークンでは最後の位置に終了トークンがあり、もちろん問題の解決策が得られます。

したがって、問題の正確な解決策は一般的に扱いにくいように思えます。問題の「良い」解決策を得るには、ある種の最適化アルゴリズムが必要です。私が一緒に暮らすことができる「良い」ソリューション。

私が始めたのは貪欲なアプローチです。最初のパスで、バッグ内の要素の数が最も多いタプルを見つけ、恣意的に関係を壊します。これまでに構築したチェーンを保持するデータ構造を作成し、選択したタプルをこのデータ構造に貼り付けます。問題を開始トークン側と終了トークン側の 2 つのサブ問題に分割します。サブ問題 1 のデータ構造の最初のトークンが開始トークンになり、サブ問題 2 の最後のトークンが終了トークンになるまで、できるだけ早く停止条件を見つけようとするように (開始または終了トークンに応じて) チェーンを成長させます。副問題について）できるだけ早くバッグの中身を使い果たしようとします。

この問題をどこかで見た人はいますか? このアルゴリズムを改善する (または正しく動作させる) 方法について何か考えはありますか? これは私が取り組んでいる実際の問題であり、はるかに大きなシステムのスマートな部分であり、おもちゃの問題でも宿題の問題でもありません。

編集

今日はパソコンから離れていてごめんなさい。些細すぎず、複雑すぎて見えない解決策の例を投稿しようと思います。

与えられた:

  1. Bag = {A, B, C, D} （例としてセットにしていますが、各アイテムは複数回出現する可能性があります）
  2. / = Start Token
  3. \ = End Token

  4. 3-タプル (トリプル): 命名を簡単にするために、これらに ag というラベルを付けます。この問題では、小文字には実際の機能はありません。

    (/,A, E) a
(/,C, D) b
(/,G, H) c
(D,B, A) d
(C,G, H) e
(B,A, \) f
(G,H, \) g

解決策: b、d、および f を連結すると、 が得られ(/,C,D,B,A,\)ます。
これは、開始トークンと終了トークンの両方を数える場合、長さ 6 のバッグ内のすべての要素を含む可能な限り短いチェーンです。一般に、可能な最短経路の長さは |BAG| です。+ 2 (実際に存在する場合)。私の問題文がより意味のあるものになることを願っています。

4

1 に答える 1

2

最大 20 個のアイテムしかないので、適切な時間 (たとえば 1 分以内) で正確な解を計算できると思います。

1 つのアプローチは、状態が次のように与えられる動的計画法を使用することです。

A) a 20 bit number m (which will represent which items have been visited so far)
B) a number b in the range 1..20 
C) a number c in the range 1..20

この状態は、Start,?,?,?,...,?,b,cie b と c が最新の 2 つの要素であるようなチェーンに対応します。

数値 m は、チェーン内でアクセスされた他の要素を表すビットフィールドです。つまり、m のビット i は、チェーンがバッグに i 番目の要素を含む場合にのみ 1 になります。

最短チェーンを見つけるアルゴリズムは次のようになります。

  1. S = start トークンを持つすべてのタプルで構成される状態のセットとします。(これらの状態はすべて同じチェーン長 2 になります)
  2. 3 以上のチェーンの長さ y ごとに、S のすべての状態を調べ、適切なタプルを使用して長さ y になるように状態を拡張してみてください。これが可能な場合は、セット S に拡張状態を追加します。
  3. ビットフィールド m がすべてのビットが設定された状態で終了する場合にのみ、終了トークンを含むタプルの追加を許可します。

最終状態を含むタプルを追加できた場合は、すべての要素を含む最短のチェーンが見つかりました。

バッグ内の N 個のアイテムの場合、およそ 2^NNN の状態があり、ほぼ管理可能です。

于 2012-10-21T17:54:06.787 に答える