DM828 - Introduction to Artificial Intelligence
Sheet 1, Autumn 2011 [pdf format]

Prepare these exercises for Thursday, November 10.


Exercises

  1. From B1, do exercises 3.9, 3.14, 3.16, 3.19, 3.29.
  2. 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.


    1. =3exDraw the portion of the state space for states 1 to 15.
    2. 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.
    3. Would bidirectional search be appropriate for this problem? If so, describe in detail ho wit would work.
    4. What is the branching factor in each direction of the bidirectional search?
  3. Consider the tree below. The leaves are roots of remaining subtrees not represented in the figure. We can examine this tree with different algorithms. The values on the edges of the tree represent the step cost, while the h values on the nodes, next to the identifying letter, are the heuristic values for completing a solution from that node. Simulate the search for the following strategies:

    Please, write your answer in a similar form as follows:


    StepVisitedFrontier
    1AB I
    2BC F B I
    3CD E F B I


    At each step indicate the node expanded and the frontier queue.


    Order the queue such that the first node is the next node to be removed for expansion. (Assume that the children of a node are expanded in alphabetical order when no other order is specified by the search.)


    In addition, comment what would make the best-first an A* search.