4

我正在寻找有关创建算法的指导，以最大程度地减少一组旅行者到达一组固定目的地的总旅行时间。旅行者并非都从同一个地方开始，但每个目的地都必须由旅行者访问，然后才能认为场景完成（类似于 TSP）。

我正在考虑生成一个矩阵，其中位于 (x, y) 的值将是从起始位置 x 到目的地 y 的行进距离，然后执行某种矩阵运算/算法来选择值，例如每一行/列只有一个从中选择的值，并且这些值的总和被最小化。有没有人有这种事情的算法背景？

基于评论的澄清：

  • 每个目的地必须由一名旅行者访问。并非所有旅行者都必须访问所有目的地。
  • 如果目的地多于旅行者，旅行者应该只瞄准一个任意目的地（仍然最小化旅行时间），然后重复这个问题，但目的地少两个。
  • 目的地和旅行者的最大数量应该是大约 30 个目的地和 10 名旅行者，所以不是很大的数字。尽管如此，我还是想避免纯粹的蛮力。
4

3 回答 3

3

看看Floyd-Warshall 算法和Merge Sort 算法。

鉴于要访问的位置（顶点）数量为 V，旅行者数量为 T，如果您应用 Floyd-Warshall 算法，它应该为您提供图中顶点对之间的最短路径，O(V^3 ) 复杂性。

然后，您可以按升序对最短路径的长度进行排序，这将是一个复杂度为 O(V lg V) 的操作。

由于您按顺序应用这些算法，因此总体复杂度仍为 O(V^3)。

您将必须执行第二阶段 K 次，其中 K 是上限（V / T），因为在第一次迭代中，您将访问 T 个顶点，但 V 大于 T，因此您有更多顶点要访问。在您的下一次迭代中，您将从计算中删除访问过的顶点并对剩余距离（您在上一步中已经找到）进行排序，然后继续从 T 个旅行者的新位置访问它们。

您可以通过为每个顶点选择最小距离来获得更好的结果，因此您选择的下一个顶点是提供的最接近的顶点。

因此，您的整体复杂性将开始看起来像 O(V^3) + K x O(V lg V)，我认为它趋于接近 O(V^3)。

这些只是帮助您入门的一些想法。

于 2013-05-01T00:06:03.720 回答
2

如果我了解您的问题，我怀疑旅行者的数量是否与快速找到解决方案有关。因此，我们通过一些启发式方法解决了基本的旅行推销员问题，然后在该循​​环中移​​动旅行者。

记录了各种建设性方法和各种迭代改进方法。下面是一些示例（从学术到漂亮的动画示例）：

于 2013-05-01T00:02:56.453 回答
1

由于旅行商问题在阶乘复杂性中运行，它可以迅速增长到超出在 CPY 上运行的合理范围。幸运的是，较新的计算机都配备了功能完善的图形卡，可以比 CPU 快数百或数千倍地运行此类问题。

我在此处发布了对 TSP 相当简单的解决方案的分析和比较，其中包括在 NVIDIA 显卡上运行的 C# 代码。还需要下载CUDAfy CUDAfy 库才能直接运行代码。

使用我的 Quad i7、16GB 笔记本电脑和 NVIDIA GEFORCE GT 显卡，我报告了 11 个城市的性能提高了近 70 倍（14.7 秒到 0.2 秒），将问题从单个 CPU 核心移植到 GPU。

The code in the CUDA Tuning project is under the MIT Licence, so free to use with attribution.

于 2013-05-01T02:21:08.570 回答