Minimum cost subset of sensors covering targets

问题:

I have a question in dynamic programming, If I have a set of sensors covering targets ( a target might be covered by mutiple sensors) how can I find the minimum cost subset of sensors knowing that each sensors has its own cost? I thought a lot about this, but I cant reach the recursive forumla to write my program? greedy algorithm gives me wrong minimum cost subset sometimes, and my problem is that sensors overlap in covering targets, any help?

For Example: I have set of sensors with cost/weight = {s1:1,s2:2.5,s3:2} and I have three targets = {t1,t2,t3}. sensors coverage as following:={s1:t1 t2,s2:t1 t2 t3,s3:t2 t3} I need to get minimum cost subset by dynamic programming, for the above example if I use greedy algorithm I would get s1,s3 but the right answer is s2 only

回答1:

check section 3 it labels the Dynamic programming algorithm for the MWCDC

https://docs.google.com/viewer?a=v&q=cache:5vPrmVg7jDMJ:www.cs.iit.edu/~wan/Journal/tcs10.pdf+&hl=en&gl=us&pid=bl&srcid=ADGEESglfvp6XtFIkqDZZ-E-Tun4AWPTZV_V7z32pTvJ05K6tdkCoefpsAxPxdK44jYDvPNLDEwYI8uK-PMlLGthsaV8-ow63utalgWPnyLrUUBKhoTTVuYwUiKSHlCXU-HXKHVeHvh4&sig=AHIEtbQGka8F39MaT8yAy4G9Kvv8TPsvJA

回答2:

I thought of something but I'm not 100% confident about it, here it goes:

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

Now, we build a matrix representing the target x sensor map:

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

So the rows are targets (t1 -> R0, t2 -> R1 etc.), and columns represent which sensors cover them.

Next we process row-by-row while collecting the list of sensors that will cover the current target set. For an example:

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

Notice that we're building a list of answers. Then we proceed to the next row, where we need to add t2 to our set of targets while calculating the minimum sensor weight required to do so.

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

Note that nothing changed on the RHS because both s1 and s2 covers t2 as well. Next the final row:

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

Notice that I had to add s3 to the first answer because it had the minimum weight covering t3.

A final walk through the list of answers would reveal that [s2 : 2.5] is the best candidate.

Now, I'm not that confident with dynamic programming, so not sure whether what I'm doing here is correct. Will be great if someone can confirm / dispute what I have done here.

EDIT: May be it makes sense to have the columns sorted according to the weight of the sensors. So that it becomes easy to select the sensor with the lowest weight covering a given target.

回答3:

Here's my proposal, it's not a dynamic programming, but is the best I can come up with, the problem is interesting and worth a discussion.

---

Define "partial solution" to be tuple (T,S,P,C) where T is covered targets, S is included sensors, P is the set of pending targets, C is the cost.

W is the current working set of partial solutions, which initially contains only ({}, {}, X, 0), i.e. cost zero, nonempty is only the set of pending targets. W can be maintained as a heap.

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

回答4:

Here is my algorithm for this problem. Its a recursive approach for the problem.

Pseudocode :

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);
  }
}

The Sensors_Used List can be avoided if those details are not needed.

Further Memoization can be introduced to this if the TargetsReached List can be mapped to an int. Then [Current_Sensor, TargetsReached] value can be saved and used when needed to avoid repetition. Hope this helps. There might be better approaches though.