WPI Worcester Polytechnic Institute

Computer Science Department

CS4341 Introduction to Artificial Intelligence 
Solutions Homework 1 - B 2003

By Prof. Carolina Ruiz, Matt Jarvis, and Peter Mardziel  


Homework and Project Goal:

    The goal of Project 1 is to help you understand exactly how different search strategies work.  You will implement each of nine net search algorithms.  Among the searches are basic searches, heuristically informed searches, and optimal searches.

In particular, the search strategies included in this project are:

  1. Depth 1st search
  2. Breadth 1st search
  3. Depth-limited search (depth-limit = 3)
  4. Iterative deepening search (show all iterations, not just the iteration that succeeds)
  5. Basic Branch-and-bound (= Uniform cost search) with neither Estimated Distance nor Dynamic Programming
  6. Greedy search (= Best 1st search)
  7. A*
  8. Hill-climbing
  9. Beam search (w = 2)

The goal of this project and homework matches the following Course Objectives:

This project consists of two parts:

  1. Part I. A written homework assignment. Please hand in a HARDcopy of your group solutions at the beginning of class on Friday Nov. 07.
  2. Part II. An implementation project. Please submit your group solutions using the turnin system by Monday, Nov. 10 at 9:00 pm.

Part I. Homework Assignment:

Suppose that you need to find a path between S and G in the following graph. See the description of this graph input format below.
S M 15
S A 1
M G 15
A I 5
A C 2
A B 50
C E 1
C D 10
I J 4
J K 50
J L 5
K L 5
L M 35
S 22
M 14
I 10
J 8
K 6
L 4
E 18
C 16
D 20
A 12
B 24

A picture of this graph is included below. Note that the (under)estimated distance of each node to the goal is included inside the node. (Special thanks to Peter Mardziel for creating this picture).

The homework assignment is the following:

Note that the homework solutions should follow exactly the same conventions as the project description below. In particular, the children of a node should be considered ordered in alphabetical order.

Homework Submission:

The homework is due at 10 am on Friday November 07, 2003.  Please hand in one HARDcopy of your group solutions to the homework assignment by the beginning of the class on Friday, Nov. 07.

Homework Grading:

Homework Solutions:

Many thanks to Matt Jarvis for creating the search trees and to Peter Mardziel for generating the traces of the queues.

Depth First Expanded Queue S [<S>] A [<A,S> <M,S>] B [<B,A,S> <C,A,S> <I,A,S> <M,S>] C [<C,A,S> <I,A,S> <M,S>] D [<D,C,A,S> <E,C,A,S> <I,A,S> <M,S>] E [<E,C,A,S> <I,A,S> <M,S>] I [<I,A,S> <M,S>] J [<J,I,A,S> <M,S>] K [<K,J,I,A,S> <L,J,I,A,S> <M,S>] L [<L,K,J,I,A,S> <L,J,I,A,S> <M,S>] M [<M,L,K,J,I,A,S> <L,J,I,A,S> <M,S>] G [<G,M,L,K,J,I,A,S> <L,J,I,A,S> <M,S>] goal reached!

Breadth First Expanded Queue S [<S>] A [<A,S> <M,S>] M [<M,S> <B,A,S> <C,A,S> <I,A,S>] B [<B,A,S> <C,A,S> <I,A,S> <G,M,S> <L,M,S>] C [<C,A,S> <I,A,S> <G,M,S> <L,M,S>] I [<I,A,S> <G,M,S> <L,M,S> <D,C,A,S> <E,C,A,S>] G [<G,M,S> <L,M,S> <D,C,A,S> <E,C,A,S> <J,I,A,S>] goal reached!

Depth Limited (L=3) Expanded Queue S [<S>] A [<A,S> <M,S>] B [<B,A,S> <C,A,S> <I,A,S> <M,S>] C [<C,A,S> <I,A,S> <M,S>] I [<I,A,S> <M,S>] M [<M,S>] G [<G,M,S> <L,M,S>] goal reached!

Iterative Deepening Expanded Queue L=1 S [<S>] L=2 S [<S>] A [<A,S> <M,S>] M [<M,S>] L=3 S [<S>] A [<A,S> <M,S>] B [<B,A,S> <C,A,S> <I,A,S> <M,S>] C [<C,A,S> <I,A,S> <M,S>] I [<I,A,S> <M,S>] M [<M,S>] G [<G,M,S> <L,M,S>] goal reached!

