3

我想要得到的是：连接图中所有点的路径，但不必告诉算法从哪里开始和在哪里结束。

它需要在 google-maps api 中使用行车方向，但无需设置起点或终点。

这不是TSP问题，因为我没有“起始城市”，也不必回到“起始城市”。

正如这个问题所表达的：Find the shortest path in a graph which visit certain nodes，我可以只使用排列，因为我有几个节点，但问题是我需要分析这几个节点的几组所以我想要功能是最耗时的posible。

注意：我不是在寻找最小生成树，因为这也不是：https ://math.stackexchange.com/questions/130863/connecting-all-points-on-a-plane-with-shortest-path-possible 我想要一条告诉我，如果你先去这里，然后去那里，然后去那里，最后去那里，你会节省汽油。

问题：有没有可以帮助我的图书馆？或者它是一个已经有确切答案的已知问题？我该如何解决？

4

4 回答 4

2

听起来您想要一个全对最短路径算法。这是一类最短路径算法，它试图计算图中每对顶点之间的最短路径（或最短路径的长度）。

这是一个众所周知的问题，并且存在解决方案。这是一些描述其他可能算法的阅读材料。可能有针对您选择的语言和开发环境的 Johnson 算法的实现。

请记住，从计算上讲，这是一个代价高昂的问题。

于 2012-11-01T03:00:55.607 回答
0

如果我理解正确，您希望 1 条路线访问所有节点，没有预定义的开始/结束，并且您希望它是最小的。一个可能的解决方案可能是稍微修改您的图表以允许旅行推销员算法获得完整的旅行。

您从图表开始并添加 1 个额外的节点E。您将该节点连接到图中的所有其他节点，并将所有这些边的成本设置为非常高的常数M。然后，您在该图上释放一个旅行推销员算法，该算法将为您提供一条P从E的路径，通过所有节点并返回到E。如果您删除P连接E到路径其余部分的 2 条边，您将拥有您正在寻找的东西。

一个快速直观的证明，它确实是您正在寻找的：假设它不是连接所有节点的最便宜的方式。让我们称之为所谓的更好的路径Q。Q并且P都连接原始图中的所有节点。的终点Q是A和B。这两个都将连接到E具有 cost 边缘的节点M。如果您将这两条边添加到Q，您将获得比 更好的 TSP 解决方案P，这是P最好的。

于 2012-11-02T12:47:39.077 回答
0

当您使用谷歌地图时，您的特定 TSP 实例可能满足三角不等式。你真的是在说距离还是旅行时间？

在距离的情况下：尝试谷歌搜索：“三角形旅行商问题”

重要提示：结果是具有保证上限的最佳结果的非常好的近似值，但并不总是最好的。

于 2014-08-05T14:51:09.360 回答
0

一种方法是使用（自组织的）kohonen 网络。
假设您在地图上有n个城市（在任何维度上都一样）。
取一串n 个连接的“神经元”并将其随机放置在地图上。然后你做了几次迭代，一次迭代包含：

  1. 选择任何城市。（例如，以有序的方式浏览它们）
  2. 确定“最近的”神经元，称之为x。（例如欧几里得距离）
  3. 将这个x移动到更靠近城市的位置（例如，将方向向量从神经元到城市，并将其乘以学习率 0
  4. 将该神经元的邻居也移向该城市（但小于 3.，取决于从邻居到“当前最近的”神经元x的距离）

可以在步骤 2、3 和 4 中选择各种功能。

还要注意，这可能不会给出全局最短路径，因为它取决于起始链的位置和其他不同的东西。为此，可以考虑在不同的起始条件下进行多次运行，或者（取决于问题）可以对预知识有所帮助。

我希望这有助于为更多的读者完成这个问题......

于 2016-11-23T17:04:06.623 回答