问题标签 [traveling-salesman]

给定一个在边上具有不对称成本的图结构，如果您只能访问每个节点一次，有没有办法以最低成本遍历一组节点？问题被表述为这样的路径必须存在。

我查看了类似的问题，但找不到与我的问题相关的任何内容。我正在努力寻找一个算法或一组“循环”来找到从CityAto的路径CityB，使用

事实。到目前为止，我设法做的事情如下，但它总是回溯write(X),到最后一次迭代，然后完成，这是我希望它做的，但只是在一定程度上。

例如，我不希望它打印出任何死胡同的城市名称，或者使用最终迭代。我希望它基本上形成一条从CityAto的路径，在路径上CityB写下它去往的城市的名称。

我希望有人能帮助我！

I am implementing the Christofides algorithm for getting a 3/2-approximation to TSP in graphs that obey the triangle inequality. I already have code for computing a minimum spanning tree using Kruskal's algorithm and an adjacency matrix.

Now, I want to implement Christofides by doubling the edges and finding an Euler tour and then shortcutting duplicate nodes. How do I perform this step? I'd like the algorithm and (optionally) C code.

Thanks!

我刚刚下载了 ai4r 库http://ai4r.rubyforge.org/我正在使用遗传算法从多个地方获得一条好的路线，就像这样：

http://ai4r.rubyforge.org/geneticAlgorithms.html

但我需要能够设置一个起始城市。

关于如何在“固定”起始城市上使用它的任何线索？

我有一个问题需要解决，但我想不出任何简单且更重要的方法：快速解决方案。这有点像多次旅行推销员问题的一部分。

首先，我有一个包含X行和N列的矩阵，N它是我算法的静态变量，并且X可以变化。让我们假设它看起来像（这里N = 5）：

每一行都被视为一条“路线”，包含 1 到 1 之间的所有唯一数字。N每条路线（= 行）将被分成部分路线。这意味着，我有一个包含X行和M( M < N) 列的断点矩阵。例如：

每行的索引breakpoints给出 AFTER 对应行的元素，matrix路线将被分成部分路线。为了清楚起见，让我们以第一行为例：breakpoints(1, :) = 2 3 4这意味着该路线matrix(1, :) = 1 2 4 3 5将被拆分为部分路线[1 2], [4], [3] and [5]。第二行有断点breakpoints(2, :) = 1 2 4，将第二条路线matrix(2, :) = 4 3 1 2 5分成部分路线[4], [3], [1 2] and [5]。

现在我的目标是从 中删除所有行matrix，而部分路由是冗余重复，只是顺序不同。在此示例中，第 2 行是第 1 行的副本。第 3 行即使与第 1 行具有相同的路由也不重复，因为存在不同的断点导致部分路由[1], [2 4], [3] and [5]。

我怎么能干净又快速地做到这一点？矩阵可以包含许多元素，例如X = 5e4行和N = 10, M = 6。

我读了这篇文章，它建议（第 1025 页最后一段）有一个多项式时间算法可以使用二进制搜索找到 k-tsp 问题的最优值。使用二分搜索表明存在一种算法来检查是否存在解决方案，cost<X并且该算法用于二分搜索。我为此“用谷歌搜索”，我能找到的唯一算法是一个非确定性的算法（这很简单），但显然我正在寻找一个确定性的算法。

出于学习目的，我对此感兴趣，

任何帮助/链接将不胜感激。

编辑

我指的是找到最佳解决方案的价值，而不是找到解决方案本身。

假设我们想为给定的具有 V 个顶点和 E 边的完整图 G 计算 TSP（我的意思是完整的：每个顶点都与每个其他顶点相连）。

我会尝试再次提出这个问题。希望这次我能做对。我的目标很简单：
对于这个完整的图 G，如何过滤掉一些可能不在图中的边？

比如说，我们有一个代表旅行商问题的解决方案的循环列表。此列表最初为空。

如果允许用户输入一个城市并且它的坐标是一一对应的，那么可以使用什么启发式方法将这些坐标插入到已经存在的游览中？

一个示例使用最近邻启发式：它将新坐标插入到旅行中已经存在的最近坐标之后。

还有哪些其他选项（如果可能，请使用伪代码）。

我正在自学如何编写涉及 TSP（Djikstra，Kruskal）的算法，并且正在寻找一些启动建议。我正在使用 C# 和 SQL。理想情况下，我希望能够在 SQL 中严格执行此操作，但是我不确定这是否可能（我假设在 50 个顶点之后运行时会很糟糕）。

所以我想问题是，我可以只做 SQL 吗？如果可以，最好的方法是什么？如果没有，我必须让 C# 参与其中，最好的方法是什么？

我正在实现一种算法，该算法在有向图中找到最佳哈密顿路径。我已经实现了一个看起来运行良好的算法，但是我不完全确定在某些情况下是否存在细微的错误或其他问题。因此，我需要一些已知解决方案的不同网络，以检查我的实现是否也在按应有的方式解决它们。

由于 Wikipedia 暗示哈密顿路径只是无向图的适当术语，因此假设“哈密顿路径”是指在给定网络上访问每个节点一次且恰好一次的路径，无论是有向的还是其他的。

为简单起见，我们可以假设每个连接（或“边”）都有一个正整数值（或“长度”）。我们还可以假设没有节点与自身相连，并且在任何两个节点之间的每个方向上都不能有超过一条边。

我碰巧对总长度最长的路径感兴趣，因此“最佳”意味着最长，尽管如果我想要最短的总长度（如在传统 TSP 中），它可能没什么区别。我也碰巧使用了贪心算法。

我可以在哪里或如何获得已解决 TSP 的定向网络？如果实际解决方案和贪婪（或其他启发式）解决方案可用，那就更好了。网络应该足够大以进行信息测试，但足够小以供我手动检查解决方案（如果解决方案最初未知）。它们应该在拓扑上足够多样化，以涵盖“简单”和“有问题”的网络。

对于其他寻找相同的人；我最好的是以下网络：

这是一个邻接列表，行是边缘起点，列是终点。数字是每条边的长度，0 表示“无边”。例如，4 表示从D到A 的边的长度为 4，从A到D没有连接（长度为 0）。

该网络中的最大路径长度为 E->D->A->C->B。它的总长度是2+3+3+3=11。我相信贪心算法能够在这种情况下找到最佳解决方案，而且很明显它是最好的解决方案。