algorithm - 如何最小化 n 人在 m 个位置上的距离

这是一个现实生活中的问题，而不是家庭作业。我将在问题中使用特定数字。

我的客户有一个非常大的仓库，有 16,000 个位置。他们想对随机选择的 200 个位置的数量进行物理计数，以验证计算机系统的数量是否准确。

我知道如何随机选择 200 个位置（Knuth TAOCP）。

位置之间的距离很容易计算。仓库布置在过道中（像一个大盒子商店）。基本上，我学到的是出租车指标（delta X + delta Y）。

假设他们将分配 4 个人来完成这项任务。如何为每个人生成一个位置列表，以最大限度地减少人们旅行的总距离？

对于一般算法，要计算的位置数量和分配给任务的人数将是输入参数。

帮你解答，我有几十年的经验，但我是自学成才的。我猜这对于动态编程来说是一个很好的问题（最近观看了 MIT 讲座系列），但从未实现过。坚持形成递归。

或者也许是其他一些算法。这不是大量的数据点，所以也许是蛮力方法？

如果其他标签合适，请提出建议。如果您愿意发布代码片段，任何语言都可以。

标签： algorithm

考虑到“总成本”标准和地点的随机分布，我预计最佳路径是让一名工人覆盖 200 个地点中的大部分或全部；其他 3 个将仅计算在起点/终点附近弹出的孤立的库存口袋，S.

对于一般攻击，我建议您将您的四名工人从S. 从那里，采取贪婪的方法：找到离四个工人中任何一个最近的位置；把那个工人送到所说的地方。继续，直到访问完所有位置。请注意，S每个工人都有第一个点和最后一个点。

现在，处理每个工人的路线以最小化该工人的总行驶距离。

最后，“扰动”每条路径。选择一个随机位置并将其从路径中移除。将其重新分配给该位置增量成本最小的路径。继续这个重新分配，直到你完成，比如说 1000 次迭代而不改变分配。