6. Метод ветвей и границ.

Метод ветвей и границ основан на упорядоченном переборе вариантов, рассмотрении лишь тех вариантов, которые оказываются по определенным признакам перспективными, и отбрасывании сразу целого множества вариантов, являющихся бесперспективными. Вначале исходное множество разбивается на некоторое число подмножеств, одно из которых включает оптимальный вариант. Для каждого из подмножеств вычисляется функция предпочтения (находится нижняя или верхняя оценка) и выбирается подмножество с оптимальной оценкой для дальнейшего ветвления. Этот процесс удобно изображать в виде дерева, вершинами которого будут рассматриваемые подмножества. Далее передвигаются с этапа на этап, выбирая каждый раз висячую вершину с оптимальным значением функции предпочтения. Полученное дерево будет деревом решения.

ПРИМЕР 3.10. Найти кратчайший путь из А в В.

М 9 К

2. 2 4 3

А 3 1 2 7 В

Р 5 Т

Вначале рассмотрим 2 подмножества путей, которые являются продолжением отрезков [A, M] и [A,P]. За нижнюю оценку каждого из этих подмножеств можно взять длины дуг: v[A,M]=v[A, P]=3. Так как оценки равны, рассмотрим продолжения каждого из этих путей: v[А,М,Р]=4; v[А,М,К]=12; v[А,М,Т]=5; v[А,Р,К]=7; v[А,Р,Т]=8. Оценка нового пути до вершины Р оказалась больше предыдущей, следовательно путь [А,М,Р] отсекается. Также отсекаются пути [А,М,К] и [А,Р,Т]. Рассмотрим варианты продолжения пути с наименьшей оценкой [А,М,Т]: v[А,М,Т,В]=12. Допустимый путь получен. Однако его оценка не является наименьшей оценкой среди других висячих вершин. Рассмотрим варианты продолжения пути [А,Р,К]: v[А,Р,К,В]=10; v[А,Р,К,Т]=9. Второй вариант отбрасываем, т.к. к вершине Т существует путь с меньшей оценкой. Получили оптимальный путь [А,Р,К,В]

Метод ветвей и границ – точный метод решения задач. Он предъявляет большие требования к оперативной памяти ЭВМ. Поэтому обычно используют приближенные методы, в которых по относительно простым правилам строятся допустимые решения, которые должны быть удовлетворительными с практической точки зрения, хотя могут и не быть оптимальными.

Задача коммивояжера.

Коммивояжеру необходимо посетить N городов, заходя в каждый город 1 раз и вернуться домой. С точки зрения теории графов: найти минимальный Гамильтонов цикл.

АЛГОРИТМ ЛИТТЛА.

0. Представим граф в виде матрицы стоимостей, на главной диагонали которой стоимость = ∞.

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

2. Проведём оценку всех нулевых элементов матрицы. , исключая выбранный элемент. Выберем максимальную из оценок θ=max γ_ij=γ_kl

3. Множество путей разобьём на два подмножества: пути, содержащие дугу (k,l) и пути, не содержащие дугу (k,l). Для второго подмножества нижней границей будет: в^/=в+ θ Чтобы вычислить границу для первого подмножества, перейдём к матрице на порядок ниже, вычеркнув k-строку и l-столбец. В новой матрице для исключения пути (l,k) в соответствующую клетку поставим знак ∞. Вычислим оценку полученной матрицы аналогично п.1 и добавим её к нижней границе цикла. Эта сумма в^// и будет границей для первого подмножества.

4. Сравним границы всех висячих вершин и выберем вершину с наименьшей границей. Если минимальной является граница в^/, то возвращаемся к матрице на порядок выше и, чтобы исключить дугу (k,l) из рассмотрения, заносим в соответствующую клетку знак ∞. Переходим к п.1.

5. Процесс продолжается до тех пор, пока не получим матрицу 1-ого порядка.

ПРИМЕР 3.11. Найти все Гамильтоновы циклы. Определить оптимальный путь коммивояжера по алгоритму Литтла.

2 5

РЕШЕНИЕ:

Г амильтоновы циклы

Граф задан в форме матрицы, где в ячейках задана стоимость передвижения между пунктами. На главной диагонали ставится символ ∞, чтобы исключить бессмысленный путь в сам себя.

	A	B	C	D	min
A	∞	2	3	2	2
B	2	∞	5	2	2
C	3	5	∞	6	3
D	2	2	6	∞	2

1.1. Найдем в каждой строке матрицы минимальный элемент и вычтем его из всех элементов этой строки.

	A	B	C	D
A	∞	0	1	0
B	0	∞	3	0
C	0	2	∞	3
D	0	0	4	∞
min			1

Т.к. в полученной матрице оказался столбец без нулевых элементов, то найдем в нем минимальный элемент и вычтем его из всех элементов этого столбца.

	A	B	C	D
A	∞	0	0	0
B	0	∞	2	0
C	0	2	∞	3
D	0	0	3	∞

Просуммируем все вычтенные элементы и получим нижнюю границу цикла в=2+2+3+2+1=10

1.2. Проведём оценку всех нулевых элементов матрицы.

γ_АВ=0+0=0

γ_АС=0+2=2

γ_AD=0+0=0

γ_BА=0+0=0

γ_BD=0+0=0

γ_CA=0+2=2

γ_DA=0+0=0

γ_DB=0+0=0

Оценку нулей удобно представлять в таблице.

	A	B	C	D
A		0	2	0
B	0			0
C	2
D	0	0

Выберем максимальную из оценок θ=max γ=γ_АC=2

1 .3. Множество путей разобьём на два подмножества:QAC– пути, содержащие дугу (AC) и QAC– пути, не содержащие дугу (АC). Для второго подмножества нижней границей будет: в^/=в+ θ =10+2=12.

Чтобы вычислить границу для первого подмножества, перейдём к матрице на порядок ниже, вычеркнув A-строку и C-столбец. В новой матрице для исключения обратного пути (CA) в соответствующую клетку поставим знак ∞.

	A	B	D	min
B	0	∞	0
C	∞	2	3	2
D	0	0	∞

Преобразуем матрицу аналогично п.1.1

	A	B	D
B	0	∞	0
C	∞	0	3
D	0	0	∞

Вычислим границу полученной матрицы 2+0=2

и добавим её к нижней границе цикла. Эта сумма в^//=10+2=12 и будет границей для первого подмножества.

1.4. Сравним границы всех висячих вершин и выберем вершину с наименьшей границей. Если этих вершин две, выбираем любую из них. Это вершина QAC, нижняя граница которой =12.

	A	B	D
B	0	∞	0
C	∞	0	3
D	0	0	∞

1.5. Проведём оценку всех нулевых элементов матрицы.

	A	B	D
B	0		3
C		3
D	0	0

Выберем максимальную из оценок θ=max γ=γ_BD=3

в^/=12+3=15.

1.6. Все последующие пункты выполняем аналогично предыдущим.

	A	B
C	∞	0
D	0	∞

Оценка нулей:

	A	B
C	0	∞
D	∞	0

Выберем максимальную из оценок θ=max γ=γ_СB=∞

в^/=в+ θ=∞

	A
D	0

В се строки и столбцы этой матрицы содержат нули. Следовательно, граница остается равной 12.