1. Search practice: START h=4 A C h=4 2 2 h=4 4 3 2 B h=4...

Transcribed Image Text:

1. Search practice: START h=4 A C h=4 2 2 h=4 4 3 2 B h=4 4 D h=4 3 G h=4 h=3 F h=3 4 3 3 h=3 GOAL h=0 K h=3 3 2 H E h=3 3 h=2 For each of the following search algorithms, write the following two things: (1) The order in which nodes are expanded during search (e.g., Start, B, A, E, ..., Goal) (2) The path that is returned once search is completed (e.g., Start-B-E-H-Goal) Assume that ties are broken by alphabetical order. Each state is labeled with an estimated value based on a heuristic function (e.g., state E has an estimated cost of 3). Each edge connecting nodes is labeled with the action cost (e.g., to go from state A to state C costs 2). Edges are bidirectional so the cost to go from state A to state C is the same cost as going from state C to state A. a) Depth-first search b) Breadth-first search c) Uniform cost search d) Greedy search (use the heuristic values labeled h) e) A* search (use the heuristic values labeled h) 1. Search practice: START h=4 A C h=4 2 2 h=4 4 3 2 B h=4 4 D h=4 3 G h=4 h=3 F h=3 4 3 3 h=3 GOAL h=0 K h=3 3 2 H E h=3 3 h=2 For each of the following search algorithms, write the following two things: (1) The order in which nodes are expanded during search (e.g., Start, B, A, E, ..., Goal) (2) The path that is returned once search is completed (e.g., Start-B-E-H-Goal) Assume that ties are broken by alphabetical order. Each state is labeled with an estimated value based on a heuristic function (e.g., state E has an estimated cost of 3). Each edge connecting nodes is labeled with the action cost (e.g., to go from state A to state C costs 2). Edges are bidirectional so the cost to go from state A to state C is the same cost as going from state C to state A. a) Depth-first search b) Breadth-first search c) Uniform cost search d) Greedy search (use the heuristic values labeled h) e) A* search (use the heuristic values labeled h)