University of Washington, Bothell

CSS 485: Introduction to Artificial Neural Networks
Fall 2002
Homework Assignment 1: Fitness & State Spaces

Assigned: Monday, October 7, 2002
Due: Wednesday, October 16, 2002 (start of class)

1. A joint probability $P(A,B)$ is the probability of two events both happening, and so can also be written as $P(A \wedge B)$. Use your knowledge of probability to prove that the probability of at least one of two events happening is $P(A \vee B) = P(A) + P(B) - P(A \wedge B)$.
2. If we think of $A$ and $B$ as sets, then their joint probability can also be written as $P(A \cap B)$, the probability of at least one happening $P(A \cup B)$, etc. Assuming that $A \cap B \neq \emptyset$, develop an expression for $P((A \cup B) - (A \cap B))$ (exclusive or).
3. Develop a program that solves the 8 puzzle using an uninformed (brute force) search. Your program should be optimal, despite being uninformed. For this problem and the next, you might want to think about the class hierarchy defined in SearchClasses.h. Submit hard copy of your code and a couple example runs (see next problem). In the written part of the assignment, describe the search algorithm you used.
4. Develop a program to perform Heuristic (A*) search to solve the 8 puzzle. Describe in your written assignment the heuristic function you used; prove that it always underestimates the distance to the goal. Submit your program hard copy and a couple example runs. Choose example runs where this algorithm outperformed uninformed search.
5. For extra credit, try the 15 puzzle (4x4). Briefly describe what happened when you tried to run this.