Python Algorithms, 2nd Edition.pdf

(5079 KB) Pobierz
www.it-ebooks.info
For your convenience Apress has placed some of the front
matter material after the index. Please use the Bookmarks
and Contents at a Glance links to access them.
www.it-ebooks.info
Contents at a Glance
About the Author �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½
xv
About the Technical Reviewer �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½
xvii
Acknowledgments �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½
xix
Preface �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½
xxi
Chapter 1
:
Introduction �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½1
Chapter 2
:
The Basics �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½9
Chapter 3
:
Counting 101 �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½43
Chapter 4
:
Induction and Recursion �½�½�½ and Reduction �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½67
Chapter 5
:
Traversal: The Skeleton Key of Algorithmics �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½93
Chapter 6
:
Divide, Combine, and Conquer �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½115
Chapter 7
:
Greed Is Good? Prove It! �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½139
Chapter 8
:
Tangled Dependencies and Memoization�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½163
Chapter 9
:
From A to B with Edsger and Friends �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½187
Chapter 10
:
Matchings, Cuts, and Flows �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½209
Chapter 11
:
Hard Problems and (Limited) Sloppiness �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½227
v
www.it-ebooks.info
Contents at a GlanCe
Appendix A
:
Pedal to the Metal: Accelerating Python �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½255
Appendix B
:
List of Problems and Algorithms�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½259
Appendix C
:
Graph Terminology �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½267
Appendix D
:
Hints for Exercises �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½273
Index �½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½�½289
vi
www.it-ebooks.info
Chapter 1
Introduction
1.
2.
3.
Write down the problem.
Think real hard.
Write down the solution.
— “The Feynman Algorithm”
as described by Murray Gell-Mann
Consider the following problem: You are to visit all the cities, towns, and villages of, say, Sweden and then return
to your starting point. This might take a while (there are 24,978 locations to visit, after all), so you want to minimize
your route. You plan on visiting each location exactly once, following the shortest route possible. As a programmer,
you certainly don’t want to plot the route by hand. Rather, you try to write some code that will plan your trip for you.
For some reason, however, you can’t seem to get it right. A straightforward program works well for a smaller number
of towns and cities but seems to run forever on the actual problem, and improving the program turns out to be
surprisingly hard. How come?
Actually, in 2004, a team of five researchers
1
found such a tour of Sweden, after a number of other research teams
had tried and failed. The five-man team used cutting-edge software with lots of clever optimizations and tricks of
the trade, running on a cluster of 96 Xeon 2.6GHz workstations. Their software ran from March 2003 until May 2004,
before it finally printed out the optimal solution. Taking various interruptions into account, the team estimated that
the total CPU time spent was about
85 years!
Consider a similar problem: You want to get from Kashgar, in the westernmost region of China, to Ningbo, on the
east coast, following the shortest route possible.
2
Now, China has 3,583,715 km of roadways and 77,834 km of railways,
with millions of intersections to consider and a virtually unfathomable number of possible routes to follow. It might
seem that this problem is related to the previous one, yet this
shortest path
problem is one solved routinely, with no
appreciable delay, by GPS software and online map services. If you give those two cities to your favorite map service,
you should get the shortest route in mere moments. What’s going on here?
You will learn more about both of these problems later in the book; the first one is called the
traveling salesman
(or
salesrep) problem
and is covered in Chapter 11, while so-called shortest path problems are primarily dealt with
in Chapter 9. I also hope you will gain a rather deep insight into why one problem seems like such a hard nut to
crack while the other admits several well-known, efficient solutions. More importantly, you will learn something
about how to deal with algorithmic and computational problems in general, either solving them efficiently, using
one of the several techniques and algorithms you encounter in this book, or showing that they are too hard and that
approximate solutions may be all you can hope for. This chapter briefly describes what the book is about—what you
can expect and what is expected of you. It also outlines the specific contents of the various chapters to come in case
you want to skip around.
David Applegate, Robert Bixby, Vašek Chvátal, William Cook, and Keld Helsgaun
Let’s assume that flying isn’t an option.
1
2
1
www.it-ebooks.info
Zgłoś jeśli naruszono regulamin