Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 83

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 77 78 79 80 81 82 < 83 > 84 >> Следующая


6.3.1. The node covering problem (158). 6.3.2. The edge covering problem (159).

Chapter 7. Local optimization, heuristic and combined algorithms .............................................................. 161

7.1. Local optimization ............................................ 161

7.1.1. Local optimization (161). 7.1.2. Examples of the defi-

nitions of a neighbourhood (162).

7.2. Heuristic algorithms ..................................... 163

7.2.1. The traveling salesman problem (163). 7.2.2. Graph-

theoretic problems (173).

7.3. Combined algorithms for the traveling salesman problem..... 176

7.3.1. Construction of an initial solution (176). 7.3.2. Improvement of the initial solution (176). 7.3.3. Computation of lower bounds for the traveling salesman problem (176). 7.3.4. Design of combined algorithms: formulation of the problem (176).

7.4. An experimental investigation of a system of combined algo-

rithms for the approximate solution of the traveling salesman problem ....................................................... 177

Chapter 8. Combined branch-and-bound algorithms ...... 181

8.1. The choice of a set for branching ............................. 182

8.2. The choice of the mode of branching ........................... 183

8.3. The choice of algorithms for the computation of bounds ........ 183

8.4. The choice of algorithms for constructing approximate solutions

in the branching process ...................................... 183

8.5. Varying the approximation degree in the solution process .... 184

8.6. Rejection rules ............................................... 184

8.7. Parametrization of combined algorithms ........................ 184
236

Contents

8.8. The choice of control parameters for combined algorithms in

dependence of the computational resources...................

8.9. Branch-and-bound method and dynamic programming ..........

PART IV LARGE-SCALE PROBLEMS

Chapter 9. The computational model and parametrization

9.1. The notion of a large-scale problem for the general discrete optimization problem ..............................................

9.2. The computational model and main parameters ..............

9.3. Applications to some discrete optimization problems ......

9.3.1. The general scheme (195). 9.3.2. Applications to problem solving (199). 9.3.3. Application of the approach to parametrizing an є-optimal algorithm for the solution of large-scale knapsack problems (201).

Chapter 10. Approximate algorithms for large-scale traveling salesman problems ..................................................

10.1. Problem formulation and general information concerning the

algorithms..................................................

10.1.1. Problemformulation (204). 10.1.2. Decomposition-based approach (204).

10.2. Decomposition ............................................

10.2.1. The partition problem: formulation (205). 10.2.2. Determining an initial partition (206). 10.2.3. Construction of an initial partition (208). 10.2.4. Improvement of the initial partition (211). 10.2.5. Correction procedures (212). 10.2.6. Hierarchic decomposition procedures (213). 10.2.7. Consecutive (tree-like) decomposition (213). 10.2.8. Practical solution of the partition problem (214).

10.3. Solving the subproblems ..................................

10.3.1. Constructinginitialsolutions (214). 10.3.2. Improvement of initial solutions (215). 10.3.3. Accuracy estimates for approximate solutions (216). 10.3.4. Dialog procedures (216).

10.4. Constructing an approximate solution from the solutions of subproblems ........................................................

185

186

189

189

191

195

204

204

205

214

217

10.4.1. Constructing an initial sequence of subsets, a complexity
Contents

237

estimate (217). 10.4.2. Improvement of the sequence of subsets (218). 10.4.3. Constructing the solutions (218). 10.4.4. An algorithm for combining the solutions of subproblems, its complexity estimate (219).

10.5. The bicriterial traveling salesman problem .................. 221

10.5.1. Problem formulation (221). 10.5.2. Optimizing the

weighted sum of criteria (222).

PROBLEMS .......................................................... 224

EXERCISES ......................................................... 226

BIBLIOGRAPHY

227
Учебное издание

СИГАЛ Израиль Хаимович ИВАНОВА Александра Петровна

ВВЕДЕНИЕ В ПРИКЛАДНОЕ ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ: МОДЕЛИ И ВЫЧИСЛИТЕЛЬНЫЕ АЛГОРИТМЫ

Редактор Е. Ю. Ходан Оригинал-макет Е. А. Королевой

JIP N5 071930 от 06.07.99. Подписано в печать 27.02.03. Формат 60x90/16. Бумага типографская. Печать офсетная. Уел. печ. л. 15. Уч.-изд. л. 16,5. Заказ N5

Издательская фирма «Физико-математическая литература» МАИК «Наука/Интерпериодика»

117864 Москва, Профсоюзная, 90

Отпечатано с готовых диапозитивов в ПФ «Полиграфист: 160001, г. Вологда, ул. Челюскинцев, 3 Тел.: (8172) 72-55-31, 72-61-75, факс (8172) 72-60-72 E-mail: pfpv@vologda.ru http://www.Vologda/ pfpv
Предыдущая << 1 .. 77 78 79 80 81 82 < 83 > 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100