AI Fall 2006 - HW2 FAQ
  AI Home   |   HW2 Assignment

Click on a question to expand it (for the details).
Click on the question title again to hide the details.

+ Sample problems?

Question:

Can we see some sample 3-jug problems and solutions?


Answer:

Below are a few I've tried. Keep in mind that there may be many possible optimal solutions (any solution with the minimum number of steps possible is an optimal solution). My solutions number the jugs from 0 to 2.

Capacities Goal State Solution

(3 4 10)
(3 4 10)
  1. Fill jug 2
  2. Fill jug 1
  3. Fill jug 0

(3 4 10)
(2 2 2)		 No solution

(3 4 10)
(1 2 0)
  1. Fill jug 2
  2. Pour jug 2 into jug 1
  3. Pour jug 1 into jug 0
  4. Empty jug 0
  5. Pour jug 1 into jug 0
  6. Pour jug 2 into jug 1
  7. Empty jug 1
  8. Pour jug 2 into jug 1

(1 2 3)
(1 1 1)
  1. Fill jug 2
  2. Pour jug 2 into jug 1
  3. Pour jug 1 into jug 0

+ BFS depth limitation?

Question:

Is there an easy way to limit BFS search depth (using Dave's code)?


Answer:

If you are using Dave's BFS search code, you will need to make changes to limit the depth of the search. Here are a few possibilities:

Change the queue to something that not only holds a list of states, but to something that holds a list of labeled states, where each state saved in the queue also has a label (an indication of the depth at which that state was generated). Don't expand any state whose depth is the maximum. For example, each thing put on the queu could look like this: (depth state), where depth is an integer and state is something like '(1 2 3).

Another approach is to keep track of state depths using another data structure, like the parentlist used by Dave's code. You could use an association list to be able to save and lookup the depth of any state visited so far.

Note that is you do not visit the same state multiple times (Dave's BFS code that uses the parentlist does this), it is entirely possible to run out of states before you reach the depth limit. This implies there is no possible solution to the current problem.

+ DFS is slow?

Question:

My DFS is slow, is this normal?


Answer:

Yes, this is to be expected. You can include code to avoid visiting states that have already been visited (like Dave's BFS code) and this will speed things up significantly. Note that Dave's code for managing parentlist (which is used by unique-successor) is not efficient, a hash table would be much better for this.