Consider the state space graph shown above. A is the start state and G is the...

Transcribed Image Text:

Consider the state space graph shown above. A is the start state and G is the goal state. The costs for each edge are shown on the graph. Each edge can be traversed in both directions. A 3 B 2 3 D 4 E • A* search with heuristic h₁ •A* search with heuristic h₂ 7 F 5 G State A B C D E F G h₁ 12.5 12 11 5 1 4 0 h₂ 11 10 a) For each of the following graph search strategies, find the path it returns. Assume ties are resolved alphabetically (earlier alphabetical order are expanded first). Write out the order in which states are added to the fringe. • Uniform cost search b) What is the cost of the shortest uniform cost path from A to G? c) Is h₁ admissible? Is it consistent? Why? d) Is h₂ admissible? Is it consistent? Why? 9 6 2 4.5 0 Consider the state space graph shown above. A is the start state and G is the goal state. The costs for each edge are shown on the graph. Each edge can be traversed in both directions. A 3 B 2 3 D 4 E • A* search with heuristic h₁ •A* search with heuristic h₂ 7 F 5 G State A B C D E F G h₁ 12.5 12 11 5 1 4 0 h₂ 11 10 a) For each of the following graph search strategies, find the path it returns. Assume ties are resolved alphabetically (earlier alphabetical order are expanded first). Write out the order in which states are added to the fringe. • Uniform cost search b) What is the cost of the shortest uniform cost path from A to G? c) Is h₁ admissible? Is it consistent? Why? d) Is h₂ admissible? Is it consistent? Why? 9 6 2 4.5 0

Answer rating: 100% (QA)

Answer option ... View the full answer