Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 4
Текст из файла (страница 4)
A candidate for the presidencyof the United States may want to determine where to spend money buying campaignadvertising in order to maximize the chances of winning an election. An airline maywish to assign crews to flights in the least expensive way possible, making sure thateach flight is covered and that government regulations regarding crew scheduling aremet. An Internet service provider may wish to determine where to place additionalresources in order to serve its customers more effectively. All of these are examples ofproblems that can be solved using linear programming, which we shall study inChapter 29.While some of the details of these examples are beyond the scope of this book, we do giveunderlying techniques that apply to these problems and problem areas.
We also show how tosolve many concrete problems in this book, including the following:••••We are given a road map on which the distance between each pair of adjacentintersections is marked, and our goal is to determine the shortest route from oneintersection to another. The number of possible routes can be huge, even if wedisallow routes that cross over themselves.
How do we choose which of all possibleroutes is the shortest? Here, we model the road map (which is itself a model of theactual roads) as a graph (which we will meet in Chapter 10 and Appendix B), and wewish to find the shortest path from one vertex to another in the graph. We shall seehow to solve this problem efficiently in Chapter 24.We are given a sequence A1, A2, ..., An of n matrices, and we wish to determinetheir product A1 A2 An.
Because matrix multiplication is associative, there are severallegal multiplication orders. For example, if n = 4, we could perform the matrixmultiplications as if the product were parenthesized in any of the following orders:(A1(A2(A3A4))), (A1((A2A3)A4)), ((A1A2)(A3A4)), ((A1(A2A3))A4), or (((A1A2)A3)A4). Ifthese matrices are all square (and hence the same size), the multiplication order willnot affect how long the matrix multiplications take. If, however, these matrices are ofdiffering sizes (yet their sizes are compatible for matrix multiplication), then themultiplication order can make a very big difference.
The number of possiblemultiplication orders is exponential in n, and so trying all possible orders may take avery long time. We shall see in Chapter 15 how to use a general technique known asdynamic programming to solve this problem much more efficiently.We are given an equation ax ≡ b (mod n), where a, b, and n are integers, and we wishto find all the integers x, modulo n, that satisfy the equation.
There may be zero, one,or more than one such solution. We can simply try x = 0, 1, ..., n - 1 in order, butChapter 31 shows a more efficient method.We are given n points in the plane, and we wish to find the convex hull of thesepoints. The convex hull is the smallest convex polygon containing the points.Intuitively, we can think of each point as being represented by a nail sticking out froma board. The convex hull would be represented by a tight rubber band that surroundsall the nails.
Each nail around which the rubber band makes a turn is a vertex of theconvex hull. (See Figure 33.6 on page 948 for an example.) Any of the 2n subsets ofthe points might be the vertices of the convex hull. Knowing which points are verticesof the convex hull is not quite enough, either, since we also need to know the order inwhich they appear. There are many choices, therefore, for the vertices of the convexhull. Chapter 33 gives two good methods for finding the convex hull.These lists are far from exhaustive (as you again have probably surmised from this book'sheft), but exhibit two characteristics that are common to many interesting algorithms.1. There are many candidate solutions, most of which are not what we want.
Finding onethat we do want can present quite a challenge.2. There are practical applications. Of the problems in the above list, shortest pathsprovides the easiest examples. A transportation firm, such as a trucking or railroadcompany, has a financial interest in finding shortest paths through a road or railnetwork because taking shorter paths results in lower labor and fuel costs. Or a routingnode on the Internet may need to find the shortest path through the network in order toroute a message quickly.Data structuresThis book also contains several data structures. A data structure is a way to store andorganize data in order to facilitate access and modifications. No single data structure workswell for all purposes, and so it is important to know the strengths and limitations of several ofthem.TechniqueAlthough you can use this book as a "cookbook" for algorithms, you may someday encountera problem for which you cannot readily find a published algorithm (many of the exercises andproblems in this book, for example!).
This book will teach you techniques of algorithm designand analysis so that you can develop algorithms on your own, show that they give the correctanswer, and understand their efficiency.Hard problemsMost of this book is about efficient algorithms. Our usual measure of efficiency is speed, i.e.,how long an algorithm takes to produce its result. There are some problems, however, forwhich no efficient solution is known.
Chapter 34 studies an interesting subset of theseproblems, which are known as NP-complete.Why are NP-complete problems interesting? First, although no efficient algorithm for an NPcomplete problem has ever been found, nobody has ever proven that an efficient algorithm forone cannot exist. In other words, it is unknown whether or not efficient algorithms exist forNP-complete problems. Second, the set of NP-complete problems has the remarkable propertythat if an efficient algorithm exists for any one of them, then efficient algorithms exist for allof them.
This relationship among the NP-complete problems makes the lack of efficientsolutions all the more tantalizing. Third, several NP-complete problems are similar, but notidentical, to problems for which we do know of efficient algorithms. A small change to theproblem statement can cause a big change to the efficiency of the best known algorithm.It is valuable to know about NP-complete problems because some of them arise surprisinglyoften in real applications. If you are called upon to produce an efficient algorithm for an NPcomplete problem, you are likely to spend a lot of time in a fruitless search. If you can showthat the problem is NP-complete, you can instead spend your time developing an efficientalgorithm that gives a good, but not the best possible, solution.As a concrete example, consider a trucking company with a central warehouse.
Each day, itloads up the truck at the warehouse and sends it around to several locations to makedeliveries. At the end of the day, the truck must end up back at the warehouse so that it isready to be loaded for the next day. To reduce costs, the company wants to select an order ofdelivery stops that yields the lowest overall distance traveled by the truck. This problem is thewell-known "traveling-salesman problem," and it is NP-complete. It has no known efficientalgorithm. Under certain assumptions, however, there are efficient algorithms that give anoverall distance that is not too far above the smallest possible.
Chapter 35 discusses such"approximation algorithms."Exercises 1.1-1Give a real-world example in which one of the following computational problems appears:sorting, determining the best order for multiplying matrices, or finding the convex hull.Exercises 1.1-2Other than speed, what other measures of efficiency might one use in a real-world setting?Exercises 1.1-3Select a data structure that you have seen previously, and discuss its strengths and limitations.Exercises 1.1-4How are the shortest-path and traveling-salesman problems given above similar? How arethey different?Exercises 1.1-5Come up with a real-world problem in which only the best solution will do.
Then come upwith one in which a solution that is "approximately" the best is good enough.1.2 Algorithms as a technologySuppose computers were infinitely fast and computer memory was free. Would you have anyreason to study algorithms? The answer is yes, if for no other reason than that you would stilllike to demonstrate that your solution method terminates and does so with the correct answer.If computers were infinitely fast, any correct method for solving a problem would do.
Youwould probably want your implementation to be within the bounds of good softwareengineering practice (i.e., well designed and documented), but you would most often usewhichever method was the easiest to implement.Of course, computers may be fast, but they are not infinitely fast. And memory may be cheap,but it is not free. Computing time is therefore a bounded resource, and so is space in memory.These resources should be used wisely, and algorithms that are efficient in terms of time orspace will help you do so.EfficiencyAlgorithms devised to solve the same problem often differ dramatically in their efficiency.These differences can be much more significant than differences due to hardware andsoftware.As an example, in Chapter 2, we will see two algorithms for sorting.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
