问题标签 [traveling-salesman]

我正在解决这个问题：

证明如果 TSP 可以在多项式时间内求解，那么 TSP-OPT 也可以。

现在，首先想到的是，如果我知道最佳解决方案的成本，我可以将 b 设置为那个，瞧。而且，你不知道吗，在我书中的其他地方，它包含了这个问题的提示：

我们如何找到最优成本？简单：通过二分查找。

我想我可能在这里误解了一些非常糟糕的事情。二进制搜索旨在查找给定项目在排序列表中的位置。这究竟如何帮助我找到最佳成本？我真的很困惑。不幸的是，作者没有进一步详细说明。

我可能想到的解决这个问题的唯一另一件事是证明它们都归结为另一个 NP 完全问题，我最终可能会这样做，但仍然......这让我很烦恼。

旅行商问题(TSP) 和中国邮差问题(CPP)有什么区别？

对我来说，两者都想去一个目的地，然后再回来。

我的任务是编写 A* 算法（提供启发式算法）的实现，以解决旅行商问题。我了解算法，它很简单，但我看不到实现它的代码。我的意思是，我明白了。节点的优先级队列，按距离 + 启发式（节点）排序，将最近的节点添加到路径上。问题是，如果不能从前一个最近的节点到达最近的节点会发生什么？一个人实际上如何将“图形”作为函数参数？我只是看不到算法实际上是如何运作的，就像代码一样。

在发布问题之前，我阅读了维基百科页面。反复。它并没有真正回答这个问题——搜索图表是一种方式，与解决 TSP 方式不同。例如，您可以构建一个图，其中任何给定时间的最短节点总是导致回溯，因为两条相同长度的路径不相等，而如果您只是尝试从 A 到 B，那么两条路径相同的长度是相等的。

您可以得出一个图表，通过始终最接近的方式永远无法到达某些节点。

我真的不明白 A* 如何适用于 TSP。我的意思是，找到从 A 到 B 的路线，当然，我明白了。但是TSP？我没有看到联系。

我们正在开发一个应用程序，其中我们将在谷歌地图中显示一些可供出售的房屋。用户可以从地图中选择任何房屋，并可以找到他/她选择的所有房屋之间的最短行车路线。

谁能告诉我我们如何找到最短的路线并在地图上显示？是否有任何基于 PHP 的 TSP 库可以帮助我们实现我们正在尝试的目标？

我目前正在做一个需要快速解决 TSP 的项目（大约 50-100 个节点在 2 秒内）。那里有很多近似算法，但我没有时间也不会分析它们并自己编写代码。

有没有可以解决 TSP 问题的免费库（近似值也可以）？像这样的东西sortedNodes = solveTspPrettyPlease(nodes, 2sec)会很棒。

提前致谢。

我有一个关于图表的问题。考虑一个具有节点和边的图，每条边都有成本。问题是访问所有节点，以使遍历的边的成本总和最小（我猜是旅行推销员问题）。

您会推荐哪种方法？通过递归使用蛮力方法或通过产生线程使用蛮力同时行进不同的路径并计算它们的成本。

或者你有更好的方法来解决这个问题吗？

我想知道是否有用于 TSP 的分支定界算法的有用 Java 实现，或者通常包含用于 TSP 的 BnB 的 OR 框架。

谢谢你的帮助！

马可

我正在尝试从旅行推销员问题算法中用 C++ 开发一个程序。我需要一个距离矩阵和一个成本矩阵。使用所有公式后，我得到一个新的结果矩阵。但我不明白那个矩阵显示了什么。假设结果矩阵是：

现在我想知道这个矩阵显示了什么？假设我有 3 个城市要穿越。

请告诉我流程。这个算法的示例程序会更有利..谢谢。

我的程序是：

输出：

我创建了一个由旅行商问题衍生而来的谜题，我称之为 Trace Perfect。

它本质上是一个带加权边的无向图。目标是使用最小权重在任何方向上至少遍历每条边一次（与目标是使用最小权重访问每个顶点的经典 TSP 不同）。

作为最后的扭曲，一条边被分配了两个权重，一个用于每个遍历方向。

我每天都会创建一个新的拼图实例并通过 JSON 接口发布它。

现在我知道 TSP 是 NP 难的。但我的拼图通常只有少量的边和顶点。毕竟，它们需要是人类可以解决的。因此，具有基本优化的蛮力可能就足够了。

我想开发一些（Javascript？）代码，从服务器检索谜题，并在合理的时间内用算法解决。此外，它甚至可以将解决方案发布到服务器以在排行榜中注册。

我已经在服务器上使用我的后端 Java 模型在 Java 中为它编写了一个基本的蛮力求解器，但是代码太胖并且如预期的那样很快耗尽了堆空间。

Javascript求解器是否可行且可行？

JSON API 很简单。您可以在以下网址找到它：http ://service.traceperfect.com/api/stov?pdate= 20110218 其中 pdate 是 yyyyMMdd 格式的拼图日期。

基本上一个谜题有很多行。每条线有两个顶点（A 和 B）。每条线有两个权重（当遍历 A -> B 时为 timeA，当遍历 B -> A 时为 timeB）。这应该是构建图形数据结构所需的全部内容。JSON 对象中的所有其他属性都用于视觉目的。

如果您想熟悉这个谜题，可以通过http://www.TracePerfect.com/上的 Flash 客户端播放它

如果有人对自己实现求解器感兴趣，那么我将发布有关将解决方案提交到服务器的 API 的详细信息，这也很简单。

感谢您阅读这篇冗长的帖子。我期待听到您对此的看法。

我有一个简单的绘图问题，我遍历一个图表来寻找一个项目。图中的每个节点都有一个项目存在的概率 n/100，其中所有概率的总和等于 1。如何找到在整个图中搜索项目的最小预期时间？

该项目保证仅存在于一个节点中。

乍一看，这似乎是一个旅行推销员问题，这很简单。只需获取路径的排列并计算每个路径并返回最小值。

但是当我需要找到最小的预期时间时，它变得很棘手。是否有任何数学公式可以插入到最小路径上以获得结果？

还是需要做一些更复杂的事情？