AI Project 2: Search
Due: April
6 at Midnight. Paper due the next day in class.
Summary:
In
this project you will write a search program to do scheduling of
classes at a college. You will take two files, one with a list of
classes offered and another with a list of available rooms, and search
for an ideal distribution of classes in rooms.
Specifics:
Write
a program that uses a simulated annealing algorithm (probably the one
in your book.) to find an appropriate schedule for the classes in a
simulated college. You're program should read in data from two files
(prompting the user for those files).
One file will contain the data about the classes themselves. It will be in
the following format
- Each class will be represented as a single line in the file.
- Different fields will be separated by a comma
- The first field will be a textual representation of the class
name.
- The second field will be the 'class cap' the maximum number of
students in the class, an integer
- The third field will be the 'time slot'
for the class. To simplify things, rather than specify actual times,
we'll just use a single integer as a "time slot" for the course. For
example one set of courses might be scheduled for time slot 5.
The
other file will contain information about the rooms. Once again each
room will have its own line in the file. The two fields will be comma
separated.
- The first field will be a textual representation of a room.
- The second field will be the maximum number of seats in the classroom.
(the maximum number of students that it can hold)
The
output of your program should be an ordered file listing assignments of
classes to rooms. The list should be ordered based on the time slot of
the class. So all classes scheduled for time slot 1 should be first
followed by all classes in time slot 2 and so on.
Your algorithm
needs to assign each class to a classroom in a time slot with the
following restrictions. Only one class can be in a room in a particular
time slot. Furthermore we want to maximize the amount of classroom
space we use so we want to assign each class to the room that has the
closest maximum number of seats to the classes 'class cap' without the
class cap being larger than the max seats in the room.
If
there are classes that cannot be scheduled, then those classes should
be output at the end of your file with a note that the program was
unable to schedule them.
Evaluating your solution:
After
you have written your program you will need to write a short paper
evaluating it as an AI program. I want this paper in hard copy in class
the next day.
The paper should have the following format
Introduction:
What did your program do? What general class of problems
does it fall into?
Evaluation of the program as an AI program?
Does this program do something that only humans are very
good at?
How well does your progam work?
Is the solution generalizable?
Is the solution intelligent? in that it can handle the
sorts of issues that humans can
odd input
new requirement added
extra rooms added
more classes added
What would make the program more intelligent? Would there be some small
changes to your program that would make it more intelligent?
Summary
what algorithm did you implement and how intelligent was
it.
Submitting the code
When
submitting include the usual readme file with your name, how to run
your program, and any parts of the program that are unfinished.
Then
zip up your lab2 folder with a zip file of <your last
name>Lab2.zip (without the <> of course) and submit via email.