o****i
发帖数: 1706 | 1 Consider a straight highway in the plane which can be modelled by a
horizontal strip in the plane. A finite set T of targets are located on the
highway, and a finite set S of wireless sensors are located outside of the
highway. A sensor s can monitor a target t if and only if the Euclidean
distance between s and t is at most one. Suppose that each sensor s has a
positive cost c and each target t can be monitored by at least one sensor in
S. Consider a subset S1 of sensors in S. S1 is said to be a cover if each
target in T is covered by at least one sensor in S1. The cost of S0 is the
total costs of the sensors in S0. The objective is to compute a cover S0 of
minimum cost. Please develop a polynomial time algorithm and write program
to implement it
是作业题，大家给我个思路吧.. |
y********9
发帖数: 130 | |
b*********h
发帖数: 103 | 3 每个 s 能覆盖一段连续的 t，然后按左端点排序，然后贪心合并 |
e******o
发帖数: 757 | 4 大牛
【在 b*********h 的大作中提到】
: 每个 s 能覆盖一段连续的 t，然后按左端点排序，然后贪心合并
|
g*********e
发帖数: 14401 | 5
每个s cost不一样的吧
【在 b*********h 的大作中提到】
: 每个 s 能覆盖一段连续的 t，然后按左端点排序，然后贪心合并
|
o****i
发帖数: 1706 | 6 对的，用greedy感觉不能做到最小cost吧，比如说3个t,2个s,最左边的那个s cost2,
只覆盖1个t,第二个s cost 5，不过覆盖所有3个t.如果greedy的话，那不是最优解就要
两个s都被加入子集了吗？其实只要第二个s就够了。 |
l***i
发帖数: 1309 | 7 greedy seems to work as long as you handle sensors with same x coordinate
correctly.
From the statement, sensors have the same cost and the same coverage.
=====================================================================
A sensor s can monitor a target t if and only if the Euclidean
distance between s and t is at most one. Suppose that each sensor s has a
positive cost c |
o****i
发帖数: 1706 | 8 no, positive cost but may varied...
【在 l***i 的大作中提到】
: greedy seems to work as long as you handle sensors with same x coordinate
: correctly.
: From the statement, sensors have the same cost and the same coverage.
: =====================================================================
: A sensor s can monitor a target t if and only if the Euclidean
: distance between s and t is at most one. Suppose that each sensor s has a
: positive cost c
|
