The algorithm of A star search with a specified goal is pretty straightforward. However, what if there are multiple goals in a graph. For instance; you may want to find a shortest path that must include previously specified nodes. Constraint here is say your path must include A, B and C nodes( or more) not just find a path to node A or B or C. And of course the graph includes one or more A, B, C type nodes. So there is a question how can I adapt the A star search algorithm for multiple goals?
edit : we can visit nodes more than one.
You are describing conditions on path and not conditions on goal. A*, like all search algorithms - is finding a path to a goal [could be in a set, of goal, no problems with that].
Your problem [for the general case] is at least as hard as the Traveling Salesman Problem, and thus this problem is NP-Hard.
The reduction is simple: Given an instance of TSP - find the shortest path from a certain v to v such that the path is going through all vertices [constraint]. You can do it by simply marking each vertex with a different mark.
Note however, that A* algorithm has no problem to find shortest path to a vertex in a set of goal vertices. Remember that A* is based on Dijkstra's Algorithm, which is finding shortest path to all vertices from a single source.
You have a set z of all nodes, goal node G, and sets a though y of sub-goal nodes. Starting from S, the starting node, path to all nodes in a through y. Then, from those path to nodes in a through y, but if a route has already gone through a c node for example ignore all c nodes for that branch. Cull branches that move away from the eventual goal until you read the final goal state and have a path that runs through all known sub-goal states.
Hope that makes sense. I'll get a diagram up shortly, which might help.
Hmm.. Compute shortest paths from S->A, S->B, S->C, select the shortest (say to B), compute shortest path from B->C and B->A, select the shortest (say C), compute shortest path C to A. Then add the paths together.
[Edit]
Ok its not quite that simple. I think you could use A* to evalute shortest paths for all permutations between Start, A, B, C (which includes S->every node in the goal sets, each node in A to each in B etc.) and pick the shortest combination.
