求大神帮忙写个算法

公子潇潇发布于 2018-01-12 17:57， 2093 次点击

现有一个配送中心点A，64个待配送点
要求把64个代配送点随机分成8组，然后每组8个点求一个几何重心点。
这8个几何重心点到配送中心点A的距离之和X
求这个X的最小值    和   X最小时64个点分为8组的组合方式
已知65个点的二维坐标我都有
这个算法困难吗？求大神帮忙

4 回复

wds12018-01-12 19:48

如果要计算出最小X，我觉得需要计算全部组合，不能随机分组。

1、利用遍历算法，给出64个点分8组的全部组合
2、求每个组合的8个点的几何重心。(x,y) x=(x1+x2+...+x8)/8;y=(y1+y2+...+y8)/8
3、计算每个组合的几何重心到A点距离和x【记录x，保留最小的X及组合】

以上供参考。

[此贴子已经被作者于2018-1-12 19:50编辑过]

xiangyue05102018-01-14 11:15

首先，论坛严禁求作业。
第二，你这个思路肯定是不对的，真做出来估计要被配送员骂死的。直线距离很近不代表实际距离近，弯弯绕绕的情况很正常。
建议用小区划分，然后利用GIS软件规划路线，然后优选。

ZHRXJR2018-01-14 14:04

同意3楼的观点！点到点的坐标距离是直线距离，而实际路程与直线距离的差距太大了，而且根据行走方法不同（汽车与单人电动车），实际路程也会有很大差距。
因此你的64个代配送点的实际路程才是关键（假定这64个代配送点时固定的，并且运输工具是什么，汽车还是单人电动车），这样可能才能考虑怎么实现你的要求。

肇励影2018-01-15 14:27

ZHRXJR说得有道理，如果是使用飞机什么的配送确实是可以使用直线。如果有障碍物，需要另行计算了。