如下问题:
对于一条线上的n个点,m个传感器。如何分配这些传感器,使得每个点都被一个传感器访问,并且使得所有传感器走过路径的最大值最小?
以下图为例:
橙色长方形为传感器,蓝色的点为需要经过的目标,数字为这些点的坐标。每个传感器走过的路程长度为3(1-4), 3(5-8),和0(10000-10000)。传感器均从左往右运动。上例为最优分配,如果把传感器放在任意其他点上,则总会有一个传感器走过的路程大于3。
如何解决这个问题?
如下问题:
对于一条线上的n个点,m个传感器。如何分配这些传感器,使得每个点都被一个传感器访问,并且使得所有传感器走过路径的最大值最小?
以下图为例:
橙色长方形为传感器,蓝色的点为需要经过的目标,数字为这些点的坐标。每个传感器走过的路程长度为3(1-4), 3(5-8),和0(10000-10000)。传感器均从左往右运动。上例为最优分配,如果把传感器放在任意其他点上,则总会有一个传感器走过的路程大于3。
如何解决这个问题?
假设n=m ,
那么每个点 上都有一个传感器。,
假设n=m+1;
S =两个传感器之间的距离+右端点传感器的路径
1. 求出 最小的 S
2. 左端点传感器的路径 = S
3. 删除右端点传感器
4. 所有传感器走过的路径的最大值 = S
假设n=m+x;
重复 步骤 1-4 x次;
恳请指教