CAP4630 Introduction to Artificial Intelligence

[2 pts] 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

Draw the portion of the state space for states 1 to 15 (1 pt)

Suppose the goal state is 11. List the order in which nodes will be visited for depth-limited search with limit 3 (0.5 pt), and iterative deepening search. (0.5 pt)

1 procedure DFS-iterative(G,v): 2 let S be a stack 3 S.push(v) 4 while S is not empty V : S.pop() if v is not labeled as discovered: label v as discovered for all edges from v to w in G.adjacentEdges(v) do S.push(w) Figure 2 Depth First Search DFS (Method 1) s stack s.push(initial node) add initial node to visited while s is not empty: Figure 1 Set all nodes to not visited" q new Queue(); q.enqueue (initial node); wile q empty do V s.peek() if for all E(v,u) there is one unvisited u: x q.dequeue(); mark u as visited if ( x has not been visited) s.push(u) visited[x] true; // Visit node x else for every edge (x, y) /* we are using all edges) if (y has not been visited) .pop q.enqueue(y) // Use the edge (x,y)!!! Figure 3 Depth First Search (Method 2) Figure 2: Breath First Search (BFS)