2 drizzlex DrizzleX 于 2015.06.15 16:01 提问

如何用多个传感器访问一条线上的多个点?

如下问题:

对于一条线上的n个点,m个传感器。如何分配这些传感器,使得每个点都被一个传感器访问,并且使得所有传感器走过路径的最大值最小?

以下图为例:

图片说明

橙色长方形为传感器,蓝色的点为需要经过的目标,数字为这些点的坐标。每个传感器走过的路程长度为3(1-4), 3(5-8),和0(10000-10000)。传感器均从左往右运动。上例为最优分配,如果把传感器放在任意其他点上,则总会有一个传感器走过的路程大于3。

如何解决这个问题?

1个回答

smils
smils   2015.06.16 12:54

假设n=m ,
那么每个点 上都有一个传感器。,
假设n=m+1;
S =两个传感器之间的距离+右端点传感器的路径
1. 求出 最小的 S
2. 左端点传感器的路径 = S
3. 删除右端点传感器
4. 所有传感器走过的路径的最大值 = S
假设n=m+x;
重复 步骤 1-4 x次;
恳请指教

Csdn user default icon
上传中...
上传图片
插入图片