什么是不考虑回到出发点旅行商问题（TSP）问题的名字吗？ [英] What is the problem name for Traveling salesman problem(TSP) without considering going back to starting point?

问题描述

我想知道什么是TSP问题名称W / O考虑回到起点的方式，什么是算法来解决这个问题。

I would like to know what is the problem name for TSP w/o considering the way of going back to starting point and what is the algorithm to solve this.

我看着最短路径问题，但是这不是我所期待的，这个问题只能找到2分配点的最短路径。但我期待的就是这个问题，我们给出n个点和输入只有1个起点。然后，找到所有的旅游点恰好一次的最短路径。 （终点可以是任何点。）

I looked into Shortest path problem but that is not what I am looking for, the problem only find the shortest path from 2 assigned points. But what I am looking for is the problem which we give n points and inputting only 1 starting point. Then, find the shortest path traveling all points exactly once. (end point can be any point.)

我也看了成汉弥尔顿路径问题，但似乎并没有解决我的定义问题，而是寻找是否有哈密顿路径或不。

I also looked into Hamiltonian path problem but it seems not to solve my defined problem but rather find whether there is Hamiltonian path or not.

请给我建议，谢谢！

推荐答案

我发现在这个回答我的问题本书。它是同一个与在计算机和其他数字系统的设计重复发生时计算机布线问题。的目的是尽量减少焊丝的总长度。因此，这的确是一个最小长度哈密尔顿路径。

I've found the answer to my question in this book. It is the same with Computer wiring problem which occurs repeatedly in the design of computers and other digital systems. The purpose is to minimize the total wire length. So, it is indeed a minimum length Hamiltonian path.

什么书建议是建立一个虚拟的点，其距离每其他点为0。因此，这个问题成为一个（N + 1） - 城市的对称TSP。解决后，直接删除虚拟点，然后最小长度汉弥尔顿路径解决，我们可以得到TSP路径，而不返回回到起点。

What the book suggests is to create a dummy point whose distances to every other points is 0. Therefore, the problem becomes an (n+1)-city symmetric TSP. After solving, just delete dummy point and then the minimum length Hamiltonian path is solved and we can get the TSP path without returning back the start point.

这篇关于什么是不考虑回到出发点旅行商问题（TSP）问题的名字吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！