我有一组元素，元素之间的距离函数满足三角不等式。
我想找到相距最远的一对元素。
有没有比尝试所有配对更好的已知解决方案？
最佳答案
如果您测量点 a 到点 b、c 和 d 的距离，您会发现 |ab| + |交流| < |ad|，那么你知道 |bc|比 |ad| 短，不需要测量 |bc|。所以并不是所有的对都需要检查以找到最长的距离。
一个可能的算法是:
从测量点 a 到所有其他点的距离开始，找到距离 a 最远的点 n，然后给出所有对 b,x，其中 |ab|+|ax| < |一个|距离 |ab|+|ax| (因为那是他们的最大可能距离)。
对 b 点做同样的事情，只测量那些尚未设置的距离。检查你是否找到了一个新的最大值，然后再次给出 |bc|+|bx| 的所有对 c,x < 最大距离 |bc|+|bx|。
继续对 c、d、... 点执行此操作
在最好的情况下，您可以在仅进行 N-1 次测量后找到一组 N 个点中的最长距离(如果 |ax| 是与 a 的任何其他距离的两倍)。在最坏的情况下，您需要测量每一对(如果最短距离超过最长距离的一半，或者如果您在遍历这些点的顺序上不走运)。
如果您想将距离测量的数量减少到绝对最小值，并且对于每个未知距离 x,y，您检查每个先前存储的值 |ax|+|ay|、|bx|+|by|、|cx |+|周期| ...查看它是否小于当前最大值并因此可以用作 |xy| 的值，测量次数大大减少。
在方形 2D 空间中的 1000 个随机点上运行此算法通常需要 499,500 次测量，返回最大距离的测量值在 2,000 到 10,000 之间(或总数的 0.4% 到 2%，平均约为 1 %)。
这并不一定意味着该算法在实践中比测量每个距离要快得多；这取决于与避免测量所需的循环、添加和比较的组合相比，测量的成本有多高。
正如@mcdowella 所指出的，随着空间维数的增加，这种方法的效率会降低。点数也有很大的影响。下表显示了相对于线对总数必须执行的测量次数。这些是在“正方形”空间中随机分布点的测试的平均值(即所有维度的坐标都在同一范围内)。如您所见，此方法最适用于 2D 或 3D 空间中具有许多点的几何问题。但是，如果您的数据在某些方面存在严重偏差，则结果可能会有所不同。
10 points (45 pairs) 100 points (4950 pairs) 1000 points (499500 pairs) dim measurem. % of total measurem. % of total measurem. % of total 1 16.6674 37.04 221.17 4.47 4877.97 0.98 2 22.4645 49.92 346.77 7.01 5346.78 1.07 3 27.5892 61.31 525.73 10.62 7437.16 1.49 4 31.9398 70.98 731.83 14.78 12780.02 2.56 5 35.3313 78.51 989.27 19.99 19457.84 3.90 6 38.1420 84.76 1260.89 25.47 26360.16 5.28 7 40.2296 89.40 1565.80 31.63 33221.32 6.65 8 41.6864 92.64 1859.08 37.56 44073.42 8.82 9 42.7149 94.92 2168.03 43.80 56374.36 11.29 10 43.4463 96.55 2490.69 50.32 73053.06 14.63 20 44.9789 99.95 4617.41 93.28 289978.20 58.05 30 44.9996 99.999 4936.68 99.73 460056.04 92.10 40 4949.79 99.99 496893.10 99.48 50 4949.99 99.9999 499285.80 99.96 60 499499.60 99.9999
正如预期的那样，测试结果在更高维度上变得可预测，离群值之间只有百分之几，而在 2D 中，一些测试用例需要比其他测试用例多 30 倍的测量值。
关于algorithm - 具有距离函数的集合的最大直径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35923497/