CSCI-UA.0472 Artificial Intelligence - Programming Assignment 1: Best Independent Set problem

Programming Assignment 1 

Assigned: January 23 
Due: February 13

Assignment 

Write two programs that solves the Best Independent Set problem, as described in Problem Set 1. The first will use iterative deepening; the second will use simple hill climbing with random restart.

Input 

Input should be a text file named "input.txt" in the same working directory as the code with the following contents:

• Line 1: The target (a positive integer) and flags: "V" for verbose output or "C" for compact output. For the hill-climbing program, the number of random restarts to run.
• Each vertex. Name (you may assume that this is a single alphabetic character) and value (a positive integer), 1 per line.
• Blank line
• Each edge: the names of the two ends. 1 per line.

Your program should be robust as regards trailing white space at the end of a line of input or blank lines at the end of the input. CourseNana.COM

Examples are given below. CourseNana.COM

Search 

The programs should search through the state space until either: 
a) A solution is found. 
b) In iterative deepening, search to depth K finds no states at depth K. (That is, none of the states at depth K-1 have any successors). Thus, if there is no goal state to be found, the search to depth K will be identical to the search to depth K-1; then the program will terminate. 
c) In hill climbing, each hill climb is carried out from a random starting state until it reaches a solution or a local maximum. A random starting point is constructed by going through the list of vertices and accepting or rejecting each with probability 1/2. 

In doing the hill climbing part of the assignment, it's a good idea to write your code so there is a module where you can specify the starting state. That way, you can both replicate your code's behavior, which is useful in debugging, and compare it against my samples. However, the code that you submit should construct random starting states. CourseNana.COM

Output 

The program should print out to standard output:

• If a solution is found, the solution (just a sequence of vertices).
  If no solution is found, then "No solution found"
• If the "verbose" flag is set then a trace of the search sequence, as illustrated below.

Coding 

Programs will be accepted in Java or Python. Check with me about other languages.

Submit 

The source code for the two programs. Also a README file for how to compile and run your code if there is anything non-obvious about that. Do not assume that the grader will read instructions passed in comments in code. Definitely do not write our code in such a way that the grader has to edit it in order to compile or run it (e.g. hard code a path that exists on your own machine).

Grading 

Grading: 8 points for correctly running code. 2 points for well-written code. A programming assignment counts equally with a problem set in computing the overall grade. CourseNana.COM

Late policy 

Programming assignments are due at the beginning of class on the due date. I will accept assignments late with a penalty of 1 point out of 10 for each week late (fractions of a week are rounded up) up to 2 weeks late.

CourseNana.COM

Input for iterative deepening program, for graph 1. Target = 18 CourseNana.COM

18 V
A 3
B 5
C 6
D 10
E 13

A B
A C
B D
C E
D E

Output CourseNana.COM

Depth=1.
A Value=3.
B Value=5.
C Value=6.
D Value=10.
E Value=13.

Depth=2.
A Value=3.
A D Value=13.
A E Value=16.
B Value=5.
B C Value=11.
B E Value=18.

Found solution B E Value=18

The input for hill climbing is the same, except that you have to indicate the number of random restarts on the top line. E.g. 
CourseNana.COM

18 V 4

for a target of 18, with four random restarts, verbose output.

In verbose output for hill climbing, you should indicate the value of the Error function as well as the cost for a state, and show all the neighbors that are being tested. (The order in which you enumerate neighbors doesn't matter.) CourseNana.COM

Sample output CourseNana.COM

Randomly chosen start state: A
A Value=3. Error=15.
Neighbors: 
{} Value=0. Error=18.
A B Value=8. Error=13.
A C Value=9. Error=12.
A D Value=13. Error=5.
A E Value=16. Error=2. 

Move to A E. Value=16. Error=2.
Neighbors
E Value=13. Error=5.
A B E Value=21. Error=3.
A C E Value=22. Error=9.
A D E Value=26. Error=10.
A Value=3. Error=15.

Search failed

Randomly chosen start state B C D
B C D Value=21. Error=5.
Neighbors
A B C D Value=24. Error=11.
C D Value=16. Error=2.
B D  Value=15. Error=8.
B C. Value=11. Error=7.
B C D E. Value=34. Error=21.

Move to C D Value=16. Error=2.
Neighbors
A C D Value=19. Error=3.
B C D Value=21. Error=5.
D Value=10. Error=8.
C Value=6. Error=12.
C D E Value=29. Error=16.

Search failed

Randomly chosen start state A B C E. Value=27. Error=12.
Neighbors
B C E Value=24. Error=6.
A C E Value=22. Error=9.
A B E Value=21. Error=3.
A B C D E Value=37. Error=27.
A B C Vaue=14. Error=10

Move to A B E Value=21. Error=3
Neighbors
B E Value=18. Error=0

Found solution B E Value=18.