CS 4341 B03 - Solutions HW 1

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
Part I. Homework Assignment
Part II. Project Assignment
Graduate Credit Problem

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:

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

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

Learning to apply course material (to improve thinking, problem solving, and decision) during the design, implementation, and analysis of computer programs that reason and/or act intelligently.
Learning fundamental principles about and generalizations of computational problem solving strategies.
Developing creative capacities for the design, implementation, and analysis of computer programs that reason and/or act intelligently.
Learning to analyze and experimentally evaluate designs and implementations of the intelligent computer programs, in particular those developed during the course projects.

This project consists of two parts:

Part I. A written homework assignment. Please hand in a HARDcopy of your group solutions at the beginning of class on Friday Nov. 07.
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:

For EACH of the search methods above,
1. follow by hand the way in which the search method seeks a path from S to G. Follow the output specifications of the project (Part II) to show for each method (as your computer program will do),
  1. the list of nodes in the order in which they were EXPANDED (not just explored), and
  2. the state of the "queue" when the node was expanded.
2. show for each search method the search tree constructed during the search.

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:

Each of the 9 search methods will be worth 11 points. These 11 points are distributed in the following way:
- 1 points for the list of expanded nodes in the correct order
- 6 points for handling the queue correctly according to the particular search method
  - 1 point for expanding the path at the front of the queue
  - 3 point for storing the children of the expanded node in the right position in the queue
  - 1 point for sorting the queue if necessary
  - 1 point for eliminating more expensive, redundant paths if necessary
- 4 points for the correct search tree
1 point for submit the homework (just to make the score sum up to 100 points :-)
Total: 100 points.

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!

CS4341 Introduction to Artificial Intelligence Solutions Homework 1 - B 2003

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

CS4341 Introduction to Artificial Intelligence
Solutions Homework 1 - B 2003