4

アルゴリズムに関する簡単な質問があります。助けていただければ幸いです。

2 次元の点がいくつかあります。それらには正の重みが関連付けられています（サンプル問題が添付されています）。重みを最大化し、選択した 2 つの点が互いに重ならないサブセットを選択したい (たとえば、添付ファイルでは、A と C は同じ行にあり、同じ方法で選択できないため、両方を選択することはできません) A と B は同じ列にあるため、両方を選択することはできません。)貪欲な (または動的な) アプローチがあれば、使用できます。重複しない間隔選択アルゴリズムを認識していますが、ここでは使用できません。問題が 2 次元であるためです。

任意の参照またはメモをいただければ幸いです。

よろしく

添付ファイル: 問題の簡単なサンプル:

   
   A (30$) -------- B (10$)
   | |
   | |
   | |
   | |
   C (8$)
4

5 に答える 5

2

適切なソリューションで問題がなく、最適なソリューションを要求しない場合は、ヒューリスティック アルゴリズムを使用してこれを解決できます。

Sを点の集合とし、-w(s)加重関数とします。

重み関数を作成しますW:2^S->R(S のサブセットから実数へ):

W(U) =    - INFINITY                         is the solution is not feasible
          Sigma(w(u)) for each u in U        otherwise

next:2^S -> 2^2^S関数( のサブセットを取得し、 のサブセットのSセットを返す関数S)も作成します。

next(U) = V   you can get V from U by adding/removing one element to/from U

ここで、そのデータが与えられたら、遺伝的アルゴリズムやヒル クライミングなど、人工知能の本の任意の最適化アルゴリズムを呼び出すことができます。

たとえば、ランダムな再起動を伴うヒル クライミングは次のようになります。

1. best<- -INFINITY
2. while there is more time
3. choose a random subset s
4. NEXT <- next(s)
5. if max{ W(v) | for each v in NEXT} < W(s): //s is a local maximum
   5.1. if W(s) > best: best <- W(s) //if s is better then the previous result - store it.
   5.2. go to 2. //restart the hill climbing from a different random point.
6. else:
   6.1. s <- max { NEXT }
   6.2. goto 4.
7. return best //when out of time, return the best solution found so far.

上記のアルゴリズムはいつでも使用できます。つまり、時間があれば、より良い結果が得られます。

于 2012-07-04T09:25:54.677 に答える
1

これは線形代入問題として扱うことができ、ハンガリーのアルゴリズムのようなアルゴリズムを使用して解決できます。アルゴリズムはコストの合計を最小化しようとするため、重みを無効にして、それらをコストとして使用します。行を列に割り当てると、必要なポイントのサブセットが得られます。すべての (行、列) ペアに関連するポイントがあるわけではない場合のスパース バリアントがありますが、これらに大きな正のコストを使用することもできます。

于 2012-07-04T05:19:49.250 に答える
0

これは 2 項制約の最適化問題と考えることができ、さまざまなアルゴリズムがあります。この問題に対する最も簡単なアルゴリズムは、バックトラッキングとアーク伝搬です。ただし、最悪の場合指数関数的な時間がかかります。問題の幾何学的性質を利用するための特定のアルゴリズムがあるかどうかはわかりません。

于 2012-07-04T04:46:40.043 に答える
0

これは、指数関数的な時間の複雑さを持つ非常に単純な動的計画法アプローチによって解決できます

s = {A, B, C ...}

getMaxSum(s) = max( A.value + getMaxSum(compatibleSubSet(s, A)),
                    B.value + getMaxSum(compatibleSubSet(s, B)),
                    ...)

wherecompatibleSubSet(s, A)は A と重複しない s のサブセットを取得します

それを最適化するために、各サブセットの結果を記憶することができます

于 2012-07-04T06:00:03.783 に答える
0

それを行ういくつかの方法：

  • 制約を無視しながら、最大の重みから外れたサブセットから最小の重みから外れたサブセットに順序付けられたサブセットを生成する関数を作成します。

  • 次に、制約を尊重するサブセットが表示されるまで、この関数を繰り返し呼び出します。

パフォーマンスを向上させるために、たとえば、同じ行ではない制約を尊重するが、同じ列ではない制約を無視する、それほど愚かではないジェネレーター関数を作成できます。

于 2012-07-04T06:47:10.777 に答える