江苏龙网

  1. 首页 > 生活 > >

旅行最短路线问题

中国邮路问题有解具体看论文参考这个中国邮路问题
■网友
这属于运筹学里经典的旅行推销员问题--tsp问题。其属于np问题，没有有效算法。所以要解？枚举……类似还有中国邮递员问题
■网友
题主有问作业的嫌疑，不过可以给一些思路。这里对题主问题的描述还有一些疑问，如果你限定了每个城市只能游历一次，那么，这个问题就是前面那些回答所说的TSP(Travelling Salesman Problem)问题。 @astro yao 回答中说的很好，它是一个NP-hard问题，所以没有有效的确定性算法来解。但是考虑到数据量不算太大，答主如果执意要找精确解，可以把模型和数据带到IBM CPLEX Optimizer里面解一解，就我的了解，CPLEX可能使用的branch-and-bound 或者branch-and-cut来解的。当然，很多热心的网友都通过不同的语言(C、Java等)给出了可运行的程序，题主在Google、github里面搜一搜就有了，只不过要把数据换成你的。如果对每个城市的游历次数没有限定，那这个问题的相比与TSP就少了几个约束了，这个时候可能需要题主自己动手编程来解决这个问题了。可以使用一些的Heuristic算法来解这个问题，大致可以分为三类，一类是简单的构造性算法(Constructive heuristics)，如Nearest neighbor algorithm, Nearest insertion heuristic等；一类是本地搜索算法(Local search)，如，2-opt,or-opt等等；一类是元启发式算法(Meta heuristics)，包括人们常说的模拟退火( Simulated Annealing)、遗传算法( Genetic Algorithms )、禁忌搜索(Tabu search)等等。对于前两种，因为是老一辈艺术家提出的东西所以想找到可运行的程序有点困难，第三类是近些年提出的，想找到例子程序很容易，但是想把他们改造成解特定问题的程序也需要题主花一定的功夫。最后补充一点，2里面提到的方法肯定也是可以解1里面说的TSP问题滴。以上，如有问题欢迎交流讨论!
■网友
怎么感觉像贪吃蛇。是吧。好。下面说算法。算法都是人想出来的。那我们就慢慢想。地图上有两个点或者三个点答案就很明显啦。因为分别确定了线和面。当在添加一个点时。我们就有了两类选择。绕圈还是走8字。绕圈就不用思考了。值得一提的是走8字的时候实际你走过了地图上确定的五个点。直觉告诉我。还是绕圈路程短。这里有个坑。晚点填。
■网友
在地图上钉33个点，找一根绳子，按照上面的点，大致绕出一个圈，然后，不断调整绳子经过的点。看哪个最短!
■网友
如果只是最短，那么dijkstra, 如果是短加便宜，可以参考qap，用蚂蚁算法或bb


    推荐阅读


    上一篇：网络数据包在传输过程，包中的MAC是怎样变换的。

    下一篇：掌游宝大规模裁员，没钱过冬要死了吗?