EXERCISES
8.6
A postman needs to deliver to 20 homes. He needs to find the
shortest route that goes to all 20 homes. Is this an NP-complete
problem?
8.7
Finding the largest clique in a set of people (a
clique
is a set of people
who all know each other). Is this an NP-complete problem?
8.8
You’re making a map of the USA, and you need to color adjacent
states with different colors. You have to find the minimum number
of colors you need so that no two adjacent states are the same color.
Is this an NP-complete problem?
160
Chapter 8
I
Greedy algorithms
Recap
• Greedy algorithms optimize locally, hoping to end up with a global
optimum.
• NP-complete problems have no known fast solution.
• If you have an NP-complete problem, your best bet is to use an
approximation algorithm.
• Greedy algorithms are easy to write and fast to run, so they make
good approximation algorithms.
161
In this chapter
• You learn dynamic programming, a
technique to solve a hard problem by
breaking it up into subproblems and
solving those subproblems first.
• Using examples, you learn to how to come up
with a dynamic programming solution to a
new problem.
dynamic
programming
9
The knapsack problem
Let’s revisit the knapsack problem from chapter 8.
You’re a thief with a knapsack that can carry 4 lb
of goods.
162
Chapter 9
Dostları ilə paylaş: |
