CSCI 4511W Midterm: CS 4511 UMN Midterm 1key 03
Document Summary
You are given the following graph, where each node has an identi er (a letter) and an h value. A number along an arc indicates the cost of the arc. G h=0 (a) show in what order a* expands nodes from start to g. g is the goal node. For each node expanded during the search show its f and g values. If a node is reached on multiple paths show its f and g values each time the node is reached, and indicate its parent node. To see why we can look for decreasing f values on any path. The triangle inequality is violated for nodes b and e. Answer: assuming that h is admissible, with values of w in the range 0 to 0. 5 the algorithm is guaranteed to nd an optimal solution (if there is a solution).
