Blog

A*SeachQuestions 1-5 are based on the following information:…

A*SeachQuestions 1-5 are based on the following information: Use a graph over 8 nodes where O is the starting node and G is the goal node. The following is a list of distances between pairs of nodes in the usual linked-list representation for a graph. (O, Z, 7), (O, S, 15), (Z, A, 15), (A, S, 14), (A, R, 16), (S, R, 8), (S, F, 10), (R, P, 10), (F, G, 20), (P, G, 10). Any pair missing here is presumed to have infinite distance, e.g., (O, R, inf).   [You may like to draw the graph for your convenience.] The heuristic values (h, or line-of-sight distances to G) for the nodes are: (O, 38), (Z, 37), (A, 37), (S, 25), (R, 19), (F, 18), (P, 11), (G, 0). A* search will start by computing f-value for the start-node O as f=0+38=38 and put it in a priority queue. Then, popping O from the queue, A* will compute the f-values of the nodes connected to O, and insert them in the priority queue. Question 1: Which answer below is the priority-queue’s status at the FIRST iteration of A*-search? [In all the answers, first the best node from previous iteration is stated as it is popped off the queue. Then, the status of the queue is shown with the f value of each node pushed in connected nodes are added with updated f values. Initial queue status of only O in it is ignored. First iteration starts next as in this question. Also going back to the parent node from the currently selected node is ignored as distances are all non-negative.]