Announcements
Announcements
• Exam 3 Solutions Online
• Final Exam March 19th
Last Time
• NP-Hard/Complete Problems are as hard as
any other problems in NP.
• It is believed that this means that there are no
polynomial time algorithms for such
problems.
Dealing With NP-Completeness
(Ch 9)
• Backtracking/Branch and Bound
• Heuristic Search
• Approximation Algorithms
Identifying NP-Complete Problems
When given a problem to solve, it is important
to determine if it is NP-Complete.
If it is, then you have very good evidence that
you won’t find a polynomial time solution. So
you have an excuse for not having a better
algorithm.
Unfortunately, this doesn’t solve your original
problem. Even if it’s NP-Complete you still
need to solve it anyway.
Bad News
If your problem is NP-Hard/NP-Complete…
Then unless P=NP, there is no algorithm that
gives the exact answer to your problem on
all instances in polynomial time.
What are the
loopholes
here?
Prove P=NP? Approximation
Algorithms/
Local Search
Fixed Parameter
Tractability
See if you can
make further
assumptions.
See if you can
modify problem.
Efficient Search
Sudoku
Consider the logic puzzle Sudoku (or any similar
logic puzzle).
Fill a 9×9 grid of numbers with 1-9 so that:
• Each row has all numbers
• Each column has all numbers
• Each of the main 3×3 sub squares has all
numbers
• Some entries are pre-filled
NP-Hard
Suitable generalizations of Sudoku are NP-Hard.
• So in general, you cannot do much better than
brute force search.
• True brute force search would consider
981 ≈ 2·1077 possibilities.
• In practice, people can solve them while
waiting for the dentist.
– How?
Deductions
One way to progress is so make deductions.
• Use the rules to show that some square can
only be filled out in one way.
• Use that information to help fill out more
squares.
• Hopefully, you can keep going until the entire
problem is solved.
Example
Consider 3-SAT:
First clause implies x = True.
Plugging in and simplifying gives:
First clause implies y = True.
Plugging in and simplifying gives:
So we must have x = y = z = True, which is a
solution.
Getting Stuck
Deductions are very useful when you can make
them, but for hard problems, you will often
get stuck quickly and be unable to make more
deductions.
How do you get out?
Option 1: Stronger deductive rules.
Sudoku Inference Rules
More complicated deduction rules allow you to go further
without getting stuck. Common Sudoku rules include:
1) Find a square that only one number can fill.
2) Find a region with only one place for a given number.
3) Find a pair of squares in the same row that must contain two
numbers (which then cannot appear elsewhere in that row).
4) Find a rectangle whose corners must contain 2 copies of a
number. That number cannot appear elsewhere in those
rows/columns.
5) Find 3 rows & 3 columns whose intersections must contain 3
copies of a number. That number cannot appear elsewhere
in those rows and columns.
Still Stuck?
What if your complicated set of inference rules
is still not enough?
There is a general strategy that can always be
made to work.
Guess and check.
Guess and Check
• Make a guess for some entry.
• Try to solve the resulting puzzle (perhaps
doing more guessing).
• If you find a solution, great!
• If not, you have deduced that your original
guess was wrong.
Example
Guess x = True:
2nd clause: y = False
4th clause: z = False
Contradicts 1st clause.
So must have x = False:
1st clause: y = True
3rd clause: z = True
Contradicts 4th clause. No Solutions!
Backtracking
You can combine guess and check nicely with
deductions. In fact, a deduction can be
thought of as just guessing the wrong way to
fill things in and then concluding that it
doesn’t work.
This brings us to the general algorithm of
Backtracking. This takes some search problem
P with some space S that needs to be
searched.
Backtracking
Backtracking(P,S)
If you can deduce unsolveable
Return ‘no solutions’
Split S into parts S
1
,S
2
,…
For each i,
Run Backtracking(P,S
i
)
Return any solutions found
Splitting
How do you split S into parts?
• Pick variable xi and set xi = True, or xi = False
• Try all possible numbers in a square in Sudoku
• Try all possible edges in Hamiltonian Cycle
Which variable do we guess?
• Often helps to pick a variable that shows up a
lot. Then guessing it’s value will make later
deductions easier.
Runtime
These problems are still NP-Hard. Worst case,
backtracking will still take exponential time.
But it is usually much better than brute force.
SAT Solvers can use these ideas to solve
problems with hundreds of variables, many
many more than would be practical by brute
force.
Optimization Version
Backtracking works well for decision/search
problems (where a potential solution works or
doesn’t work), but not so well for optimization
problems (where many solutions work, but
you need to find the best one).
If most solutions work, how do you weed out
bad paths?
Branch & Bound
To get rid of bad paths do two things:
1) Keep track of the best solution you have
found so far.
2) Try to prove upper bounds on your
subproblems.
If an upper bound is smaller than your best
solution so far, it cannot contain the
optimum.
Example: Maximum Independent
Set
Set of size 3.
If we have
this point…
Can’t have
any of these.
Can’t have
both of
these
Set of size
at most 3.
Branch and Bound
BranchAndBound(Best,S)
If UpperBound(S) ≤ Best
Return ‘no improvement’
If S a full solution
Return value of S
Split S into S
1
,S
2
,…
For each S
i
New ← BranchAndBound(Best,S
i
)
Best = Max(New,Best)
Return Best
Local Search
Many optimization problems have a structure
where solutions “nearby” a good solution will
likely also be good.
This leads to a natural algorithmic idea:
• Find an OK solution
• Search nearby for better solutions
• Repeat
Local Search
LocalSearch(f)
\\ Try to maximize f(x)
x ← Random initial point
Try all y close to x
If f(y) > f(x) for some y
x ← y
Repeat
Else Return x