CS312 Lab 3-Heuristic Search Algorithms Solved

Task 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.

Report Format :

1. Brief description about the domain:
   1. State space
   2. Start node and goal node

   III. MOVEGENandGOALTESTalgorithm

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

Evaluation Criteria:

Correctness: 15 Report: 10 Code Quality: 5