Combinatorial Heuristic Algorithms with FORTRAN

در سال‌های اخیر، محققان تلاش زیادی را صرف توسعه الگوریتم‌های اکتشافی کارآمد برای حل کلاس مسائل NP-complete کرده‌اند که به طور گسترده اعتقاد بر این است که ذاتاً از نقطه نظر محاسباتی غیرقابل حل هستند. اگرچه الگوریتم‌هایی طراحی شده‌اند و در میان محققان بدنام هستند، برنامه‌های رایانه‌ای یا بر روی رایانه‌ها پیاده‌سازی نمی‌شوند یا به‌دست آوردن آنها بسیار دشوار است. هدف این کتاب ارائه منبعی از الگوریتم های کدگذاری شده فرترن برای تعدادی از مسائل بهینه سازی ترکیبی شناخته شده است. این کتاب به عنوان متن تکمیلی در الگوریتم های ترکیبی، بهینه سازی شبکه، تحقیق در عملیات و علم مدیریت در نظر گرفته شده است. علاوه بر این، توضیح کوتاه در مورد هر الگوریتم به کتاب اجازه می دهد تا به عنوان یک مرجع مناسب استفاده شود. این کار بدون امکانات عالی Bell-Northern Research، کانادا امکان پذیر نبود. H. T. Lau lIe des Soeurs Quebec, Canada آگوست 1986 محتویات صفحه مقدمه قسمت I. برنامه نویسی عدد صحیح فصل 1. برنامه ریزی خطی عدد صحیح فصل 2. برنامه ریزی خطی صفر و یک 30 فصل 3. Zero-one Problem 38 Knapsack II. طراحی شبکه فصل 4. مسئله فروشنده دوره گرد 52 فصل 5. مسئله درخت اشتاینر 81 فصل 6. پارتیشن بندی نمودار 98 فصل 7. مکان K-Median 106 فصل 8. مکان K-Center 114 فهرست برنامه های فرعی NT یادداشت های زیبا 121DU24 دنبال کنید. از نظر کامل بودن NP، ایده توسعه الگوریتم های اکتشافی کارآمد محبوبیت و اهمیت خود را به دست آورده است.

In recent years researchers have spent much effort in developing efficient heuristic algorithms for solving the class of NP-complete problems which are widely believed to be inherently intractable from the computational point of view. Although algorithms have been designed and are notorious among researchers, computer programs are either not implemented on computers or very difficult to obtain. The purpose of this book is to provide a source of FORTRAN coded algorithms for a selected number of well-known combinatorial optimization problems. The book is intended to be used as a supplementary text in combinatorial algorithms, network optimization, operations research and management science. In addition, a short description on each algorithm will allow the book to be used as a convenient reference. This work would not have been possible without the excellent facilities of Bell-Northern Research, Canada. H. T. Lau lIe des Soeurs Quebec, Canada August 1986 CONTENTS Page Introduction Part I. INTEGER PROGRAMMING Chapter 1. Integer Linear Programming Chapter 2. Zero-one Linear Programming 30 Chapter 3. Zero-one Knapsack Problem 38 Part II. NETWORK DESIGN Chapter 4. Traveling Salesman Problem 52 Chapter 5. Steiner Tree Problem 81 Chapter 6. Graph Partitioning 98 Chapter 7. K-Median Location 106 Chapter 8. K-Center Location 114 List of Subroutines 123 Bibliographic Notes 124 INTRODUCTION Following the elegant theory of NP-comp1eteness, the idea of developing efficient heuristic algorithms has been gaining its popularity and significance.