## CSPs

## 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)

Start with a random assignment of values to variables

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