问题标签 [traveling-salesman]

我正在研究旅行商问题的分支定界算法，但遇到了一点麻烦。我正在使用一个非常标准的队列，其中的节点代表顶点（路径）的子集。我很确定我已经解决了整个问题，但目前我有公共类 Queue，在它下面有私有类 Node，它的所有属性：当前路径、下限等。

但是，在我的主程序中，我初始化了节点队列并创建了两个起始节点，但出现错误“节点无法解析为类型”。我认为这是因为它在 Queue 类中并且主程序无法访问，但是当我将它移出时，我在连接到节点的项目上的其他任何地方都会出错。

我真的希望这是有道理的，我不确定如何解释它，但其他一切似乎都很好。这是我的代码片段以进行澄清：

那是我声明 Node 类的地方，也是我在主程序中实际使用它的地方：

这是一个学术问题而不是实际问题。在旅行推销员问题中，或任何其他涉及找到最小优化的问题中……如果有人使用 map/reduce 方法，似乎有一些方法可以将当前最小结果广播给所有人计算节点以某种方式允许它们放弃超过该值的计算。

换句话说，如果我们将问题映射出来，我们希望每个节点在完成之前知道何时放弃给定的部分结果，但何时已经超过了其他解决方案。

立即想到的一种方法是，reducer 是否有办法向映射器提供反馈。考虑一下我们是否有 100 个节点，并且映射器向它们提供数百万条路径。如果 reducer 将最好的结果提供给 mapper，则该值可以作为参数包含在每个新路径（问题子集）中。在这种方法中，粒度相当粗略……这 100 个节点将每个节点都在他们的问题分区上不断打磨以完成，并且只有在映射器的下一个请求时才获得新的最小值。（对于少量节点和大量问题分区/子集在此粒度上工作将是无关紧要的；而且它

想到的另一种方法是让节点主动订阅某种频道，或多播甚至广播，它们可以从它们的计算循环中收集新的最小值。在这种情况下，他们可以在收到更好的解决方案（由他们的同行之一）通知时立即放弃错误的计算。

所以，我的问题是：

• 与现有 map/reduce 讨论相关的任何艺术术语是否涵盖此概念
• 当前的 map/reduce 框架是否提供了支持这种动态反馈的功能？
• 这个想法有什么缺陷……为什么它很愚蠢？

我有一个问题已被有效地简化为多个推销员的旅行推销员问题。我有一个从初始位置访问的城市列表，并且必须访问所有销售人员有限的城市。

我正在尝试提出一种启发式方法，并想知道是否有人可以伸出援手。例如，如果我有 20 个城市和 2 个推销员，我想到的方法是两步法。首先，将 20 个城市随机划分为 10 个城市，每个城市有 2 个推销员，我会发现每个城市的旅行好像对于几个迭代都是独立的。之后，我想交换或分配一个城市给另一个推销员并找到旅行。实际上，这将是一个 TSP，然后是最小制造时间问题。这样做的问题是它太慢了，而且交换或分配一个城市的好邻居生成是困难的。

任何人都可以就我如何改进上述内容提出建议吗？谢谢。

我有一个问题已被有效地简化为多个推销员的旅行推销员问题。我有一个从初始位置访问的城市列表，并且必须访问所有销售人员数量有限的城市。

我正在尝试提出一种启发式方法，并想知道是否有人可以伸出援手。例如，如果我有 20 个城市，有 2 个销售员，我想到的方法是两步法。首先，将 20 个城市随机分成 10 个城市，每个城市有 2 个推销员，我会发现每个城市的巡演好像是独立的几次迭代。之后，我想交换或分配一个城市给另一个推销员并找到旅行。实际上，这将是一个 TSP，然后是最小制造时间问题。这样做的问题是它太慢了，而且交换或分配一个城市的好邻居生成是困难的。

任何人都可以就我如何改进上述内容提出建议吗？

编辑：

每个城市的地理位置都是已知的，销售人员在同一个地方开始和结束。目标是最小化最大旅行时间，使这种最小制造时间问题。因此，例如，如果 salesman1 需要 10 小时，而 salesman2 需要 20 小时，则最长行程时间为 20 小时。

