CIS 730 (Introduction to Artificial Intelligence)
Due:
Monday, 15 September 2003 (by 5pm)
This
programming assignment is designed to apply your theoretical understanding of
search-based problem solving to the implementation of uninformed and informed
graph searches.
Refer to
the course intro handout for guidelines on working with other students.
Note: Submit the Homework on the webboard,
zipped with pseudonumber.
Data format: First, write a
driver (in Java, C++, SML, or an imperative programming language of your
choice) that takes input from standard input in the following format:
|
The vertical bar denotes comments.
|
Your program should ignore all input on a line containing the ‘|’ symbol.
|
|
The first non-comment line contains a single integer
|
denoting the number of nodes in the graph.
4
|
The second non-comment line contains the unique start node.
|
NB: The first node is 0, but this is not necessarily the start node.
0
|
The third non-comment line contains a list of goal nodes
|
separated by spaces.
3
|
The fourth non-comment line starts the edge-cost adjacency matrix.
|
The example below denotes the adjacency list:
|
0 ® (1) 1 ® 2 (2) ® NULL
|
1 ® 3 (5) ® NULL
|
2 ® 3 (1) ® NULL
|
3 ® NULL
*
1 2 *
*
* * 5
*
* * 1
*
* * *
|
After the adjacency matrix, the heuristic evaluation
|
vector is given, one node per line.
|
The heuristic in the example below is admissible – why?
3
1
1
0
1.
(10
points total) Uninformed (Blind) Search.
a)
(5
points) Implement a depth-first search of a graph in the above input
format. Your program should print the
list of nodes visited, one per line, and terminate as soon as the first goal
node is reached, printing the total path cost.
b)
(5
points) Implement a breadth-first search of a graph in the above input
format. Your program should print the
list of nodes visited, one per line, and terminate as soon as the first goal
node is reached, printing the total path cost.
2.
(30
points total) Informed (Heuristic)
Search.
a)
(10
points) Implement a branch-and-bound search of a graph in the above
input format. Your program should print
the list of nodes visited, one per line, and the accumulated cost g
for each expanded node. It should
terminate as soon as the first goal node is reached, printing the total path
cost.
b)
(10
points) Implement algorithm A to search a graph in the above input
format. Your program should print the
list of nodes visited, one per line, and the cost f = g + h for
each expanded node. It should terminate
as soon as the first goal node is reached, printing the total path cost. Given an heuristic matrix that corresponds
to an admissible heuristic evaluation function, your algorithm should behave as
A*.
c)
(10
points) Implement beam search with
the beam width w given as a
command-line argument. Your program
should print the list of nodes visited and the cost for each expanded node.
3.
(10
points) Documentation. Provide a
README file describing how to compile or interpret your program and run
it. All of your source files must be
named:
mp1-1a.{language}
mp1-1b.{language}
mp1-2a.{language}
mp1-2b.{language}
Extra credit:
(10 points) Implement simulated annealing search
using the same data format. Beam width
should appear in the input file on the last line.
Class participation:
a)
Post your
“turn-to-a-partner” exercise from Friday 29 Aug 2003, or a follow-up containing
your thoughts on this exercise to the CIS730 web board.
Post a single paragraph commentary on applications of machine translation (text-to-text, single-user speech-to-text or dictation, multiple-user speech-to-text or transcription). Specify a particular application domain. How effective do you think the state-of-the-art system would be in your hypothetical domain? How so?