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

 

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

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

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


с древовидной схемой поиска оптимального решения.... 109

3.6.1. Структура информации о дереве подзадач (HO).
Оглавление

5

3.6.2. Операции на дереве подзадач (110). 3.6.3. Структура информации о подзадаче (111).

3.7. Алгоритм ветвей и границ нахождения множества всех

^-близких решений в общей задаче и некоторые его применения ................................................ 113

3.7.1. Алгоритм нахождения множества всех ^-близких решений (113). 3.7.2. Аппроксимационно-комбинаторныйметод решения задач дискретной оптимизации (114).

Глава 4. Применение метода динамического программирования для решения некоторых аддитивных задач дискретного программирования ................................ 117

4.1. Задача о распределении ресурсов между проектами...... 117

4.1.1. Простой пример (117). 4.1.2. Алгоритм динамического программирования Веллмана для решения задачи (120).

4.1.3. Принцип оптимальности (122).

4.2. Задача о ранце ...................................... 122

4.2.1. Принцип оптимальности Веллмана (122). 4.2.2. Алгоритм решения задачи (124). 4.2.3. Примеры применения алгоритма для решения задач (125).

4.3. Задача о минимизации суммы функций двух переменных .. 129

4.3.1. Постановка задачи и общая схема решения (129).

4.3.2. Алгоритм анализа вариантов (131). 4.3.3. Алгоритм «киевский веник» (132). 4.3.4. Принцип оптимальности (133).

РАЗДЕЛ III

ПРИБЛИЖЕННЫЕ МЕТОДЫ И АЛГОРИТМЫ

В ДИСКРЕТНОМ ПРОГРАММИРОВАНИИ

Глава 5. Постановка задачи о поиске приближенного решения и некоторые общие вопросы ....................... 137

5.1. Постановка задачи ............................. 137

5.2. Общая характеристика алгоритмов приближенного решения

и их классификация .............................. 139

5.3. Локальные и глобальные подходы к повышению эффектив-

ности алгоритмов решения задач дискретного программирования ........................................... 140

5.3.1. Локальные подходы (140). 5.3.2. Глобальные подходы. Переход к є-оптимизации (142).
б

Оглавление

5.4. є-оптимальньїй алгоритм ветвей и границ для задачи о

ранце ................................................. 143

5.4.1. Постановка задачи и алгоритм (143). 5.4.2. Оценка для числа є-существенньїх переменных (146). 5.4.3. Замечания о полиномиальной трудоемкости алгоритма (147). 5.4.4. Примеры (148).

Глава 6. Алгоритмы гарантированного функционирования 151

6.1. Задача об одномерном ранце ........................... 151

6.1.1. Задача об одномерном целочисленном ранце (151).

6.1.2. Задача об одномерном булевом ранце (153).

6.2. Метрическая задача коммивояжера на плоскости ......... 154

6.2.1. Первый алгоритм (155). 6.2.2. Второй алгоритм (156).

6.3. Задачи о покрытиях графов ............................ 158

6.3.1. Задача о вершинном покрытии (158). 6.3.2. Задача о реберном покрытии (159).

Глава 7. Локальная оптимизация, эвристические и комбинированные алгоритмы ......................................... 161

7.1. Локальная оптимизация ................................ 161

7.1.1. Общая схема локальной оптимизации (161). 7.1.2. Примеры определения окрестности (162).

7.2. Эвристические алгоритмы .............................. 163

7.2.1. Задача коммивояжера (163). 7.2.2. Задачи теории графов (173).

7.3. Комбинированные алгоритмы для задачи коммивояжера ...................................................... 176

7.3.1. Построение начального решения (176). 7.3.2. Улучшение начального решения (176). 7.3.3. Вычисление нижней оценки для задачи коммивояжера (176). 7.3.4. Постановка задачи о формировании комбинированного алгоритма (176).

7.4. Экспериментальное исследование системы комбинирован-

ных эвристических алгоритмов для приближенного решения задачи коммивояжера ................................... 177

Глава 8. Комбинированные алгоритмы ветвей и границ 181

8.1. Выбор множества для ветвления ........................ 182

8.2. Выбор способа ветвления............................... 183

8.3. Выбор алгоритмов вычисления оценок ................... 183
Оглавление

7

8.4. Выбор алгоритмов формирования приближенных решений в

процессе ветвления .................................. 183

8.5. Изменение точности в процессе решения задачи....... 184

8.6. Правила отсева..................................... 184

8.7. Параметризация комбинированных алгоритмов ......... 184

8.8. Выбор управляющих параметров комбинированных алгоритмов в зависимости от вычислительных ресурсов ............ 185

8.9. Метод ветвей и границ и метод динамического программирования ................................................. 186

РАЗДЕЛ IV ЗАДАЧИ БОЛЬШОЙ РАЗМЕРНОСТИ

Глава 9. Вычислительная модель и параметризация .... 189

9.1. Понятие о задачах большой размерности для общей задачи

дискретного программирования ........................ 189

9.2. Вычислительная модель и основные параметры......... 191

9.3. Применение полученных результатов к некоторым задачам
Предыдущая << 1 < 2 > 3 4 5 6 7 8 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100