Thuật toán Algorithms (Phần 55)
lượt xem 4
download
Thuật toán Algorithms (Phần 55)
Tham khảo tài liệu 'thuật toán algorithms (phần 55)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Thuật toán Algorithms (Phần 55)
 WCOMPLETE PROBLEMS running the given program on the given input, so it produces a solution to an instance of the given problem. Further details of this proof are well beyond the scope of this book. Fortunately, only one such proof is really necessary: it is much easier to use reduction to prove NPcompleteness. Some NP Complete Problems As mentioned above, literally thousands of diverse problems are known to be NPcomplete. In this section, we list a few for purposes of illustrating the wide range of problems that have been studied. Of course, the list begins with satisfiability and includes traveling salesman and Hamilton cycle, as well as longest path. The following additional problems are representative: PARTITION: Given a set of integers, can they be divided into two sets whose sum is equal? INTEGER LINEAR PROGRAMMING: Given a linear program, is there a solution in integers? MULTIPROCESSOR SCHEDULING: Given a deadline and a set of tasks of varying length to be performed on two identical processors can the tasks be arranged so that the deadline is met? VERTEX COVER: Given a graph and an integer N, is there a set of less than N vertices which touches all the edges? These and many related problems have important natural practical applica tions, and there has been strong motivation for some time to find good algo rithms to solve them. The fact that no good algorithm has been found for any of these problems is surely strong evidence that P # NP, and most research ers certainly believe this to be the case. (On the other hand, the fact that no one has been able to prove that any of these problem do not belong to P could be construed to comprise a similar body of circumstantial evidence on the other side.) Whether or not P = NP, the practical fact is that we have at present no algorithms that are guaranteed to solve any of the NPcomplete problems efficiently. As indicated in the previous chapter, several techniques have been devel oped to cope with this situation, since some sort of solution to these various problems must be found in practice. One approach is to change the problem and find an “approximation” algorithm that finds not the best solution but a solution that is guaranteed to be close to the best. (Unfortunately, this is sometimes not sufficient to fend off NPcompleteness.) Another approach is to rely on “averagetime” performance and develop an algorithm that finds the solution in some cases, but doesn’t necessarily work in all cases. That is, while it may not be possible to find an algorithm that is guaranteed to work well on all instances of a problem, it may well be possible to solve efficiently virtually all of the instances that arise in practice. A third approach is to work
 534 CHAPTER 40 with “efficient” exponential algorithms, using the backtracking techniques described in the previous chapter. Finally, there is quite a large gap between polynomial and exponential time which is not addressed by the theory. What about an algorithm that runs in time proportional to Nl”sN or ‘2m? All of the application areas that we’ve studied in this book are touched by NPcompleteness: there are NPcomplete problems in numerical applica tions, in sorting and searching, in string processing, in geometry, and in graph processing. The most important practical contribution of the theory of NP completeness is that it provides a mechanism to discover whether a new prob lem from any of these diverse areas is “easy” or “hard.” If one can find an efficient algorithm to solve a new problem, then there is no difficulty. If not, a proof that the problem is NPcomplete at least gives the information that the development of an efficient algorithm would be a stunning achievement (and suggests that a different approach should perhaps be tried). The scores of efficient algorithms that we’ve examined in this book are testimony that we have learned a great deal about efficient computational methods since Euclid, but the theory of NPcompleteness shows that, indeed, we still have a great deal to learn.
 535 Exercises 1. Write a program to find the longest simple path from x to y in a given weighted graph. 2 . Could there be an algorithm which solves an NPcomplete problem in an average time of N log N, if P # NP? Explain your answer. 3. Give a nondeterministic polynomialtime algorithm for solving the PARTI TION problem. 4 . Is there an immediate polynomialtime reduction from the traveling sales man problem on graphs to the Euclidean traveling salesman problem, or vice versa? 5 . What would be the significance of a program that could solve the traveling salesman problem in time proportional to l.lN? 6 . Is the logical formula given in the text satisfiable? 7. Could one of the “algorithm machines” with full parallelism be used to solve an NPcomplete problem in polynomial time, if P # NP? Explain your answer. 8. How does the problem “compute the exact value of 2N” fit into the P NP classification scheme? 9. Prove that the problem of finding a Hamilton cycle in a directed graph is NPcomplete, using the NPcompleteness of the Hamilton cycle problem for undirected graphs. 10. Suppose that two problems are known to be NPcomplete. Does this imply that there is a polynomialtime reduction from one to the other, if P#NP?
 536 SOURCES for Advanced Topics Each of the topics covered in this section is the subject of volumes of reference material. From our introductory treatment, the reader seeking more information should anticipate engaging in serious study; we’ll only be able to indicate some basic references here. The perfect shuffle machine of Chapter 35 is described in the 1968 paper by Stone, which covers many other applications. One place to look for more information on systolic arrays is the chapter by Kung and Leiserson in Mead and Conway’s book on VLSI. A good reference for applications and implemen tation of the FFT is the book by Rabiner and Gold. Further information on dynamic programming (and topics from other chapters) may be found in the book by Hu. Our treatment of linear programming in Chapter 38 is based on the excellent treatment in the book by Papadimitriou and Steiglitz, where all the intuitive arguments are backed up by full mathematical proofs. Further information on exhaustive search techniques may be found in the books by Wells and by Reingold, Nievergelt, and Deo. Finally, the reader interested in more information on NPcompleteness may consult the survey article by Lewis and Papadimitriou and the book by Garey and Johnson, which has a full description of various types of NPcompleteness and a categorized listing of hundreds of NPcomplete problems. M. R. Garey and D. S. Johnson, Computers and Intractability: a Guide to the Theory of NPCompleteness, Freeman, San Francisco, CA, 1979. T. C. Hu, Combinatorial Algorithms, AddisonWesley, Reading, MA, 1982. H. R. Lewis and C. H. Papadimitriou, “The efficiency of algorithms,” Scientific American, 238, 1 (1978). C. A. Mead and L. C. Conway, Introduction to VLSI Design, AddisonWesley, Reading, MA, 1980. C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, PrenticeHall, Englewood Cliffs, NJ, 1982. E. M. Reingold, J. Nievergelt, and N. Deo, Combinatorial Algorithms: Theory and Practice, PrenticeHall, Englewood Cliffs, NJ, 1982. L. R. Rabiner and B. Gold, Digital Signal Processing, PrenticeHall, Englewood Cliffs, NJ, 1974. H. S. Stone, “Parallel processing with the perfect shuffle,” IEEE Transactions on Computing, C20, 2 (February, 1971). M. B. Wells, Elements of Combinatorial Computing, Pergaman Press, Oxford, 1971.
 Index Abacus, 528. Approximation algorithms, 522 Abstract data structures, 30, 88, 524, 533. 128, 136. Arbitrary numbers, 33. adapt (integration, adaptive Arithmetic, 2330. quadrature), 85. Arrays, 24. Additive congruential generator Articulation points, 390392, (randomint), 3840. 430. add (polynomials represented Artificial (slack) variables, 503, with linked lists), 27. 509. add (sparse polynomials), 28. Attributes, 335. Adjacency lists, 3788381, 3822 Average case, 1213. 383, 391392, 410411, 435. AVL trees, 198. Adjacency matrix, 3777378, 384, 410411, 425, 435, 493, 515. Btrees, 228231, 237. Adjacency structure; see ad Backtracking, 517522. jacency lists. Backward substitution, 60, 62 adjlist (graph input, adjacency (substitute), 64. lists), 379. Balanced multiway merging, adjmatrix (graph input, ad 1566161. jacency matrix), 378. Balanced trees, 187199, 237, Adleman, L., 301, 304. 355. Aho, A. V., 304. Basis variables, 504. Algorithm machines, 4577469. Batcher, K. E., 4633465. Allnearestneighbors, 366. Bayer, R., 228. Allpairs shortest paths, 4922494. Bentley, J. L., 370. Analysis of algorithms, 1216, 19. Biconnectivity, 390392, 429. 537
 538 Binary search, 175177, 176 Caesar cipher, 297. (binarysearch), 336. Catalan numbers, 487. Binary search trees, 169, 178% Chisquare (x2) test (c&square), 185, 204, 210, 336, 343346, 4142. 353, 3566359. Ciphers, 297300. array representation, 1844185. Caesar, 297. indirect representation, 184 Vernam, 299. 185, 353. Vigenere, 298. optimal, 489492. product, 300. standard representation, 178 Ciphertext, 297. 179. Clancy, M., 19. weighted internal path length, Closestpair problem, 362366, 490. 368. Binary trees, 179, 237. Closestpoint problems, 361368, Binomial queues, 167. 370. Bipartite graphs, 444447. Closure, 258, 261. Bitonic merge, 463465. Clustering, 207. bits, 116, 118, 122, 214, 215, 221, Comer, D., 237. 222. Compareexchange, 93, 460465. Bland, R. G., 507. Compilers, 247, 269, 276279, Bland’s method (for cycle 304. avoidance in simplex), 509. Complete binary tree, 130. Borodin, A,, 88. Complete graphs, 376. Bottomup parsing, 275276. Complex numbers, 473478. Boyer, R. S., 242, 304. Complex roots of unity, 473477. BoyerMoore string searching, 250251. Computational accuracy, 61, 63, 86, 504. Branchandbound, 519520. Concatenation, 258, 261. Breadthfirst search, 395, 397 398, 439. Connected components, 375. Brown, M. R., 167. Connected graph, 375. brutesearch (bruteforce string Connectivity, 389405, 454. searching), 243. Conqueranddivide, 152. b&delete (binary search tree dele Constant running time, 14. tion), 185, 355. Constraints, 498. bstinsert (binary search tree in Contextfree grammars, 270272. sertion), 184, 353, 355. Contextrsensitive grammars, 272. b&range (onedimensional range Convex hull, 321. search), 337, 355. Convex hull algorithms, 321333, bubblesort, 99. 368, 370.
 INDEX 539 divideandconquer, 368. heap, 129140. FloydEddy method, 331332. indirect binary search tree, Graham scan, 326330, 329 184185. (grahamscan), 332. indirect heap, 138139. hull selection, 331332. linked list, 2728, 202203, package wrapping, 323326, 379. 325 (wrap), 332. priority queue, 127140. Convex polygons, 321. queue, 264, 395. Convexity, 321. redblack tree, 192199. Conway, L. C., 536. sorted list, 129. Cook, S. A., 242, 532. stack, 109110, 264, 394, 428, Cook’s theorem (satisfiability is 429. NPcomplete), 532533. string, 241. Cooper, D., 19. topdown 234 tree, 187199. Counting, 455. unordered list, 129. Cross edges, 423, 430. Database, 226, 237, 335. Cryptanalysis, 295296. Decryption, 297, 301. Cryptography, 295296. Deletion in binary search trees, Cryptology, 295302, 304. 183184. Cryptosystem, 296. Deletion in hash tables, 208. Cryptovariables, 299. Dense graphs, 376, 378, 397398, Cubic running time, 15. 411, 413, 415417. Curve fitting, 6776. densepfs (priority graph traver Cycle, 375, 384. sal), 416, 439440. Cycling in the simplex method, Deo, N., 536. 506507, 509. Depthfirst search, 371, 381387, 391395, 397399, 422423, Dags (directed acyclic graphs), 428430, 454, 515. 426428. Depthfirst search forest, 382, Data fitting, 6776. 384, 394, 422423. Data structures. Derivation, 270. abstract, 30, 128, 136. Deterministic algorithm, 528. adjacency lists, 378381. dfs (recursive depthfirst search), adjacency matrix, 377378. 382385. adjacency structure, 378381 Dictionaries, 171. array, 24. Diffie, W., 301. Btree, 228231, 237. Digital search trees, 213216. binary search tree, 178185. digitalinsert, 215. deque, 263267. digitalsearch, 214.
 540 Dijkstra’s algorithm (for finding forward, 437. the shortest path), 415. negative weight, 494. Dijkstra, E. W., 410, 415, 454. up, 423, 430. Directed acyclic graphs (dags), Edmonds, J., 439440. 426428. eliminate (forward elimination), Directed cycle, 428. 62. Directed graphs, 376, 380, 421 Encryption, 297, 301. 430. eof, 9. Directed path, 423. Equal keys, 172, 177, 193, 204, Directory, 233. 214, 227228, 234. Discrete mathematics, 19. Escape sequence, 286. Disk searching, 225235. Euclid’s algorithm (for finding Distribution counting, 99101, the gcd), 1011, 19, 302. 116, 122123. Divideandconquer, 48, 51, 104, Euclidean minimum spanning 152, 175, 362, 474, 477480, tree, 417. 483. Euclidean shortest path problem, Divideandconquer recurrence, 418. 51, 108, 149, 475, 363. Euclidean traveling salesman Dot product, 74. problem, 522524. Double buffering, 161. eval (fast Fourier transform), 479. Double hashing, 207210. eval (spline evaluation), 72. Double rotation, 198. Even, S., 454. Down edges, 423. Exception dictionary, 210. downheap (topdown heap Exhaustive graph traversal repair), 134. (visit), 515. Drawing lines, 310 (draw), 311. Exhaustive search, 513524, 536. Dual of Voronoi diagram, 367 Exponential running time, 15, 368. 513, 520, 528, 534. Dummy node; see z. Exponentiation, 4647, 301. Duplicate keys; see equal keys. expression (topdown compiler), Dynamic programming, 483494, 277. 536. expression (topdown parser), 273. Eddy, W. F., 331, 370. Extendible hashing, 231235, Edges, 374. 237. backward, 437. External nodes, 180, 230, 289, capacities, 435. 490. cross, 423, 430. External searching, 225235. down, 423. External sorting, 155165.
 INDEX 541 factor (topdown compiler), 278. Gaussian elimination, 5765, 60 factor (topdown parser), 274. (gauss), 71, 76, 504, 508. Fagin, R., 231, 237. gcd (greatest common divisor, fastfind (unionfind with com Euclid’s algorithm), 11, 12. pression and balancing), 403, General regularexpression pat 411. tern matching, 265 (match), Fast Fourier transform, 465, 471 279. 480, 479 (eval), 536. Geometric algorithms, 307370. Feasible basis, 509510. closest pair, 362366. File compression, 283293. convex hull, 321333, 368. Huffman encoding, 286293. elementary, 307319. runlength encoding, 284286. grid method, 339342. variablelength encoding, 286 inside polygon test, 316318. 293. intersection, 349359. Find, 399. line drawing, 310311. find (unionfind, quick union), range searching, 336347. 401. simple closed path, 313315. findinit (fastfind initialization), 403, 411. 2Dtrees, 343346. Finitestate machine. Gerrymandering, 307. deterministic, 248, 259. Gold, B., 536. nondeterministic, 259267. Gosper, R. W., 242. Flow, 435. Graham, R. L., 326, 370. Floyd, R. W., 331. Graham scan, 326330, 329 Ford, L. R., 435. (grahamscan). Forecasting, 161. Grammars, 270272. Forest, 375. Graph algorithms, 373454. Forsythe, G. E., 88. allpairs shortest paths, 492 Forward elimination, 59, 6062, 494. 62 (eliminate), 64. biconnectivity, 390392. Cnode, 188. bipartite matching, 444447. Fourier transform, 471480. breadthfirst search, 395. Fredkin, E., 216. connected components, 384. Friedman, J. H., 370. cycle testing, 384. Fringe vertices, 393, 410. depthfirst search, 381387. Fulkerson, D. R., 435. elementary, 373387. exhaustive search for cycles, Garey, M. R., 536. 515520. GaussJordan method, 63, 65, maximum tlow in a network, 508. 439440.
 542 minimum spanning tree, 408 Hamilton cycle problem, 514 413. 520, 531532. priority traversal, 395397. Hash functions, 202. shortest path, 413415. Hashing, 201210, 234. stable marriage, 447452. double hashing, 207210. strongly connected com initialization for open address ponents, 428430. ing, 205 (ha&initialize). topological sorting, 426428. linear probing, 2055207, 205 transitive closure, 423426. (hashinsert). unionfind, 398405. open addressing, 205210. Graph input, adjacency lists, 379 separate chaining, 202204. (adjlist). Head node, 1744175, 180, 181, Graph input, adjacency matrix, 199, 203204, 214, 222, 352 378 (adjmatrix). 353. Graph isomorphism, 387. Heaps, 89, 129140, 289290, Graph traversal, 393398. 397. Graphs, 492494. Heap algorithms, 129140. adjacency list, 416. change, 135. adjacency matrix, 416. construct, 136137. bipartite, 444447. downheap, 134, 136. complete, 376. insert, 132, 135. connected, 375. join, 139140. connectivity, 389405. pqconstruct, 138. dense, 376. pqdownheap, 139, 289290. directed, 376, 421430, 421& pqinsert, 139, 158, 160. 430. pqremove, 139, 290. directed acyclic, 426428. pqreplace, 159, 160. representation, 376381, 416, remove, 134, 135. 421, 435. replace, 135. sparse, 376. upheap, 132. traversal, 393398. Heap condition, 130. undirected, 376. Heapsort, 135137, 136 weighted, 376. (heapsort). Greatest common divisor (gcd), Hellman, M. E., 301. 912. Hoare, C. A. R., 103, 167. Greatest increment method, 507. Hoey, D., 349, 370. Grid method, 339342, 341 Holt, R., 19. g7ngegrid), 342 (gridrange), Horner’s rule, 4546. Hu, T. C., 536. Guibas, L., 237. Huffman, D. A., 304.
CÓ THỂ BẠN MUỐN DOWNLOAD

Thuật toán Algorithms (Phần 1)
10 p  69  18

Thuật toán Algorithms (Phần 16)
10 p  59  15

Thuật toán Algorithms (Phần 2)
10 p  52  10

Thuật toán Algorithms (Phần 8)
10 p  55  9

Thuật toán Algorithms (Phần 11)
10 p  57  9

Thuật toán Algorithms (Phần 3)
10 p  59  8

Thuật toán Algorithms (Phần 12)
10 p  50  8

Thuật toán Algorithms (Phần 4)
10 p  48  7

Thuật toán Algorithms (Phần 13)
10 p  50  7

Thuật toán Algorithms (Phần 6)
10 p  57  7

Thuật toán Algorithms (Phần 10)
10 p  46  6

Thuật toán Algorithms (Phần 9)
10 p  52  6

Thuật toán Algorithms (Phần 7)
10 p  42  6

Thuật toán Algorithms (Phần 5)
10 p  55  6

Thuật toán Algorithms (Phần 14)
10 p  31  5

Thuật toán Algorithms (Phần 15)
10 p  36  4

Thuật toán Algorithms (Phần 17)
10 p  33  4