No-good

From Glossary

Jump to: navigation, search


A partial assignment of variables to values that does not lead to a solution. In other words, there does not exist a solution to the overall problem that satisfies all the assignments in the no good.

In a backtracking search to find a solution, each dead-end corresponds to a no good. However, where no-goods become useful is when they can be learned and added to the constraint problem as implied constraints that remove many dead-ends that would otherwise have to be searched over.

In particular, no-good learning and reasoning are very important for modern techniques to solve SAT problems.


Views
Personal tools