K-旅行商优化 [英] k-Travelling Salesman optimization

问题描述

给定一个加权图其当前我有超过100个节点。接下来的问题是如何通过节点属于内置图形阵列（用于实例10个节点），找到最短之旅。这个问题看上去类似旅行商问题，但事实并非如此。

Given a weighted graph which current I have more than 100 nodes. The question is then how to find shortest tour through an array of nodes (10 nodes for instances) which belongs to the built graph. The question seems similar to traveling salesman problem but it's not.

我目前的解决方案是非常简单 第1步：建立从10个节点数组的新图，我必须从构建旅游 第2步：使用Dijkstra算法来寻找节点之间的距离，连接所有的顶点图 第3步：现在，它只是变成旅行商问题

My current solution is quite straightforward Step 1: Build a new graph from array of 10 nodes which I have to construct tour from Step 2: Use Dijkstra to find distance between nodes and connect all the vertices in the graph Step 3: Now it simply turns into traveling salesman problem

容易。然而，第2步复杂度为O（n ^ 2），因为我必须要找到最短路径（其中有Dijkstra算法多项式复杂性），新图的节点的所有组合。

Easy. However, step 2 complexity is O(n^2) since I have to find shortest path (which Dijkstra having polynomial complexity) for all combination of nodes of new graph.

我怎样才能让我的算法快？最好的情况是，我可以消除不必查找最短距离为节点，在我的新图的每对组合的瓶颈。

How can I make my algorithm faster? Best case being I can eliminate the bottleneck of having to find shortest distance for every pair combinations of nodes in my new graph.

推荐答案

Dijkstra算法度为O（E日志（N））的复杂性，如果你有完整的图形（你有，如果你正在做TSP），比你可以写为O（N²的log（n）），对所有节点对它是O（N 4的log（n））。因此，它应该是更有效地使用弗洛伊德算法，该认定所有对节点之间的O（N³）。最短路径

Dijkstra has complexity of O(E log(N)), if you have complete graph (which you have, if you are doing TSP), than you can write it as O(N² log(N)), for all pairs of nodes it is O(N⁴ log(N)). Hence it should be more efficient to use Floyd-Warshall algorithm, which finds shortest path among all pairs of nodes in O(N³).

这篇关于K-旅行商优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！