算法移动重叠间隔，直到没有重叠

Question

我有一个重叠间隔的排序列表，间隔之间从不包含，例如

[(7, 11), (9, 14), (12,  17)]

输出的约束是使每个元素尽可能接近它的原点(间隔的中间)，保留输入的顺序，并删除所有重叠。只有一个近似解是必要的。示例输入的预期结果是:

[(5,9), (9, 14), (14, 19)]

我只知道在一些模拟中解决这个问题的方法样式:将每个元素在自由方向上移动一些值迭代直到所有的重叠都被移除。

是否有现有的算法来解决这个问题?

Answer 1

查找总体平均值:

在我们的例子中:

(7 + 11 + 9 + 14 + 12 + 17)/6 = 11.667

查找总长度:

(11-7) + (14-9) + (17-12) = 4 + 5 + 5 = 14;

查找新的最小值/最大值;

14/2 = 7
11.667 - 7 = 4.667
11.667 + 7 = 18.667

可以四舍五入

4.667 ~ 5
18.667 ~ 19

从最小值开始，按间隔

创建分段

(5, (11-7)+5) = (5,9)
(9, (14-9)+9) = (9,14)
(14, (17-12)+14) = (14,19)

注意:

此方法不会使元素尽可能与原始元素相等，但会考虑到它们的相对值(保留中心)，使它们尽可能接近原始元素

编辑:

如果你想保持所有间隔的平均值尽可能接近原始值，你可以实现一个数学解决方案。

问题的输入是:

<子> = 1(<子> 1,1 ,<子> 1,2 ),…, <子> n =(1 <子> n, , <子> n, 2

我们将定义:

ai

<子> 1 = <子> 1,2 ——<子> 1,1子> p>b₁ = (d, d+ai₁)

b <子> n = (d +总和(ai <子> 1 . . ai <子> n - 1 ), d +总和(ai <子> 1 . . ai <子> n ))

bi <子> 1 = <子> 1,2 - b <子> 1,1子> /blockquote>

我们需要找到一个'd'，例如:

s =总和(abs(<子> 1,1 + <子> 1,2子> 1,1 + b <子> 1,2子> /blockquote>

min(s)是我们想要的

在我们的例子中:

<子> = 1(7、11),ai <子> 1 = 4,一个<子> avg1子> p> <子> 2子> 2 = 5,一个<子> avg2子> p> <子> 3 =(12日7),ai <子> 3 = 5,一个<子> avg3子> p> b <子> 1 = (d, d + 4) b <子> avg1子> p> b <子> 2 = (d + 4 d + 9) b <子> avg2子> p> b <子> 3 = (d + 9, d + 14) b <子> avg3子> p> s = abs (9 - (d + 2)) + abs (11.5 - 6.5 (d +)) + abs (14.5 - 11.5 (d +)) = abs (7 d) + abs (5 d) + abs (3 d)

现在计算导数以找到最小/最大或遍历d以获得结果。在我们的例子中，您需要从3迭代到7

Answer 2

给定解必须是保序的，我们可以将这个问题表述为一个线性规划。设[a_i， b_i]为第i个区间。设变量x_i为第i个区间的左移，y_i为第i个区间的右移。

最小化总和我<子> (x <子> + y <子>)
根据
(*)我:我<子> - x <子> + y <子>≤子> <我+> - x <子> i + 1 + y <子> i + 1
对于所有i: x_i， y_i≥0

通过引入变量z_i重写约束(*)。

所有我:

x <子> - y <子> - x <子> i + 1 + y <子> i + 1 - z <子> = 0
我对所有我:z <子> ≥我<子> - <子> i + 1

现在问题被简化为计算最小成本循环，这可以在多时间内完成。然而，我有一种感觉，这个问题有一个更直接的解决办法。

图看起来像

        (*)
    ---- | ----
   /    z|     
  /     i|      
 /   xi  |  xi+1 
|/ <---- v <---- |
...     (*)     ...
   ---->   ---->
    yi     yi+1