Describe reasonable heuristic algorithms or rules for the following problems. Fo

Question

Describe reasonable heuristic algorithms or rules for the following problems. For this problem, you do not need to give full implementation details: it is enough to describe the main idea behind the algorithm or rule in 1-2 sentences. Keep in mind that it is ok if a heuristic sometimes fails to find the best answer.

Consider a modified version of the Sat problem, in which the goal is to find a truth assignment for literals so that as many clauses as possible are satisfied. In other words, even if it is not possible to satisfy all clauses, your goal is to satisfy as many as you can. Design a reasonable heuristic algorithm for this problem.

Explanation / Answer

Solution:-

The SAT solving problem satisfy the clauses to find a truth assignment for literals. It a NP complete problem and no algorithm exists that solves the SAT solving problem in polynomial time, only algorithms with exponential worst-case complexity are known for it. Although there are some SAT solvers which uses the heuristic approach. We discuss here some SAT solvers rules to maximize the truth assignment.

The Davis–Putnam–Logemann Loveland (DPLL) algorithm is a complete, backtracking search algorithm for finding the truth assignment for satisfiability of propositional logic in conjunctive normal form. A modern approach of DPLL is conflict driven clause learning. The DPLL SAT solvers uses efficient backtracking to search the space of variables assignment to find the satisfiability. The conflict driven clause learning DPLL algorithm uses heuristic approach if backtracking. The steps are -

1) This algorithm iteratively makes assignment to free variables.

2) When algorithm encounters a bad assignment then it backtrack.

3) It backtracks to a previous iteration and chooses a different assignment of variables.

By these iterations as much as possible variables assignment done for the propositional logic satisfiability. It uses a Branching Heuristic to decide the next free variable assignment, the branching algorithm effectively makes choosing the variable assignment into a decision tree.

So these are some steps to solve a SAT solving problem by using a heuristic approach.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.