Artificial Intelligence: Programming Assignment 1

Assigned: Jan. 22
Due: Feb. 19

The assignment is to write programs to solve the KERNEL problem described in Problem Set 1 using the two algorithms given there, implementing both using DFS and iterative deepenening; and to test these algorithms over randomly generated graphs.

Part I

Write a program that reads in a sequence of directed graphs G and solves the kernel problem on each using 4 different methods: Each of these methods should be run until finding the first solution, or until exhausting the state space.

Note: none of these programs should generate the state space as a data structure and 25% will be deducted for any program that does this. The state space is purely an implicit construct.

Form of the input

Each graphs is terminated in the input by a line containing a single asterisk. Each graph is represented in input by list of edges. An edge is a single line with the names of two vertices separated by a blank. A vertex is any single character other than asterisk. Different graphs may use the same vertex names. (E.g. vertex "A" may appear in two different graphs.) Blank lines are ignored. You may assume that the input is correctly formatted (i.e. you need not do error checking on the input.)

For example, a file containing graphs 1 and 2 from Problem Set 1 could have the following form:

A B
D A
B C
C D
*



E F
F G
G H
H I
I E
H E
*
The output for each method on each graph should be: Needless to say, if one method finds a solution, then all the other methods should find some (not necessarily the same) solution. If one method finds a solution and another method reports "No solution found", you're doing something wrong.

Part II

In this part of the assignment, you will test these methods on random graphs with 8 vertices and collect statistics. For p between 0 and 1, a random graph of density p is generated as follows:
for each vertex V do
   for each vertex U do
      if U != V 
         begin R := random number between 0 and 1;
               if R < p then add edge U -> V to G;
Carry out the following operation:
For p := {1/4, 1/2, 3/4} do
   For I := 1 to 100 do
      begin generate a graph G of density p over 8 vertices;
            run the four methods on G;
            collect the statistics listed below
      end
For each value of p and for each method, you should collect and report the following statistics: the average, max, min and standard deviation of the CPU time and of the number of state space nodes generated. That is, your output should give 96 numbers (3 values of p * 4 methods * 4 statistics * 2 measures of time.) In addition, you should report for each value of p, the fraction of graphs in which a solution is found. For instance, your output could have the following form:
p      Method      Measure  Avg     Min     Max      StDev
1/4  Alg. 1 DFS    CPU      2.3ms   0.5ms   15.6ms   1.5ms
1/4  Alg. 1 DFS    #States  35.4    8       200      10.2
1/4  Alg. 1 ID     CPU      1.5ms   0.8ms   25.4ms   0.6ms
...

When p=1/4, 90% of graphs have a kernel
When p=1/2, 40% of graphs have a kernel
When p=3/4, 20% of graphs have a kernel

Please note: The above numbers were entirely made up out of my head. I have no idea whether they're anywhere close to the true values.

Code may be written in any language that I can compile on the Sun system.

To submit

via email: Do not send object code.