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

 

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

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

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 30 31 32 33 34 35 < 36 > 37 38 39 40 41 42 .. 84 >> Следующая


Найдем сначала верхнюю оценку по правилу перехода в ближайшую точку. Полученный маршрут z имеет вид 1—> 2 —> 3 —> 4 —> Б —>
104

Разд. II. Комбинаторные методы решения задач

—У б —У I, l(z) = 13. Если при решении задачи могут быть построены

3 два 1-дерева с одинаковой длиной, одно

из которых является маршрутом коммивояжера, т.е. степени всех вершин равны

2, то этот маршрут является решением оценочной задачи и может стать новым рекордом. Такой подход позволяет уменьшать число решаемых подзадач и число ветвлений. Для матрицы С построим 1-дерево Ti, которое имеет вид, представ-Рис. 3.14 ленный на рис. 3.14.

Длина 1-дерева I (Ti) = 8, поэтому 8 < I (zo) < 13; здесь

di = 2, d2 = 4, б?з = 2, б?4 = I, б?5 = 2, d,Q = 1.

Первый шаг алгоритма. Исходная задача разветвляется на четыре задачи, так как d2 = 4. Фрагмент дерева ветвления имеет вид, показанный на рис. 3.15.

Рис. 3.15

Вычислим оценки для каждой из вершин.

Второй шаг алгоритма. 1) Для вершины (1,2) 1-дерево Ti имеет вид, показанный на рис. 3.16, его длина равна 9. При этом d\ = 2, d2 = 3, ds = 2, g?4 = I, c?5 = 2, 6? = 2. Задача (1,2) разветвлена на три подзадачи, как это показано на рис. 3.26, где представлено полное дерево ветвления. На этом рисунке отмечены подзадачи, для которых 1-дерево является циклом.

3

2) Для вершины (2,3) 1-дерево Ti имеет вид, показанный на рис. 3.17, его длина равна 10. При этом d2 = 3 и задача (2,3) разветвлена на три подзадачи.
Гл. 3. Метод ветвей и границ

105

3) Для вершины (2,4) 1-дерево Ti имеет вид, показанный на рис. 3.18, его длина равна 10, 4 = 3 и задача (2,4) разветвлена на три подзадачи.

4) Для вершины (2,5) 1-дерево Ti имеет вид, показанный на рис. 3.19, его длина равна 10, 4 = 3 и задача (2,5) разветвлена на три подзадачи.

В результате выполнения второго шага алгоритма мы получили, что 9 <1 (z0) < 13.

Третий шаг алгоритма. 1) Для задачи, у которой запрещены переходы (1,2) и (2, 3), получаем 1-дерево в виде цикла (1, б, 5, 2,4, 3,1) с длиной 11 (рис. 3.20). Поэтому

9 < I(Z0) < 11,

вершина, соответствующая рассмотренной задаче, становится новым рекордом и в дальнейшем ветвлению не подлежит. Из решения этого примера в п. 3.4.6 известно, что длина оптимального маршрута равна 11.

Рис. 3.20

Рис. 3.21

Рис. 3.22

2) Для задачи, у которой запрещены переходы (1,2) и (2,4), получаем 1-дерево в виде цикла (1, 3, 2, 5, б, 4,1) с длиной 11 (рис. 3.21). Мы снова получили оптимальное решение задачи. Вершина, соответствующая рассмотренной задаче, дальнейшему ветвлению не подлежит.

3) Для задачи, у которой запрещены переходы (1, 2) и (2, 5), получаем 1-дерево в виде цикла (1, 3, 2,4, 5, б, 1) с длиной 11 (рис. 3.22) —
106

Разд. II. Комбинаторные методы решения задач

снова оптимальное решение задачи. Вершина дальнейшему ветвлению не подлежит.

После выполнения третьего шага алгоритма получаем, что 10 < < I(Z0) < И.

Четвертый шаг алгоритма. Переходим к ветвлению задачи (2,3).

1) Для вершины (2,3) и (1,2) на третьем шаге уже было построено 1-дерево, поэтому оценка 11 фиксируется без непосредственного вычисления.

2) Для вершины (2,3) и (2,4) 1-дерево изображено на рис. 3.23, его длина равна 12. Задача отсеяна.

2

^ 5

..... 3

4

Рис. 3.23

3) Для вершины (2,3) и (2,5) 1-дерево представляет собой цикл (1, 2,4, б, 5, 3,1) (рис. 3.24), его длина равна 12. Вершина исключается из рассмотрения.

После выполнения четвертого шага имеем 10 < Z(^o) <11-

Пятый ШАГ алгоритма. Переходим к ветвлению задачи (2,4).

2 Задача (2,4), (1, 2) с оценкой 11 реше-

на на третьем шаге.

Задача (2,4), (2,3) с оценкой 12 решена на четвертом шаге.

Решим задачу (2,4), (2,5). 1-дерево для этой задачи приведено на рис. 3.25 и имеет длину 12. Задача отсеяна по прави-

4 лам отсева.

После выполнения пятого шага имеем

10 < I(Z0) < 11.

Шестой шаг алгоритма. Переходим к ветвлению задачи (2,5).

Задача (2,5), (2,3) с оценкой 12 решена на четвертом шаге.

Задача (2,5), (2,4) с оценкой 12 решена на пятом шаге.

Задача (2,5), (1,2) с оценкой 11 решена на третьем шаге.

6

Рис. 3.25

Рис. 3.24
Гл. 3. Метод ветвей и границ

107

Цикл, Цикл Цикл Цикл рекорд

Цикл Цикл

Рис. 3.26

Цикл

Цикл

Все эти подзадачи отсеяны и симметричная задача решена, оптимальный маршрут имеет длину 11.

При решении этой задачи было решено 11 оценочных подзадач, каждая из которых сводилась к нахождению кратчайшего 1-дерева. На рис. 3.26 показано полное дерево ветвления для симметричной задачи.

3.5.4. Некоторые рекомендации для практического решения задач. В рассмотренном примере дерево ветвления содержит 17 вершин, но реально было решено лишь 11 оценочных подзадач, для шести задач результат решения был зафиксирован без их непосредственного решения. Такая ситуация типична при применении описанного подхода для решения симметричных задач. Это связано с тем, что в процессе решения возникают подзадачи с одинаковыми множествами запрещенных переходов, т.е. с равными значениями оценок. Если одна из таких подзадач решена, то значения оценок для других подзадач фиксируются без их непосредственного вычисления. При этом возникает вопрос о том, какая из двух операций более экономна в смысле быстродействия — повторное вычисление оценки или нахождение задачи с уже вычисленным значением оценки, если такая задача существует на дереве подзадач. Построение 1-дерева и вычисление его длины имеет трудоемкость О (n2) = С2 Ti2 арифметических операций. Остановимся на трудоемкости операции нахождения задачи с уже вычисленным значением оценки. Каждой концевой вершине дерева поставим в соответствие единственный путь, ведущий из нее к вершине второго уровня (на первом уровне — начальная вершина, на втором — вершины, соответствующие задачам с одним запрещенным переходом и т.д.). Каждой вершине соответствует запрещенный переход, два пути на дереве ветвления будем называть одинаковыми, если соответствующие им множества запрещенных переходов совпадают. Под длиной пути будем понимать количество вершин в нем.
Предыдущая << 1 .. 30 31 32 33 34 35 < 36 > 37 38 39 40 41 42 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100