算法 求助一个算法问题
本来想问的是二维的问题，但是想了想，还是先从一维开始吧
假设有一条直线 L，起点的 x 轴坐标为 0，终点的 x 轴坐标为 10. 在该直线上有一组点，现在我们假设有 4 个点，每个点都能在直线 L 的某个范围内自由移动，定义如下： 点 a 可以在 (0..4) 之间自由移动， 点 b 可以在 (3..5) 之间自由移动， 点 c 可以在 (0..8) 之间自由移动， 点 d 可以在 (7..9) 之间自由移动。
求一种算法，可以找到这些点的坐标，使得这些点彼此之间尽量远离。
这里需要考虑 彼此之间尽量远离 的含义，从直观的角度考虑，应该就是这些点尽量均匀得分布在直线上，但如何从数学的角度描述，我还没想清楚，毕竟我是小学文化水平的人。
对我来说至少有 2 个难点：
- 没有一个合适的初始的点。
- 点的移动没有最小单位的限制，比如可以移动 1，也可以是 0.1，0.01，依此类推。
补充： 如果移动距离完全不做限制，我觉得不太靠谱。那么假设单位移动距离为 0.01，那么如果没有一个良好的算法，直线又比较长，计算量怕是比较巨大。。。
先提一个不均匀，尽量两端分散的算法：
- 将所有的 range 合并，找到几何上最远的两个点，这样就确定了两个点；
- 将剩余的点和 range 重复步骤 1。
然后考虑尽量均匀分布：
- 令两个目标点分别为 -max 和 +max；
- 在合并的 range 里找到最接近目标的两个点；
- 利用这两个点的距离和总点数计算出均匀分布时，靠近两侧的两个目标点
- 将剩余的点和 range 重复步骤 2。
你这个题 二维和一维完全不是一个难度啊。
如果全部分布在一条直线上，你要保证点之间尽量远离，那么左边界最小的地方必然有一个点，右边界最大的地方必然有一个点， 比如你的例子（所有的端点都在 0 到 9 之间分布）为了保证远离 0 和 9 必各有一个点 剩下的位置选择 3 和 6，就能得到（0,3,6，9）。 你只需要遍历找出 能最接近 3 和 6 的点就可以
剩下两个点就在 两个端点中间平均的位置，属于越靠近，那么平均距离越小。
接下来就是比较较小端点的右边界 和较大端点的左边界（哪个更接近中间的端点了
抛砖引玉：一般是否均匀分布，都可考虑一下方差的概念及应用 1.假设 a,b,c,d，每个点的可挪动位置范围 [a_x，a_y](b,c,d 诸如此类） 2.某一个时间点 t, 每个点的位置是 a_t（b,c,d 诸如此类），a_t 要满足在 [a_x，a_y] 区间范围内。 3.a 到 b 的位置的距离记作 a_t - b_t 的绝对值，a 到 c 的位置记作 a_t - c_t 的绝对值，这样 a 获得到 b、c、d 三个绝对值距离，b 也同样获得三个绝对值距离，c,d 均如此。 4.要求这些距离尽量均匀，也就是方差尽可能小，算一下他们的均匀分布状态下的方差（方差），然后比较大小。 5.t 可以根据移动的距离 0.01 一点点迭代循环计算。
killernova
回复
Umm...我是凭感觉，感觉描述的场景可能是需要做类似 LBS 类的应用，具体你再权衡权衡 GeoHash 是不是适合～
理论上如果需要在二维空间上计算物体间远近，都可以试试 GeoHash，坐标不一定非得是经纬度，从 0 到 10，从 0 到 1 这样的自定义坐标也可以的，原理上都是做分区编码，然后找最近或最远编码。