旅行时间最小化算法
我正在寻找指导，在创建一个算法，以减少总旅行时间为一组旅行者到达一组固定的目的地。旅行者并不都是从同一个地方开始的，但每个目的地都必须由旅行者访问才能被认为是完全的(类似于TSP)。
我想到的是产生一个矩阵，其中位于(x，y)处的值是从起始位置x到目的地y的旅行距离，然后执行某种矩阵操作/算法来选择值，这样每一行/列只有一个从中选择的值，并且这些值的和被最小化了。有谁对这类事情有算法背景吗？
根据评论作出的澄清：
- 每个目的地必须有一名旅客访问。所有的旅行者都不必去所有的目的地。
- 如果目的地比旅行者多，旅行者应该只针对一个任意目的地(仍然尽量减少旅行时间)，然后重复这个问题，但目的地要少两个。
- 最多的目的地和旅行者应该在30个目的地和10个旅行者，所以不是一个庞大的数字。如果可能的话，我想避免纯粹的蛮力。
回答 3
Stack Overflow用户
发布于 2013-05-01 00:06:03
看看Floyd-Warshall算法和合并排序算法。
如果要访问的地点(顶点)是V，而旅行者的数目是T，那么如果应用Floyd算法，它应该给出图中顶点对之间的最短路径，具有O(V^3)的复杂性。
然后，您可以按升序排序最短路径的长度，这将是一个具有O( V )复杂性的操作。
由于您是按顺序应用这些算法，所以您仍然处于O(V^3)的总体复杂性。
您必须执行第二阶段K次，其中K是上限(V/ T)，因为在第一次迭代中，您会访问T顶点，但是V大于T，所以您有更多的顶点要访问。在下一次迭代中，您将从计算中移除已访问的顶点，并对剩余的距离(在上一步中已经找到)进行排序，然后继续从T旅行者的新位置访问它们。
您可能会通过为每个顶点选择最小的距离来获得更好的结果，因此您选择的下一个顶点是提供的最接近的顶点。
因此，您的总体复杂度将开始看起来像O(V^3) +K(V lg V)，我认为它趋向于O(V^3)。
这些只是一些让你开始的想法。
Stack Overflow用户
发布于 2013-05-01 00:02:56
如果我理解你的问题，我怀疑游客的数量是否与快速找到解决方案相关。所以我们用一些启发式的方法来解决基本的旅行推销员问题，然后让旅行者绕着这个周期转。
有各种建设性的方法和不同的迭代改进方法。下面是几个例子(从学术到漂亮的动画例子)：
- 算法
- http://bjornson.inhb.de/?p=26
- http://www.cs.ubc.ca/labs/beta/Courses/CPSC532D-05/Slides/tsp-camilo.pdf
Stack Overflow用户
发布于 2013-05-01 02:21:08
由于旅行推销员问题在阶乘复杂性中运行，它可以快速增长，超出在CPY上运行是明智的。幸运的是，较新的计算机都配备了一个功能完善的显卡，可以运行类似这样的问题，比CPU快几百倍或上千倍。
我已经发布了对TSP 这里相当简单的解决方案的分析和比较，其中包括运行在NVIDIA显卡上的C#代码。还需要下载CUDAfy CUDAfy库来直接运行代码。
使用我的Quad i7、16 GT笔记本电脑和NVIDIA GEFORCE GT显卡，我报告了11个城市的性能提高了近70倍(14.7秒)。至0.2秒)将问题从单个CPU核心移植到GPU。
该代码在CUDA调谐项目是在麻省理工学院的许可下，所以可以自由使用与归属。
https://stackoverflow.com/questions/16310622
复制相似问题
腾讯云开发者
