1

動的計画法で質問があります。ターゲットをカバーするセンサーのセットがある場合 (ターゲットは複数のセンサーでカバーされる場合があります)、各センサーに独自のコストがあることを知っているセンサーの最小コストのサブセットを見つけるにはどうすればよいですか? 私はこれについて多くのことを考えましたが、プログラムを書くために再帰的なフォーラムに到達できませんか? 貪欲なアルゴリズムは時々私に間違った最小コストサブセットを与えます、そして私の問題はセンサーがターゲットをカバーするのに重なることです、何か助けはありますか?

例: コスト/重量 = {s1:1,s2:2.5,s3:2} のセンサーのセットがあり、3 つのターゲット = {t1,t2,t3} があります。={s1:t1 t2,s2:t1 t2 t3,s3:t2 t3} 動的計画法によって最小コストのサブセットを取得する必要があります。上記の例で貪欲なアルゴリズムを使用すると、s1,s3 が得られますが、正解はs2だけ

4

4 に答える 4

0

私は何かを考えましたが、それについて100％自信がありません。

S = {s1 : 1, s2 : 2.5, s3 : 2}
M = {s1 : t1t2, s2 : t1t2t3, s3 : t2t3}

target x sensor次に、マップを表すマトリックスを作成します。

[1, 1, 0]
[1, 1, 1]
[0, 1, 1]

したがって、行はターゲット(t1 -> R0, t2 -> R1 etc.)であり、列はどのセンサーがそれらをカバーするかを表します。

次に、現在のターゲットセットをカバーするセンサーのリストを収集しながら、行ごとに処理します。例：

Row - 0:
{t1} -> [s1 : 1], [s2 : 2.5]

回答のリストを作成していることに注意してください。次に、次の行に進みます。ここで、必要t2な最小センサーウェイトを計算しながら、ターゲットのセットに追加する必要があります。

Row - 1:
{t1, t2} -> [s1 : 1], [s2 : 2.5]

s1とs2カバーの両方があるため、RHSでは何も変更されていないことに注意してくださいt2。次の最後の行：

Row - 2:
{t1, t2, t3} -> [s1, s3 : 3], [s2 : 2.5]

最初の回答に追加s3する必要があることに注意してください。これは、最小の重量カバーを持っていたためですt3。

回答のリストを最後に確認すると、それ[s2 : 2.5]が最良の候補であることがわかります。

今、私は動的計画法にそれほど自信がないので、ここで行っていることが正しいかどうかわかりません。誰かが私がここでしたことを確認/異議を唱えることができれば素晴らしいでしょう。

編集：センサーの重みに従って列を並べ替えることは理にかなっているかもしれません。これにより、特定のターゲットをカバーする最小の重量のセンサーを簡単に選択できるようになります。

于 2012-11-22T19:30:12.403 に答える
0

これがこの問題に対する私のアルゴリズムです。問題に対する再帰的なアプローチです。

擬似コード:

MinimizeCost(int cost , List targetsReached, List sensorsUsed, int current_sensor) {

if(targetsReached.count == no_of_targets ) {
    if(cost < mincost ) {
          mincost = cost;
          minList = sensorsUsed;
            }       
    return;
    }

   if(current_sensor > maxsensors)
         return;
   else {
         // Current Sensor is to be ignored 
     MinimizeCost(cost , targetsReached, sensorsUsed, current_sensor +1 );

         // Current Sensor is Considered 
     int newcost = cost + sensor_cost[current_sensor];  
     sensorsUsed.Add(current_sensor);
     AddIfNotExists(targetsReached, targets[current_sensor]);
     MinimizeCost(newcost, targetsReached, sensorsUsed, current_sensor+1);
  }
}

これらの詳細が必要ない場合は、Sensors_Used リストを避けることができます。

TargetsReached リストを int にマップできる場合は、これにさらにメモ化を導入できます。次に、[Current_Sensor, TargetsReached] 値を保存して、繰り返しを避けるために必要なときに使用できます。お役に立てれば。ただし、より良いアプローチがあるかもしれません。

于 2012-11-27T13:49:30.460 に答える
0

これが私の提案です。これは動的プログラミングではありませんが、私が思いつくことができる最高のものです。問題は興味深いものであり、議論する価値があります。

「部分解」を、カバーされるターゲット、含まれるセンサー、保留中のターゲットのセット、コストのタプル(T,S,P,C)としてT定義SしPますC。

Wは部分解の現在のワーキング セットであり、最初は のみを含みます({}, {}, X, 0)。つまり、コストはゼロです。空でないのは保留中のターゲットのセットのみです。Wヒープとして維持できます。

W = { ({}, {}, X, 0) }
repeat
  p = select and remove from W the partial solution with the minimum cost
  if p.P is empty
     return p
  t = select from p.P the target, covered by the minimum number of sensors
  for each sensor s, covering t, which is not in p'.S
     p' = new partial solution, copy of p;
     p'.S += {s};
     p'.C += cost(s);
     for each target t' covered by s
       p'.T += {t};
       p'.P -= {t};
     end for
     W += {p'}
  end for
end repeat
于 2012-11-22T19:46:01.790 に答える