CS4341 Introduction to Artificial Intelligence
HOMEWORK 1 - C 2000
DUE DATE: Tuesday, Jan 25 at 5 pm.
- Instructions for Homework 1:
- This is an INDIVIDUAL homework
- The homework is due Tuesday, January 25, 2000 at 5 pm.
Please turn in the homework using the
turnin system.
- Homework Problems:
This homework consists of two (plus an additional problem for students
who are taking this course for graduate credit) problems:
Problem 1 (40 points + extra-points): Problem Solving Strategies
Consider the following puzzle (taken from Russell and Norvig's textbook, 1995)
This puzzle consists in finding a substitution of the letters
F, O, R, T, Y, E, N, S, I, X
by digits such that when each of these letters is replaced
by the corresponding digit, the following sum is still arithmetically
correct.
FORTY
+ TEN
+ TEN
-----
SIXTY
This puzzle has solutions. One of them is
F = 2, O = 9, R = 7, T = 8, Y = 6, E = 5, N = 0, S = 3, I = 1, X = 4
since:
29786
+ 850
+ 850
-----
31486
is arithmetically correct.
Solutions to the puzzle should not repeat digits.
Your mission is to:
- Design a computer system that uses the generate-and-test strategy
to solve this puzzle.
- Your system must satisfy the following conditions:
- It should find at least one solution to the puzzle.
- The generator must be
- complete, and
- non-redundant
- Write a computer program using any high level programming language
(Lisp, Prolog, C, C++, ...) that implements the system you designed
to solve this puzzle. Your program must run in the CCC machines.
- You will receive extra credit if:
- your program produces a solution to the puzzle different to the one
given above
(extra points for each additional correct solution found),
OR
if you prove (providing a formal argument) that
no other solutions are possible.
- your generator is informed.
For this problem, you need to "turnin" the following material by the
deadline:
- A description of your system (generator and tester) together with
formal arguments showing that the generator is complete and
non-redundant.
- Your program code. Your program code should be documented using the
departmental documentation standard
- A transcript containing the solutions found by your program.
- A precise count of how many different candidate solutions your
generator would produce before exhausting all possibilities.
- For the extra credit you need to include also:
- A formal argument showing that your generator is informed.
Problem 2: Search (60 points)
Consider the graph on page 634 (figure E4.1) of your textbook.
S denotes the starting state and G denotes the goal state.
The number attached to each edge in the graph represents the COST
of traversing the edge. Assume also that the ESTIMATED
distances to the goal are given by the following table:
| FROM
| TO
| ESTIMATED DISTANCE
|
| S
| G
| 10
|
| A
| G
| 8
|
| B
| G
| 5
|
| C
| G
| 1.4
|
| D
| G
| 9
|
| E
| G
| 6
|
| F
| G
| 2
|
| G
| G
| 0
|
For EACH of the following search methods show the search tree as it is
explored/expanded by the method until it finds a path from S to G.
Number the nodes in the order in which they are expanded by each method.
Show your work.
- Depth 1st
- Breadth 1st
- Depth-limited Search (depth-limit = 3)
- Iterative Deepening Search
- Branch-and-bound (= Uniform Cost Search)
- Greedy Search (= Best 1st Search)
- A*
- Hill-climbing
- Beam Search (m = 2)
Problem G: Additional Graduate Credit Problem (20 points)
We have computed optimal paths under the assumption that COSTS are
non-negative. Suppose that we remove that assumption.
Discuss how allowing some of the costs (both g and h values)
to be negative would affect
the search methods below, and illustrate the effects of this change with
examples.
- Depth 1st
- Breadth 1st
- Depth-limited Search
- Iterative Deepening Search
- Branch-and-bound (= Uniform Cost Search)
- Greedy Search (= Best 1st Search)
- A*
- Hill-climbing
- Beam Search