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

Question

如下问题：

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

以下图为例：

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

如何解决这个问题？

Answer 1

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