如何获得的近似解得到的最短路径经过的所有节点会

是否有人知道的算法或东西做如何获得的近似解得到的最短路径经过的所有节点会

所以我有一个弧形的连接节点，我必须找到一个解决方案，以找到一个近似最短路径覆盖所有节点。（我只能访问他们一次）

它必须是一个近似的路径，因为它会采取太多的时间来获得的最短路径

谢谢您的回答:)

（我必须这样做在Java）

来源

2012-11-24 Lol Pallau

这被称为[旅行推销员问题]（http://en.wikipedia.org/wiki/Travelling_salesman_problem） –

@JanDvorak - 它可能实际上是[哈密尔顿路径问题]（https：//en.wikipedia .ORG /维基/ Hamiltonian_path_problem）;他从不说他需要回到原始节点。 –

这些问题统称为_Graph Theory_，并且存在大量问题，其中包括众所周知的解决方案。这已经介绍给你了吗？ –

是的，有。该方法被称为“遗传优化”，其步骤如下 1.找到解决方案，即访问每个节点一次的路径。 2.选择K的靠近节点随机：N1，N2..Nk：X-> N1 - > .. NK->ý 3.检查以查看是否有从X到Y使用节点N1..Nk较短的路径 4.更换路径X - 通过较短的溶液*>ý 5.转到2

ķ必须小（5或更小），这样就可以很容易地找到较短的组合

的好处约您可以随时停止并使用现有的解决方案。一个改进是随机选择一个更大的k。

来源

2012-11-24 12:23:58 alzaimar

这与遗传学有什么关系？你所描述的是K-opt（它本身并不是一个坏算法） –

或者它的一个不好的版本。如果你总是选择K _adjanced_节点，那么你不能做很多优化 –

我知道这个解决方案来自delphi。作者称其为“使用遗传算法进行优化”。如果我谷歌它，我觉得这种类型的解决方案。如果你把它称为'K-opt'（或者它甚至是唯一合法的官方名称）好。然后我学到了一些新东西。 – alzaimar

这就是所谓的Travelling Salesman Problem和一个合理和快速的近似是总是访问最近的未访问的节点，然后重试几个其他的起始位置相同。通常情况下，这会让您非常接近最佳解决方案。

另一种算法是首先构造图的最小生成树，然后删除重复的节点。这保证了次优性的某个上限（在欧几里德情况下不超过两倍）

另一种算法是从前三个节点开始，然后以某种顺序添加下一个节点（最初，按x坐标排序，按照距离中心的距离排序......），同时保持路径尽可能短，通过分割现有边（或在最后添加新的边）。

一旦你有一个解决方案（哪怕是个坏），你可以通过K-选择改进：反复挑选ķ随机边缘，完全删除它们，找到重新连接新的端点的最佳途径。 K-opt的一个变体是Lin-Kerningham启发式方法，该方法以三步选择步骤（以某种顺序）交替执行2选择步骤，其中三个边中的两个总是相邻的。

如果最边缘的丢失或很长（两个节点之间的distaces没有形成指标），那么你有问题。我们只是说它是NP完全的，确定如果这样的路径甚至存在，如果有缺失的边缘。

来源

2012-11-24 12:28:24

一个非常快速的近似是订购沿空间填充曲线的顶点。空间填充曲线减小了维度并保留了一些空间信息。尝试旅行商推销员问题的摩尔曲线，因为它是4条希尔伯特曲线的副本，因此起点和终点彼此相邻。但绘制起来要贵一些。

enter image description here

来源

2012-11-24 14:17:04 Bytemain

+1。不过，不确定它实际上比最接近的第一快。 –

用希尔伯特曲线更新一些tsp的例子。绿色的形状基本上是一个茶匙。 – Bytemain

@JanDvorak：你的意思是http://en.wikipedia.org/wiki/Nearest_neighbour_algorithm？我总是把这与http://en.wikipedia.org/wiki/Closest_pair_of_points_problem混淆。这不是这个消费者吗？ – Bytemain

如果你没有自己实现算法所需的信息，你可能想看看JGraphT。它有一个算法实现Hamiltonian Cycles。

来源

2012-11-24 14:58:22

太糟糕了，当链接失效时，这个答案将毫无用处。仅链接答案应该是评论。 –

如何获得的近似解得到的最短路径经过的所有节点会

回答

相关问题