## States Of Variables

• State is assignment of values to variables under constraints

• Three kinds:

• Constraint Satisfaction Problem: Find an assignment that satisfies constraints

• Optimization Problem: Find an assignment that optimizes some objective function

• Constraint Optimization Problem: Find assignment that optimizes under constraints

## CNF 3-SAT

• Variables are "atoms" in logical formula; values are true or false

• Formula is in Conjunctive Normal Form with at most 3 variables per clause: e.g.

(A or not B or C) and (not A and B or C) and (A or B or C)

• Constraint is that the formula be true: every clause must have at least 1 true literal

• For this formula take A=f, B=f, C=t
• In general, problem is NP-complete

## Complete Search For CSPs (3-SAT)

• Let's add a third "unassigned" state for variables. This extends the state space to include partial assignments

• Algorithm (DPLL):

• Try assigning A=t. If the formula has no false clauses, try recursively solving the remaining variables

• Try assigning A=f. If the formula has no false clauses, try recursively solving the remaining variables

• If no solution has been found, return unsat

• This is breadth-first search to a fixed depth (number of variables)

## Variable Ordering

• Free choice at each state of which variable to solve for next

• Heuristics are probably helpful here:

• Branch on variables that have large number of occurrences (to fail quickly)

• Branch on variables in short clauses (to fail quickly)

• Generally "most constrained first"

## Value Ordering

• Free choice at each state of what order to try values for chosen variable

• Heuristics are probably helpful here:

• Try value that satisfies most clauses (to succeed quickly)

• Try value that produces most short clauses (to make problem easy to solve) [Crawford et al]

• Generally "least constraining first"

## Local Search for CSPs (3-SAT)

• Neighbors are change of value of some variable: "flips" in 3-SAT

• Heuristic: Number of satisfied clauses (more is better)

• Use "noise moves" and "restarts" as usual to speed up search

## Optimization for CSPs (HW Problem)

• Same basic framework: use complete or local search

• Complete search can find an optimal solution — in principle

• Heuristics will involve the scoring of a partial or total solution — greed is good