我在动态编程中有一个问题，如果我有一组覆盖目标的传感器（一个目标可能被多个传感器覆盖），如果知道每个传感器都有自己的成本，我如何才能找到传感器的最小成本子集？我对此想了很多，但我无法到达递归论坛来编写我的程序？贪心算法有时会给我错误的最小成本子集，我的问题是传感器在覆盖目标时重叠，有什么帮助吗？
例如：我有一组成本/重量 = {s1:1,s2:2.5,s3:2} 的传感器，我有三个目标 = {t1,t2,t3}。传感器覆盖范围如下：={s1:t1 t2,s2:t1 t2 t3,s3:t2 t3} 我需要通过动态编程获得最小成本子集，对于上面的示例，如果我使用贪心算法我会得到 s1,s3 但是正确答案只有 s2
我想到了一些东西，但我对它不是 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]是最好的候选人。
现在，我对动态编程没有那么自信，所以不确定我在这里所做的是否正确。如果有人可以确认/质疑我在这里所做的事情，那就太好了。
编辑：根据传感器的重量对列进行排序可能是有意义的。这样就可以轻松选择覆盖给定目标的重量最小的传感器。
这是我的建议，它不是动态编程，而是我能想到的最好的，这个问题很有趣，值得讨论。
将“部分解决方案”定义为包含目标、包含传感器、未决目标集合、成本的(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
这是我解决这个问题的算法。它是解决问题的递归方法。
伪代码：
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] 值并在需要时使用以避免重复。希望这可以帮助。不过可能有更好的方法。