tailieunhanh - Thuật toán Algorithms (Phần 53)

Tham khảo tài liệu 'thuật toán algorithms (phần 53)', 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ả | 39. Exhaustive Search Some problems involve searching through a vast number of potential solutions to find an answer and simply do not seem to be amenable to solution by efficient algorithms. In this chapter we ll examine some characteristics of problems of this sort and some techniques which have proven to be useful for solving them. To begin we should reorient our thinking somewhat as to exactly what constitutes an efficient algorithm. For most of the applications that we have discussed we have become conditioned to think that an algorithm must be linear or run in time proportional to something like or to be considered efficient. We ve generally considered quadratic algorithms to be bad and cubic algorithms to be awful. But for the problems that we ll consider in this and the next chapter any computer scientist would be absolutely delighted to know a cubic algorithm. In fact even an algorithm would be pleasing from a theoretical standpoint because these problems are believed to require exponential time. Suppose that we have an algorithm that takes time proportional to If we were to have a computer 1000 times faster than the fastest supercomputer available today then we could perhaps solve a problem for N 50 in an hour s time under the most generous assumptions about the simplicity of the algorithm. But in two hour s time we could only do N 51 and even in a year s time we could only get to N 59. And even if a new computer were to be developed with a million times the speed and we were to have a million such computers available we couldn t get to N 100 in a year s time. Realistically we have to settle for N on the order of 25 or 30. A more efficient algorithm in this situation may be one that could solve a problem for N 100 with a realistic amount of time and money. The most famous problem of this type is the traveling salesman problem given a set of N cities find the shortest route connecting them all with no 513 514 CHAPTER 39 city visited twice. This problem .