Description

Homework #2 – Part 1
Guideline: Please complete the following problems and submit the answers as a single PDF file to Camino.

Problem 1: Consider a state space where the start state is number 1 and the successor function for state n returns two states, numbers 2n and 2n + 1.
(a). Draw the portion of the state space for states 1 to 15.
(b). Suppose the goal state is 11. List the order in which nodes will be visited for breadth-first search, depth-limited search with limit 3, and iterative deepening search.
Problem 2: (Provide derivations of your answer, that is, draw the search tree, and write down the list of visited nodes and the corresponding frontier nodes). Execute Tree Search through this graph (i.e. do not remember visited nodes). S is the start node, and G is the goal node. Step costs are given next to each arc. Heuristic function values are given in the table on the right. The successors of each node are indicated by the arrows out of that node. Use the alphabetical order as tie-breakers, i.e. if nodes A, B, and C are available to expand, expand A before B, B before C. For each search strategy below, show the order in which nodes are expanded, ending with the goal node that is found. Show the solution path from start to goal, and give the cost of the solution path that is found.

2.a depth-first search
Order of node expansion: ____________________________________________________________
Path found: _________________________________ Cost of path found: _____________________ 2.b uniform-cost search
Order of node expansion: ____________________________________________________________
Path found: _______________________________________ Cost of path found: _______________
2.c greedy (best-first) search with h(n)
Order of node expansion: ____________________________________________________________
Path found: ____________________________________ Cost of path found: __________________
2.d iterative deepening depth-first search
Order of node expansion: ____________________________________________________________
Path found: _________________________________ Cost of path found: _____________________ 2.e A* search with h(n)
Order of node expansion: ____________________________________________________________
Path found: __________________________________ Cost of path found: ____________________

Problem 3: (Provide derivations of your answer, that is, work on the search tree, write down the list of visited nodes and the corresponding frontier nodes). Consider the search tree below. The two goal states G1 and G2 are indeed the same goal. The numbers on the edges represent step-costs. You also know the following heuristic estimates: h(B→G2) = 9, h(D→G2) =10, h(A→G1)=2, h(C→G1)=1. In what order will A* search visit the nodes? Explain your answer by giving the value of the evaluation function f(n) for those nodes that the algorithm considers. Also give the solution path.