我想知道TSP w/o的问题名称是什么，考虑回到起点的方式，以及解决这个问题的算法是什么
我研究了最短路径问题，但这不是我要找的，问题只找到从2个指定点的最短路径。但我要找的问题是我们给出n个点，只输入1个起始点。然后，找出经过所有点一次的最短路径。(结束点可为任意点)
我还研究了哈密顿路径问题，但它似乎没有解决我定义的问题，而是发现是否存在哈密顿路径。
我在这本书里找到了我问题的答案。在计算机和其他数字系统的设计中反复出现的计算机布线问题也是如此。其目的是尽量减少总导线长度。因此，它确实是一个最小长度的哈密顿路径。
书中建议的是创建一个虚拟点，其与所有其他点的距离为0。因此，问题变成了一个(n+1)-城市对称TSP。求解后，只需删除虚拟点，即可求解最小长度哈密顿路径，无需返回起始点即可得到TSP路径。
如果我理解正确的话，您想要找到最短路径(从某个顶点s开始)并遍历图中的所有节点，而不访问同一节点两次。一个更简单的问题，是哈密顿路径问题。它问，就像你说的，是否存在这样一条路径。因为这个问题是np困难的，而且它比你的问题简单，所以解决你的问题至少是np困难的。嗯，这不是真的，因为你的问题不是决策问题。但它确实说的是，我们几乎可以肯定，对于你的问题，没有多项式算法。
你可以采用近似。这里有一个很酷的度量TSP近似值:http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP。
使用非对称TSP求解器
如果必须指定一个开始节点，如@Vivek Payasi所提到的，你可以构建一个典型的TSP问题，除了流入开始节点的弧线外，其他权重都是正常的。将它们的权重设置为0。
这将产生一个不对称旅行推销员问题(ATSP)。
现在，如果你有一个精确的ATSP求解器，它将寻找最短的周期。
完成后，从溶液中去除重量为0的弧线。这将看起来像你正在寻找的路径。
*所有这些都依赖于一个高效的ATSP求解器。
使用普通对称TSP求解器代替
如果您想避免使用ATSP求解器，请参考此答案:https://stackoverflow.com/a/59354134/7470152
底线是:固定开始节点&一个结束节点，添加一个虚拟节点，其弧线连接到权重为0的两个节点，然后将其视为正常的TSP问题。
对所有(n-1)个结束节点重复此操作，并选择最短的一个。
带虚点的对称TSP求解器
创建一个虚拟点，它与起点的距离为0，与其他点的距离为大数字(这个"number")应该大于"图形的直径"，这样它应该始终是最佳的虚拟点连接到您的起始点。然后使用对称TSP求解器得到解，并从答案中去除虚拟点。
证明:想象最优解有一个虚拟点不连接到你的起点。然后让我们构建另一个解决方案:我们采用相同的路径，但移除虚拟点，并将其置于起点和任何相邻点之间。那么路径的长度将被
改变-2 * "number" -
- "path between neighbour of starting point and starting point" -
+ "path between first neighbours of dummy point"
+ "number" =
= -"number" + "path between first neighbours of dummy point" - "path between neighbour of starting point and starting point"
,
"number" > "diameter of graph" >= "path between first neighbours of dummy point"
得到
-"number" + "path between first neighbours of dummy point" - "path between neighbour of starting point and starting point" < 0
意味着我们得到了更多的最优解。矛盾。这意味着虚拟点总是与起始点相连。