Artificial Intelligence Assignment 3

CS 312: Artificial Intelligence
Assignment 3
Heuristic Search Algorithms
Domain: Uniform Random-4-SAT is a family of SAT problems distributions obtained by randomly
generating 3-CNF formulae in the following way: For an instance with n=4 variables and k=5 clauses,
each of the k clauses is constructed from 3 literals which are randomly drawn from the 2n possible literals
(the n variables and their negations) such that each possible literal is selected with the same probability of
1/2n. Clauses are not accepted for the construction of the problem instance if they contain multiple copies
of the same literal or if they are tautological (i.e., they contain a variable and its negation as a literal). Each
choice of n and k thus induces a distribution of Random-4-SAT instances. Uniform Random-4-SAT is the
union of these distributions over all n and k.
Firstly generate your formula for N = 4 and k = 5. Please write your clauses in the text file and each clause
should be written in a different line of the text file. Then input the formula to three algorithms.
Implement:
1. Variable neighborhood descent : Modify Hill-Climbing Search to switch to a denser
neighborhood function when stuck at a local optimum.
2. Beam Search : Code for different beam lengths
3. Tabu Search : Implement tabu search and find an optimum tabu tenure value for the domain.
Evaluation Criteria: (Total : 50 Points)
Correctness: 15
Report: 10
Code Quality: 5
NOTE:
1. Due date for Assignment is 11:59 PM 9 Jan 2022.
2. Submit the following files named with your group number.
a. Code: <group_number>.py
b. Input file if there (input.txt)
c. Report: <group_number>.pdf
d. Readme.txt ( How to execute your program)
3. Mode of submission is moodle.
4. We will run a plagiarism check for all the submissions, If found copied, 0% score will be
awarded.
5. Penalty of 10% will be issued per day if the deadline is not met.
Report Format :
1. Brief description about the domain:
a. State space
b. Start node and goal node
c. MOVEGEN and GOALTEST algorithm
2. Heuristic functions considered
3. Beam search analysis for different beam lengths
4. Tabu search for different values of tabu tenure
5. Comparison of Variable neighborhood descent, Beam Search, Tabu Search: Nodes explored by
each.