问求解一个非常简单的多旅行商问题的最优有效方法
EN

Stack Overflow用户

提问于 2016-11-17 10:15:21

回答 1查看 52关注 0票数 0

我有两个双精度的nx2矩阵，A&B在每一行包含x和y坐标。我必须将A中的一个点与B中的一个点配对，使得它在欧几里德距离方面做得最好，这意味着假设A包含人的初始位置，B包含宝藏位置。每个智能体只想到达最近的宝藏，因为所有的宝藏都是平等的。

这与多TSP略有不同。我正在寻找最优的算法来实现，它不是这个问题的过度杀伤力。天真的方法是从第一个代理开始，开始将代理与珍宝配对，直到所有代理都完成。一旦智能体与宝藏配对，宝藏就不再用于进一步分配。这是我目前在Matlab中实现的，但我对更好的解决方案持开放态度。

发布于 2016-11-17 10:20:40

我假设穷举O(n * n)是不可能的？使用memoization，一旦超过当前“最佳”的总距离，您就可以通过中止来改进详尽的解决方案。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/40645630

复制

相似问题

问求解一个非常简单的多旅行商问题的最优有效方法EN