ForceDirected搜索神秘门店

场景

有一个神秘门店，有配送服务，给很多人(N<20)配送过商品，但是配送单上只有配送目标地点坐标(x,y)和配送距离(D，存在误差，但保证只多不少)，现在我们收集到了这些配送单，要求反找出这个门店的位置。（大致能估算出来就行，要求这个位置满足）

解决思路

这个问题最开始想到的是质心定位，但第一次定位肯定存在定位不准，所以就需要迭代优化，考虑到被配送点反推距离是个圆，于是迭代方案就选择了力引导迭代，把迭代时的步进因子设置一下。

和大佬交流了一下，大佬表示如果数据真的比较干净的话（保证存在交集）可以使用拉格朗日乘子算法，找到零点最近（min(x^2+y^2) or min(x+y)）的那个，每个采样点d(x0-x,y0-y)-R < 0 作为约束条件，但是假如约束条件太多的话容易导致优化器迭代很慢，不过有现有的优化器可以直接调包，是一种快捷的思路。

另一个大佬有对于初始点定位有新的思路：先把经纬坐标映射到平面坐标系上，然后将所有的圆（或者椭圆，这个映射方式无所谓，后面会说）扩展为一个经纬平行方向的矩形，对于圆来说，找交集很困难，但是对于矩形来说，找交集很简单，所以将这些矩形从小到大排列，然后依次叠加交集，过滤掉后来的没有交集的矩形，最后留下的矩形交集的几何中心就是初始点。

关于为什么映射成圆或者椭圆无所谓，因为这种算法省略了计算任意两点距离的麻烦，只需要计算经向纬向的最远距离，独立两个纬度的线性可逆变换最后都能很简单反映射回去。

生成模拟数据

模拟数据分为两种，一种是保证有交集的干净数据，一种是不保证有交集的脏数据。干净数据生成方式可以逆向思维，先确定一个交集，在去生成覆盖这个交集的圆，脏数据生成就是让干净数据随机偏移就可以了。

设计细节

拉格朗日乘子有现有方案，要注意一下不同迭代器的参数配置。

对于矩形交集初始点，这个方案很清晰明了，算起来也很快，所以不多说了，注意一下矩形是需要排个序的，最小的权重最大，交集一定是最小的矩形的子集。

说到质心+力导向：

• 关于质量权重的选择，显然圆越大越不准，所以质量权重应该越低，把质量定义为半径的平方倒数，生成初始点期望更靠近小的圆。
• 关于力的定义，采用圆内 F = 0，圆外 F = (d-r)^2 ，首先这样可以尽可能保证圆外的点都能尽快回到圆内，另一个就是希望离圆越远就靠近越快。
• 经纬度算距离和平面距离不太一样，建议距离计算单独写一个函数便于更改。

实验结果

PS：每批做了十万次实验

实验日志

Start==========Finished
Circle Num=4
Step Radio:0.003
迭代上限：5000
Lab Num=100000
Time:3129ms
Fails Ratio=0.0
Fails Avg Distance=NaNm
Max Delivery Distance = 20.0km
平均迭代：85.95243

Start==========Finished
Circle Num=7
Step Radio:0.003
迭代上限：5000
Lab Num=100000
Time:3798ms
Fails Ratio=0.0
Fails Avg Distance=NaNm
Max Delivery Distance = 20.0km
平均迭代：83.55214

Start==========Finished
Circle Num=15
Step Radio:0.003
迭代上限：5000
Lab Num=100000
Time:2860ms
Fails Ratio=0.0
Fails Avg Distance=NaNm
Max Delivery Distance = 20.0km
平均迭代：29.99788

Start==========Finished
Circle Num=25
Step Radio:0.003
迭代上限：5000
Lab Num=100000
Time:2714ms
Fails Ratio=0.0
Fails Avg Distance=NaNm
Max Delivery Distance = 20.0km
平均迭代：15.66433

Start==========Finished
Circle Num=25
Step Radio:0.005
迭代上限：5000
Lab Num=100000
Time:2013ms
Fails Ratio=0.0
Fails Avg Distance=NaNm
Max Delivery Distance = 20.0km
平均迭代：9.49053