1

我在动态编程中有一个问题，如果我有一组覆盖目标的传感器（一个目标可能被多个传感器覆盖），如果知道每个传感器都有自己的成本，我如何才能找到传感器的最小成本子集？我对此想了很多，但我无法到达递归论坛来编写我的程序？贪心算法有时会给我错误的最小成本子集，我的问题是传感器在覆盖目标时重叠，有什么帮助吗？

例如：我有一组成本/重量 = {s1:1,s2:2.5,s3:2} 的传感器，我有三个目标 = {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]

请注意，RHS 上没有任何变化，因为两者都s1覆盖s2了t2。接下来是最后一行：

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

请注意，我必须添加s3到第一个答案，因为它具有最小的权重覆盖t3。

最后浏览答案列表会发现这[s2 : 2.5]是最好的候选人。

现在，我对动态编程没有那么自信，所以不确定我在这里所做的是否正确。如果有人可以确认/质疑我在这里所做的事情，那就太好了。

编辑：根据传感器的重量对列进行排序可能是有意义的。这样就可以轻松选择覆盖给定目标的重量最小的传感器。

于 2012-11-22T19:30:12.403 回答
0

这是我的建议，它不是动态编程，而是我能想到的最好的，这个问题很有趣，值得讨论。

将“部分解决方案”定义为包含目标、包含传感器、未决目标集合、成本的(T,S,P,C)元组。TSPC

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 回答
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 回答