物体间最短距离

Question

假设我有这样一个对象：

let objs = { obj1: [ 0, 10 ], obj2: [ 3, 9 ], obj3: [ 5, 12, 14 ] }

每个obj有多个距离点，但只应选择一个与其他obj的距离点相结合。

我可以根据上面的距离点以12种方式组合三个物体。

例如，它可以变成0,3,5；在这种情况下，三个对象之间的总距离为5-0，即5；

也可以是10，9，5，距离为10-5= 5；

组合也可以是0，3，12，距离为12-0= 12；

我打算实现的是找到最短的组合，在这种情况下，应该是10，9，12；距离是12-9 =3；

所以我已经考虑了一个一个地执行组合，我可以做嵌套循环来完成，但是这是非常低效率的。我能用什么最有效的方法来实现这一点？

Answer 1

您可以得到笛卡儿乘积，然后通过取一个具有较小的最大值和最小值的数组来减少数组。

​

let objects = { obj1: [ 0, 10 ], obj2: [ 3, 9 ], obj3: [ 5, 12, 14 ] },
    data = Object.values(objects),
    cartesian = data.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), [])),
    result = cartesian.reduce((a, b) => Math.max(...a) - Math.min(...a) < Math.max(...b) - Math.min(...b) ? a : b)

console.log(result);
console.log(cartesian.map(a => a.join(' ')));

.as-console-wrapper { max-height: 100% !important; top: 0; }

​

一种更快的方法使用排序数组，并且只按排序顺序接收每个数组的最后三个项。

这是不使用笛卡尔乘积的线性搜索。

指数δ

​

let objects = { obj1: [ 0, 10 ], obj2: [ 3, 9 ], obj3: [ 5, 12, 14 ] },
    data = Object
        .values(objects)
        .map((a, i) => a.map(v => [v, i]))
        .reduce((a, b) => a.concat(b))
        .sort((a, b) => a[0] - b[0] || a[1] - b[1]),
    parts = [undefined, undefined, undefined],
    result,
    i;

for (i = 0; i < data.length; i++) {
    parts[data[i][1]] = data[i][0];
    if (parts.some(v => v === undefined)) continue;
    if (!result || Math.max(...parts) - Math.min(...parts) < Math.max(...result) - Math.min(...result)) {
        result = parts.slice();
    }
}

console.log(result);
console.log(data);

.as-console-wrapper { max-height: 100% !important; top: 0; }

​

Answer 2

对于obj中的每个值v创建对(v，o)，然后根据对的第一个元素对所有对进行排序。它需要O(n log n)

现在，您希望从排序的序列中选择至少每个o中至少有一个在其中的一些连续元素。您可以使用散列映射在O(n log n) (或O(n) )中选择最佳答案。

从选择满足条件的序列的最小前缀开始。创建两个指针，连续选择元素的开始和结束。

Start = 1，end =x(其中x是每个对象在所选集合内的最小值)

然后尝试增加开始(删除所选子序列的第一个元素)，并在必要时增加结束。以结束值和开始值之间的差异最小为例，这是你的答案。

正如我所说的，要跟踪是否所有对象都在内部，请创建一个map /散列图，在该映射/散列映射中，您可以按照所选的顺序存储每个对象的数量。当您增加start时，您必须减少子序列中某些对象的数量。然后，您应该增加结束，直到每个对象o在所选的子序列中发生非零次数。(要获得O(n log )复杂性，可以存储有多少对象的值为0。当您增加任何，减少计数器，当您将任何对象的数量减少到0时，增加它)

结果总是正确的，不使用启发式。