Consider the following graph where Start is the start and Goal is the goal state. For...

 

Transcribed Image Text:

Consider the following graph where Start is the start and Goal is the goal state. For the following sub-questions, ties are broken in alphabetical order. h-6. 3 Start h=9 h=6 E b-8 h-5 h-3 3 Goal h-0 1. (8 pts) In what order are states expanded by DFS? What path would DFS return? 2. (8 pts) In what order are states expanded by BFS? What path would BFS return? 3. (8 pts) In what order are states expanded by UCS? What path would UCS return? 4. (8 pts) In what order are states expanded by Greedy? What path would Greedy return? 5. (8 pts) In what order are states expanded by A"? What path would A" return? 6. (5 pts) Is the heuristic in the above graph admissible? If not, provide a minimal set of edges whose costs must be changed along with their new costs to make the heuristic admissible. 7. (5 pts) Is the heuristic in the above graph consistent? If not, provide a minimal set of edges whose costs must be changed along with their new costs to make the heuristic consistent. Consider the following graph where Start is the start and Goal is the goal state. For the following sub-questions, ties are broken in alphabetical order. h-6. 3 Start h=9 h=6 E b-8 h-5 h-3 3 Goal h-0 1. (8 pts) In what order are states expanded by DFS? What path would DFS return? 2. (8 pts) In what order are states expanded by BFS? What path would BFS return? 3. (8 pts) In what order are states expanded by UCS? What path would UCS return? 4. (8 pts) In what order are states expanded by Greedy? What path would Greedy return? 5. (8 pts) In what order are states expanded by A"? What path would A" return? 6. (5 pts) Is the heuristic in the above graph admissible? If not, provide a minimal set of edges whose costs must be changed along with their new costs to make the heuristic admissible. 7. (5 pts) Is the heuristic in the above graph consistent? If not, provide a minimal set of edges whose costs must be changed along with their new costs to make the heuristic consistent.