Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tham khảo sách 'advances in greedy algorithms_2', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 16 Greedy Like Algorithms for the Traveling Salesman and Multidimensional Assignment Problems Gregory Gutin and Daniel Karapetyan Royal Holloway University of London United Kingdom 1. Introduction Majority of chapters of this book show usefulness of greedy like algorithms for solving various combinatorial optimization problems. The aim of this chapter is to warn the reader that not always a greedy like approach is a good option and in certain cases it is a very bad option being sometimes among the worst possible options. Our message is not a discouragement from using greedy like algorithms altogether we think that for every combinatorial optimization problem of importance researchers and practitioners should simply investigate the appropriateness of greedy like algorithms and the existence of better alternatives to them considering both quality of solution and running time . In many cases especially when the running time must be very short the conclusion may still be that the most practical of known approaches is a greedy like algorithm. The Traveling Salesman and Multidimensional Assignment Problems are optimization problems for which greedy like approaches are usually not very successful. We demonstrate this by providing both theoretical and experimental results on greedy like algorithms as well as on some other algorithms that produce in theory and or in experiments much better results without spending significantly more time. There are some general theoretical results that indicate that there are in fact many combinatorial optimization problems for which greedy like algorithms are not the best option even among fast construction heuristics see e.g. 3 5 17 . We will not consider these general results in order to avoid most mathematical details that are not necessary for understanding the results of this chapter. For this reason we will not give proofs here apart from two simple proofs that of Theorem 8 which shows that some instances on which the greedy .