Branch and Bound Expanded Queue S [0<S>] A [1<A,S> 15<M,S>] C [3<C,A,S> 6<I,A,S> 15<M,S> 51<B,A,S>] E [4<E,C,A,S> 6<I,A,S> 13<D,C,A,S> 15<M,S> 51<B,A,S>] I [6<I,A,S> 13<D,C,A,S> 15<M,S> 51<B,A,S>] J [10<J,I,A,S> 13<D,C,A,S> 15<M,S> 51<B,A,S>] D [13<D,C,A,S> 15<L,J,I,A,S> 15<M,S> 51<B,A,S> 60<K,J,I,A,S>] L [15<L,J,I,A,S> 15<M,S> 51<B,A,S> 60<K,J,I,A,S>] M [15<M,S> 20<K,L,J,I,A,S> 50<M,L,J,I,A,S> 51<B,A,S> 60<K,J,I,A,S>] K [20<K,L,J,I,A,S> 30<G,M,S> 50<L,M,S> 50<M,L,J,I,A,S> 51<B,A,S> 60<K,J,I,A,S>] G [30<G,M,S> 50<L,M,S> 50<M,L,J,I,A,S> 51<B,A,S> 60<K,J,I,A,S>] goal reached!

Greedy Expanded Queue S [22<S>] A [12<A,S> 14<M,S>] I [10<I,A,S> 14<M,S> 16<C,A,S> 24<B,A,S>] J [8<J,I,A,S> 14<M,S> 16<C,A,S> 24<B,A,S>] L [4<L,J,I,A,S> 6<K,J,I,A,S> 14<M,S> 16<C,A,S> 24<B,A,S>] K [6<K,J,I,A,S> 6<K,L,J,I,A,S> 14<M,S> 14<M,L,J,I,A,S> 16<C,A,S> 24<B,A,S>] L [4<L,K,J,I,A,S> 6<K,L,J,I,A,S> 14<M,S> 14<M,L,J,I,A,S> 16<C,A,S> 24<B,A,S>] K [6<K,L,J,I,A,S> 14<M,S> 14<M,L,J,I,A,S> 14<M,L,K,J,I,A,S> 16<C,A,S> 24<B,A,S>] M [14<M,S> 14<M,L,J,I,A,S> 14<M,L,K,J,I,A,S> 16<C,A,S> 24<B,A,S>] G [0<G,M,S> 4<L,M,S> 14<M,L,J,I,A,S> 14<M,L,K,J,I,A,S> 16<C,A,S> 24<B,A,S>] goal reached!

A* Expanded Queue S [22<S>] A [13<A,S> 29<M,S>] I [16<I,A,S> 19<C,A,S> 29<M,S> 75<B,A,S>] J [18<J,I,A,S> 19<C,A,S> 29<M,S> 75<B,A,S>] C [19<C,A,S> 19<L,J,I,A,S> 29<M,S> 66<K,J,I,A,S> 75<B,A,S>] L [19<L,J,I,A,S> 22<E,C,A,S> 29<M,S> 33<D,C,A,S> 66<K,J,I,A,S> 75<B,A,S>] E [22<E,C,A,S> 26<K,L,J,I,A,S> 29<M,S> 33<D,C,A,S> 75<B,A,S>] K [26<K,L,J,I,A,S> 29<M,S> 33<D,C,A,S> 75<B,A,S>] M [29<M,S> 33<D,C,A,S> 75<B,A,S>] G [30<G,M,S> 33<D,C,A,S> 54<L,M,S> 75<B,A,S>] goal reached!

Note: This version of Hill Climbing allows BACKTRACKING. Hill Climbing Expanded Queue S [22<S>] A [12<A,S> 14<M,S>] I [10<I,A,S> 16<C,A,S> 24<B,A,S> 14<M,S>] J [8<J,I,A,S> 16<C,A,S> 24<B,A,S> 14<M,S>] L [4<L,J,I,A,S> 6<K,J,I,A,S> 16<C,A,S> 24<B,A,S> 14<M,S>] K [6<K,L,J,I,A,S> 14<M,L,J,I,A,S> 6<K,J,I,A,S> 16<C,A,S> 24<B,A,S> 14<M,S>] M [14<M,L,J,I,A,S> 6<K,J,I,A,S> 16<C,A,S> 24<B,A,S> 14<M,S>] G [0<G,M,L,J,I,A,S> 6<K,J,I,A,S> 16<C,A,S> 24<B,A,S> 14<M,S>] goal reached!

Beam Expanded Queue S [22<S>] A [12<A,S> 14<M,S>] M [14<M,S> 24<B,A,S> 16<C,A,S> 10<I,A,S>] G [0<G,M,S> 4<L,M,S>] goal reached!