算法 求助一个算法问题

killernova · 2022年06月16日 · 最后由 oatw 回复于 2022年06月20日 · 384 次阅读

本来想问的是二维的问题,但是想了想,还是先从一维开始吧

假设有一条直线 L,起点的 x 轴坐标为 0,终点的 x 轴坐标为 10. 在该直线上有一组点,现在我们假设有 4 个点,每个点都能在直线 L 的某个范围内自由移动,定义如下: 点 a 可以在 (0..4) 之间自由移动, 点 b 可以在 (3..5) 之间自由移动, 点 c 可以在 (0..8) 之间自由移动, 点 d 可以在 (7..9) 之间自由移动。

求一种算法,可以找到这些点的坐标,使得这些点彼此之间尽量远离

这里需要考虑 彼此之间尽量远离 的含义,从直观的角度考虑,应该就是这些点尽量均匀得分布在直线上,但如何从数学的角度描述,我还没想清楚,毕竟我是小学文化水平的人。

对我来说至少有 2 个难点:

  1. 没有一个合适的初始的点。
  2. 点的移动没有最小单位的限制,比如可以移动 1,也可以是 0.1,0.01,依此类推。

补充: 如果移动距离完全不做限制,我觉得不太靠谱。那么假设单位移动距离为 0.01,那么如果没有一个良好的算法,直线又比较长,计算量怕是比较巨大。。。

先提一个不均匀,尽量两端分散的算法:

  1. 将所有的 range 合并,找到几何上最远的两个点,这样就确定了两个点;
  2. 将剩余的点和 range 重复步骤 1。

然后考虑尽量均匀分布:

  1. 令两个目标点分别为 -max 和 +max;
  2. 在合并的 range 里找到最接近目标的两个点;
  3. 利用这两个点的距离和总点数计算出均匀分布时,靠近两侧的两个目标点
  4. 将剩余的点和 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 一点点迭代循环计算。

咦~你需要的是不是 GeoHash 算法呀~这个算法可以用来求二维空间物体远近。

oatw 回复

@oatw 我查了下,GeoHash 好像是做地理位置编码的,在这里好像用不到呀。

killernova 回复

Umm...我是凭感觉,感觉描述的场景可能是需要做类似 LBS 类的应用,具体你再权衡权衡 GeoHash 是不是适合~

理论上如果需要在二维空间上计算物体间远近,都可以试试 GeoHash,坐标不一定非得是经纬度,从 0 到 10,从 0 到 1 这样的自定义坐标也可以的,原理上都是做分区编码,然后找最近或最远编码。

需要 登录 后方可回复, 如果你还没有账号请 注册新账号