The problem is this: I have a graph G=(V,E). a subgroup of vertices U<=V, and a start vertex s. weight function w for the edges. I need to find the shortest path from 's' that passes through all vertices in U. The calculation can be approximated, there should be some balance between calculation time and path length. I need a fast algorithm/heuristic that will produce a fine approximation for the shortest path. This algorithm shouldn't be too complicated to implement (in C++). for example, I have already thought of a way to make this into a Traveling Salesman Problem, and to use a TSP solver library or something that uses some kind of heuristic, but couldn't find any, and implementing the heuristic myself will be too hard. Thanks advanced! =]

c++algorithmpath-findingmotion-planning

GalDude33

Reputation: 7130

path planning - multiple destinations

The problem is this:

I have a graph G=(V,E). a subgroup of vertices U<=V, and a start vertex s. weight function w for the edges.

I need to find the shortest path from 's' that passes through all vertices in U.

The calculation can be approximated, there should be some balance between calculation time and path length. I need a fast algorithm/heuristic that will produce a fine approximation for the shortest path.
This algorithm shouldn't be too complicated to implement (in C++). for example, I have already thought of a way to make this into a Traveling Salesman Problem, and to use a TSP solver library or something that uses some kind of heuristic, but couldn't find any, and implementing the heuristic myself will be too hard.

Thanks advanced! =]

Upvotes: 1

Answers (2)

Xantix

Reputation: 3331

This is a variant of the Travelling Salesman Problem called the Set TSP problem, or Generalized TSP. Here's the Wikipedia link.

The reference from the above article link to a method for converting a Generalized TSP problem to a TSP problem without doubling the number of nodes in the graph.

The record-holding TSP solver is freely available and is known as Concorde, and can be downloaded from here, it can be run as a command-line tool (possibly as a library, not sure).

I came across GTSP when trying to create a solver for the game RevolvoMan4k by getting all pieces of money on each level with the minimum number of button pushes. (it's a fun game, but after level 50, the levels are random, so some may be impossible and need to be skipped with 'N').

Upvotes: 3

bigblind

Reputation: 12867

Imagine that you have 3 vertices: S, A and B. Now, let's say we need to find the shortest path from S through A and B. The easiest way to do this, is to find which point is closer to S: A or B. If your graph actually has some spatial data, you can approximate this using the vertices's co-ordinates, otherwise, you'll have to get the shortest path from S to each of your destinations. Pick the closest destination, in this case let's say that's A, and travel there. Now the only place you have left to go is B. Calculate the shortest path from A to B, and go there.

Now, in a situation with more than 2 destinations, you could do this recursively. I don't know C++, but here's some pseudocode that could get you started

function pathThrough(startNode,destinationNodes[])
    closestNode = getClosestNode(startNode,destinationNodes)
    newDestinations = removeFromArray(destinationNodes,closestNode)
    return joinPaths(getShortestPath(startNode,closestNode),pathThrough(closestNode,newDestinations.))

for the closestNode and getShortestPath functions, you can use whatever search algorithm suits your graph, A*, dijkstra's algorithm,...

Upvotes: 0

path planning - multiple destinations

Answers (2)

Related Questions