Homework 1 CSE592 Applications of AI

Solution 

2.

A)

Write out the binary constraints which ensure 3 coloring of the following graph (I.e. color each of the nodes red, green or blue so that no nodes connected by an edge have the same color)

Write the domains of each of your variables, using R,G,B for the colors and the pairs of available values.

(1,2), (1,3), (1,4), (1,5) (2,3), (2,5), (3,4), (4,5) :

(R,G) (R,B) (G,R) (G,B) (B,R) (B,G)

(2,4), (3,5)

(R,G) (R,B) (G,R) (G,B) (B,R) (B,G)

 

B)

At the web address http://liawww.epfl.ch/~torrens/Project/JCL/jclhome.html there is a binary constraint solving applet.

Test the constraints you've written for the above graph at this site and see if they can be solved.

Test the constraints for the 10 queens problem which is given at this site. Try the basic solver and then try the solver with forward checking. Which is faster? In one sentence, describe why it is faster.

There are 6 possible colorings. One is:
V1=R V1=R V1=G V1=G V1=B V1=B
Forward checking is faster in this case because it prunes out from the search whole branches of the search space when it's determined that no leaves of that branch hold a solution.

3) The 8-puzzle problem

This question describes the use of search techniques for solving the 8 puzzle toy. The object of the toy is to slide tiles horizontally or vertically into a blank location with the goal of eventually reaching the configuration given on the right below. The arrow shows the move of sliding the 8 tile into the blank slot.

A) Assume we couch the 8 puzzle problem as state space search. Assume there is no checking for cycles. For the following methods, state if 1) they will always find a solution to the problem and 2) if they will always find the optimal solution (Ie the one which requires the fewest number of moves.

 
  1. Depth First Search

    2. a) No may get into endless loop(e.g. Left, Left, ... , Up,U, ..., Down, D, ... Right,R,.. and back to left again). Note that even if there are a finite number of board positions, the search tree can be infinite if there are cycles. B) No longer path to goal may be found first

  2. Breadth First Search

    3. a) Yes b) Yes

  3. Iterative Deepening

    4. a) Yes b) Yes

  4. A* with an admissable heuristic
    1. Yes b) Yes
  1. A* with a heuristic which is not admissable
    1. Yes, the heuristic can give a large cost to a node that would eventually reach the goal, but the cost must be finite and so A* will eventually expand it. f(n) *must* grow larger as A* searches deeper in the tree because g(n) depends on the depth of the tree. We assume that h(n) is always positive.
    2. No

B) State whether the following heuristics are admissable and briefly why or why not.
  1. The number of misplaced tiles

    2. Yes this never overestimates the number of remaining moves

  2. The number of turns it takes on average for a human player to solve this board position

No. This may overestimate the remaining number of moves.