Use A* on an undirected graph, where you have to visit specific nodes, where an

Question

Use A* on an undirected graph, where you have to visit specific nodes, where an edge weight and a node weight are incoorperated into the graph. What kind of Heuristic function should I use?

An example of this problem: A cargo plane has to do certain deliveries between specific nodes. e,g, Deliveries between A->B,    C->A,     D->B. Use an A* search to find the optimal path to travel through the graph which completes the deliveries.

I kind of know how to do an A* search to get from a single start node to an end node, but here there are multiple goal(delivery paths) to cover. How would I do this?

Explanation / Answer

There are multiple goals in a graph. Strait line distance SLD from a node to goal node help to find the shortest path from source node to goal node. In this case there are many goal nodes, Heuristic function is proposed to use minimum straight-line distance from a node to all goal nodes. Try to implement A* in following way:

Algorithm A*(Graph, source, Goals)

n? number of gold nodes

for each vertex v in Graph

        value of vertex? minimum SLD from all goal nodes

source to open list OL

while (n>0&&(OL is not Empty)

           extract a node with minimum value from open list OL

            if(N is one of Goal)

                 n?n-1

          for each adjacent vertex u of N

                 if(fvalue(u), > (heuristic value of u + sum of edge cost value from source to u))

                         fvalue(u) ? heuristic value of u + sum of edge cost value from source to u

                        if u is in close list put it in OL.

          Put N in close list.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.