假设我有一个对象，它具有以下属性：
let objs = { obj1: [ 0, 10 ], obj2: [ 3, 9 ], obj3: [ 5, 12, 14 ] }
每个对象都有多个距离点，但只能选择一个与其他对象的距离点组合。
基于上述距离点，我可以通过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；
因此，我考虑逐个执行组合；我可以使用嵌套循环来执行，但效率非常低。
有什么最有效的方法可以实现这一点？
你可以获取笛卡尔积，然后通过选取最大值和最小值之间较小差值的数组来缩减它。
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; }更快的方法使用排序后的数组，并按照排序顺序仅获取每个数组的最后三个项目。
这是一种线性搜索，而不使用笛卡尔积。
index values delta
----- -------------------- -----
0 0 10
1 3 9
2 5 12 14
-------- 5
-- ----- 9
-------- 5
-------- 3 <-- min
------ -- 5
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; }我认为嵌套/递归循环是最好的算法，最坏情况下仍需要检查所有组合。但是，我认为应用分支定界算法会得到良好的优化效果，因为它会提前修剪不太好的距离分支-同时利用你已经按对象排序的点，所以您可以一次修剪多个选择。
实际上，对于每个对象，我们可以修剪为只有两个选择，即选择范围最接近且最接近当前已选择的区间。因此，我估计最坏情况下的复杂度为O(k * (2+log k)n) （给出n个平均有k个已排序点的对象），而不是朴素枚举的O(kn)。
诚然，这比尼娜的第二种方法的O(kn log(kn) + kn²)或马拉斯算法的O(kn log(kn))更糟糕-可以通过在已排序列表上使用k路归并算法进一步优化至O(kn log n)。