Consider the maze show below, in which the successors of a cell include any adjacent cell...

Transcribed Image Text:

Consider the maze show below, in which the successors of a cell include any adjacent cell in the directions North, South, East, and West of the current cell, except at the boundary of the maze or when a barrier (thick line) exists. A B C DE FSHKMN P Q RT G For example, successors(M) = {D, N, G}. Assume each move has cost 1. Find a path from cell S to cell G. Break ties, if needed, using the alphabetical order of the labels in the cells, so Breadth- First Search would visit cells in the order: SFHPKQCRATBG. For parts (a-b) below, what is the order of nodes expanded (plus the goal node if it is found) by each of the following search strategies? a) Depth-First Search. Assume cycles are detected and eliminated by never expanding a node containing a state that is repeated on the path back to the root. b) Greedy Search. Use as the heuristic function h(state) = Manhattan distance from state to G assuming there were no barriers. For example, h(K)-2 and h(S)=4. c) A* Search. Use the same heuristic function as in b). Remove redundant states. Consider the maze show below, in which the successors of a cell include any adjacent cell in the directions North, South, East, and West of the current cell, except at the boundary of the maze or when a barrier (thick line) exists. A B C DE FSHKMN P Q RT G For example, successors(M) = {D, N, G}. Assume each move has cost 1. Find a path from cell S to cell G. Break ties, if needed, using the alphabetical order of the labels in the cells, so Breadth- First Search would visit cells in the order: SFHPKQCRATBG. For parts (a-b) below, what is the order of nodes expanded (plus the goal node if it is found) by each of the following search strategies? a) Depth-First Search. Assume cycles are detected and eliminated by never expanding a node containing a state that is repeated on the path back to the root. b) Greedy Search. Use as the heuristic function h(state) = Manhattan distance from state to G assuming there were no barriers. For example, h(K)-2 and h(S)=4. c) A* Search. Use the same heuristic function as in b). Remove redundant states.

Answer rating: 100% (QA)

For DepthFirst Search the order of nodes expanded would be S F ... View the full answer