我正在寻找此问题的名称或算法或源代码的任何线索：

示例：您想找到访问美国 100 个最大城市（经典 TSP）的最佳路线，但在访问任何给定城市之前，您必须先访问其所在州的首府。

示例：您正在收集几位教授的学生的许可单。你需要拜访每一位学生和每一位教授，但你不能拜访一位教授，除非你见过他所有的学生。

一些谷歌搜索出现了顺序排序问题或“SOP”，但没有太多文献我相信这是一个被广泛接受的名称。

我认为这些偏序不能简单地通过选择要在图中使用的边（例如，您最初不能从纽约到芝加哥，但是一旦您访问斯普林菲尔德就可以）或权重来表示在经典 TSP 中，但我可能错了。

我想知道 TSP 的问题名称是什么，不考虑返回起点的方式以及解决此问题的算法是什么。

我研究了最短路径问题，但这不是我要找的，这个问题只能从 2 个指定点找到最短路径。但我正在寻找的是我们给出 n 分并且只输入 1 个起点的问题。然后，找到通过所有点的最短路径恰好一次。（终点可以是任何点。）

我还研究了哈密顿路径问题，但它似乎没有解决我定义的问题，而是找出是否存在哈密顿路径。

我正在为 java 中的 TSP 编写一个简单的本地搜索算法。这是方法：

问题是 if 语句始终为真，因此在运行该方法时，输出如下所示：

....3, 34, 43, 32, }LENGTH: 30464.0 当前最佳：30464.0

....14、37、24、49、}长度：31499.0 当前最佳：31499.0

....8, 4, 20, 42, }LENGTH: 30710.0 当前最佳：30710.0

....23, 33, 12, 6, }LENGTH: 29321.0 当前最佳：29321.0

....11、32、28、15、}长度：30545.0 当前最佳：30545.0 .................... ......................

如您所见，“最佳”总是被“候选”取代，而它不应该。

我的代码对我来说似乎很好，但显然有问题。

笔记：

1) 我检查了 stochastic_2_opt() 方法，没关系。

2) getLength() 方法返回双精度值，所以我认为这可能是一个陷阱，我使用了 Double.compare，但即使那样也没有用。

3) 我还注意到，当将 if 条件写为 (candidate.getLength() < best.getLength()) 时，它也总是正确的。

你能帮我找出错误在哪里吗？

所采取的路径不必在预定顶点处结束。基本上是旅行商问题，除了一个顶点可以被访问不止一次。

编辑：最多有 10,000 个顶点和边

我知道这是一个相当常见的问题（一般是 tsp），但我已经被它难倒了一段时间。我正在寻找给定一组 x,y 坐标的最小距离哈密顿路径。起点和终点是完全任意的，但它不能循环，因此标准 tsp 已退出（尽管据说在与所有其他节点的距离为 0 处添加一个虚拟点，然后稍后将其删除，但我不知道该怎么做）。

有很多数学论文的链接和类似的讨论算法来解决类似问题，但我更愿意使用代码而不是复杂的方程，我真的不想重新发明轮子。

当然，主要语言 java、c#、c++、ruby、javascript、php 等有一个相当简单的实现可以解决我的问题的大约 20 个节点版本。

编辑：我也在寻找尽可能准确的，显然它不能完全准确到 20！有很多排列，但等于或优于人类在几分钟内可以做的事情将是完美的。

Edit2：另外澄清一下，我正在使用未加权图上的标准二维坐标。距离 A->B == B->A

Edit3： 为了消除混淆，这里有一个可视化的例子，只有几点来说明 tsp 可能不是最理想的（这种情况很容易解决，但如果有更多节点，它可能会更极端）。

TSP 减最长段（红线）

期望的输出

什么是旅行推销员问题的实际解决方案，使用谷歌地图/地理定位/路线查找？

我不需要最好的解决方案，在 5% 以内就可以了。

例如，我在英国有 20 个地点可以访问，顺序不限。这可能需要扩展到数百个位置。

鉴于我可以查找距离（但不想查找数百个距离），我可以使用哪种算法？