Shortest path between two points through N checkpo

How to find shortest path between two points, namely S and D, in a matrix ? It should pass through multiple checkpoints named &. It cannot pass through G. * represents an open gate. Paths can pass through destination and checkpoints any number of times.

Example:

GGGGG
GS**G  
GGDGG  
G**&G  
GGGGG

Output for this matrix should be 6.

回答1:

The problem is easy when you only have one waypoint that you have to visit. You find the path (using A*, for instance) to the waypoint and then the path from the waypoint to the goal.

When the number of waypoints increases the problem gets exponentially harder, because you have to consider visiting any waypoint next. This becomes the Traveling Salesman Problem.

General approaches are to approximate the shortest solution by choosing the waypoint that looks best next, or to find the optimal solution by trying all possibilities. (The wikipedia page linked above goes into these.)

But, you'll need to do your own research on these -- far beyond the scope of what we can help you with here.

A good next step would be to choose an approach to implement. If you don't understand it you can ask specifically how some aspect of the approach works. But, full solutions are complicated, so you won't get much coding help with such a general question.

For optimal solutions your best bet is a depth-first branch and bound search. This is a depth-first search with pruning - eliminating paths that are guaranteed to be worse that your best solution so far. You can find information about the algorithm on many pages, including this one, but if you have a question about how to implement a specific algorithm you should start working on that algorithm and then ask a new question about that.

Your question of how to do it has been answered by both questions here at the same level of detail of your own question. Nobody is going to post a full source-code solution for you here, as this sounds like a class assignment. When you start implementing something and get stuck, feel free to ask another question about exactly what is getting you stuck.

回答2:

For this kind of problem, you need to do 2 steps:

Find the shortest path from your source node to the other using Breadth First Search (BFS);
Reconstruct the graph with only S, D and & points, and the weight of each edge is the shortest path between them in original path you calculated in the first step, then the problem becomes a typical Travelling Salesman Problem.