4. Решение переборных задач.
Допустимое множество состоит из конечного числа элементов, поэтому решение задачи всегда можно найти за конечное число шагов, но в ряде случаев количество вариантов слишком велико, чтобы можно было организовать их полный перебор, и приходится искать методы целенаправленного перебора.
4.1. Метод ветвей и границ.
Пусть
-
все множество возможных вариантов. На
этом множестве задан функционал качества
f(x).
Надо найти
f(x)
Пусть
мы можем оценить этот минимум на
через
параметр :
f(x)
Делим
множество
на
два множества. Для каждого из этих
множеств выписываем оценку:
f(x);
,
Будем постепенно получать дерево: ( -граница)
Способ получения этого дерева описывается ниже:
Выберем
минимальный среди
.
Пусть
минимальный
.
Делим
на
два множества, вычисляем оценки и т.д.
Пусть
где-то получили множество
...=
{
}
с оценкой
...
(которая
меньше всех других)
Тогда
-
оптимальный вариант.
Если оценка не минимальная, то находим тот лист дерева, у которого оценка минимальная и соответственно I вновь разбиваем на два множества и т.д.
Метод ветвей и границ (МВГ) дает экономию по сравнению с перебором всех вариантов.
Рассмотрим пример.
4.1.1. Задача о коммивояжере.
Есть n городов. Надо объехать все города с минимальной стоимостью (расстоянием) и вернутся в исходный город. При этом каждый город посещается один раз (т.е. имеется Гамильтонов цикл, но с минимальной стоимостью).
Матрица стоимостей путей
A
=
-стоимость
пути от i
до j.
м.б.
,
0 ,
i,
j
Допустимый маршрут содержит по одному элементу в каждой строке и столбце. Обратное неверно, так как возможны подциклы
Количество возможных вариантов n!.
Составим математическую модель:
Обозначим
, причем
1 - если дуга входит в маршрут
0 - если дуга не входит в маршрут.
?
, причем
=
1, j
=
,
{0,1}
* в каждом столбце содержится один элемент
=
1, i
=
* в каждой строке содержится один элемент
Эти ограничения разрешают циклы, поэтому эти условия являются необходимыми, но не достаточными.
Требование
непрерывности маршрута обеспечиваются
введением дополнительных N
ограничений, где N
=
,
каждое ограничение имеет вид:
n
i
=
,j
=
Таким образом, матрица сильно разрежена, симплекс-метод применять не выгодно.
Используем МВГ.
Предположим,
что мы выбирали некоторый путь S,
его длина
=
,
причем каждый из индексов используется
один и только один раз.
Так как в путь S входит только один элемент из каждой строки и столбца, то можно проделать операцию нормализации матрицы A. Выберем произвольную строку i .
-
наименьший элемент i
-й строки и построим матрицу
с
элементами
=
(изменена
каждая строка)
Матрица
определяет
новую задачу коммивояжера, которая в
качестве оптимальной будет иметь ту же
последовательность городов.
=
+
В
каждой строке
будет теперь, по крайней мере, один
нулевой элемент.
Обозначим
-
минимальный элементj-го
столбца
.
Построим
матрицу
с
элементами
=
Оптимальный
путь тот же, а длина
=
+
,
где
=
+
Обозначим
-
решение задачи коммивояжера (ЗК).
=
Тогда
величина
-
простейшая нижняя оценка решения
:
(*)
это
для МВГ.
Рассмотрим
ЗК с матрицей
.
Рассмотрим путь S, содержащий переход i j.
Тогда нижняя оценка пути:
+
Следовательно,
для тех переходов, у которых
=
0 будем иметь снова оценку (*). Естественно
ожидать, что кратчайший путь содержит
один из таких переходов.
Рассмотрим
один из переходов i
j,
для которого
=
0.
Обозначим
(i
j)
-множество
всех тех путей, которые не содержат
переход i
j.
Так
как из города i
надо куда-то идти, то множество (i
j)
содержит
один из переходов i
k,
k
j.
Так
как в город
j
надо прийти, то множество (i
j)содержит
переход m
j,
где m
i.
Следовательно,
некоторый путь
из множества (i
j),
содержащего переходы
i k , m j, будет иметь следующую нижнюю оценку:
+
+
Обозначим:
=
+
Для
любого из множества путей (i
j)
мы будем иметь оценку:
+
(**)
Мы
хотим исключить некоторое множество
вариантов (i
j).Поэтому
надо выбрать такой переход i
j,
для которого оценка (**) была бы максимальной.
=
(
+
)
Таким
образом, все множество возможных
вариантов мы разбили на два множества:
,
.
Для
путей из множества
-
оценка (*).
Для
путей их множества
-
оценка
+
.
Для
матрица
будет
отличаться от матрицы
тем, что
(переход i j запрещен , кот. выбран).
Рассмотрим
множество
и матрицу
.
Так как все пути, принадлежащие этому множеству, содержат переход i j, то для его исследования достаточно рассмотреть ЗК, в которой города i и j совпадают
(из
вычеркиваетсяi
-ая строка и j
-й столбец).
Размерность этой задачи n - 1.
Так
как переход j
i
невозможен, то элементы матрицы
:
.
Точнее,
так как элемента
может
не быть, маршрут, определяемый дугой
( i, j ) содержит сколько-то (может быть ни одного) из ранее выбранных ребер помимо ребра ( i, j ).
Ребро ( i, j ) будет или изолировано от этих других ребер, или будет частью пути, включающего некоторые или все эти ребра.
Пусть
p
и q
- начальный
и конечный города этого пути. Возможно,
что p=i
или q=j.
Положим
.
Эта мера предохраняет от выбора ребра (q , p) в качестве последующего, а тем самым предохраняет от формирования замкнутого цикла длины < n.
В общем случае, среди всех полученных множеств вариантов выбираем то, для которого оценка минимальна.
Пример:
A
:
:
:
27+8=35
- определяем "веса" нулей (минимум по строке + минимум по столбцу)
- выбираем ноль с максимальным "весом",
- выбираем соответствующий путь и вычеркиваем столбец и строку.
Выбираем путь 32.
:
,
23
- запрещен (т.к.
выбран 32)
:
оценка 35 + 4 =39
Выбираем путь 13; пути 31 нет
:
3
2
- запрещенный путь ( выб.
в A1)
оценка 35 + 38 + 20 =93
:
1
3
оценка 39 + 37 =76
132
; запрещенный путь: 2
1
:
оценка 39 + 35 =74
Путь
132
был . По
:
241
Оптимальный
путь: 1
3
2
4
1
Вес: 74 = 24 + 4 + 45 + 1 (см. A)
строилось дерево:
Упражнение: Написать программу решения задачи о ранце с помощью метода ветвей и границ.