g9 (542472), страница 2
Текст из файла (страница 2)
Множество 
допустимых маршрутов состоит из элементов 
. Количество элементов равно 
Математическая интерпретация задачи:
- это целевая функция ( 9.2.0 )
В качестве ограничений возьмем:
( 9.2.0 )
( 9.2.0 )
- это элементы матрицы путевых расстояний(издержек).
Ограничение ( 9.2 .0 ) говорит о том, что въезд в город осуществляется один раз.
Ограничение ( 9.2 .0 ) говорит о том, что выезд из города осуществляется один раз.
Эта задача может быть также сформулирована как задача о назначениях.
Чтобы была записана задача о коммивояжере, необходимо ввести дополнительные ограничения:
Эти ограничения вводятся, чтобы получить кольцевой маршрут.
Пример.
Пусть имеется матрица 
вида:
полному перебору всех возможных вариантов можно поставить дерево вариантов.
Угловым моментом метода ветвей и границ является возможность получения оптимистических оценок выигрыша выигрышной ветви дерева или совокупности ветвей дерева, имеющих общее начало.
Обозначим через 
- последовательность, где 
указывает количество вершин, а 
- номер этой последовательности( - мощность множества, которое содержит ветвей).
Обозначим - некоторая ветка дерева, включающая вершин вместе с исходной, - это номер(индекс) ветки.
может изменяться от 
до 
, где - мощность множества 
.
, то есть количество ветвей нашего дерева, отличающегося элементами, начиная с первого.
С каждой веткой свяжем последовательность 
, где 
показывает, сколько необходимо вершин, чтобы получить полную ветвь, включающую все города, 
- порядковый номер последовательности.
Пример.
Возьмем 
, где 
(из предыдущего примера).
.................................
Обозначим через - множество всех начальных участков ветвей, содержащих элементов.
- множество ветвей, имеющих общий начальный участок и включающий все городов.
Пример.
Вводится понятие нижней границы для совокупности веток .
где 
- длина участка от исходной вершины по ветви 
.
Оптимистическая оценка:
Обозначим ее
Выбор такой оптимистической оценки ничем не обусловлен. Она может выбираться по-разному.
Эффективность метода ветвей и границ зависит от того, насколько удачна выбрана оптимистическая оценка.
Предлагается следующий способ ее получения:
-
в каждой строке матрицы
![]()
отыскивается минимальный элемент ![]()
. На этом же шаге минимальные элементы строк вычитаются построчно из других элементов.
. На этом же шаге минимальные элементы строк вычитаются построчно из других элементов. 
-
в каждом столбце матрицы
![]()
находим минимальный элемент ![]()
. На этом же шаге вычитаем из элементов каждого столбца минимальный его элемент; получаем матрицу ![]()
.
. На этом же шаге вычитаем из элементов каждого столбца минимальный его элемент; получаем матрицу 
. 
В качестве оптимистической оценки длины маршрута, включающего все 
городов, принимается:
Для любого маршрута, входящего в множество , длина его вычисляется по формуле:
Естественным образом 
Пример.
( продолжение предыдущих примеров )
В процессе решения начало маршрута известно:
- начальный участок.
- строки с номерами.
- столбцы с номерами.
В оставшейся матрице осуществляется процедура приведения.
Для совокупности вычисляется оптимистическая оценка.
,
где 
- длина маршрута.
Пример.
( продолжение предыдущих примеров )
Берем исходную матрицу и вычеркиваем 1 строку и 3 столбец.
Вычислим минимальные элементы:
( 
)
,
где 
.
Алгоритм метода ветвей и границ задачи о коммивояжере.
-
выбирается полная ветвь и вычисляется длина маршрута. Выбранную ветвь называют эталонной.
-
рассматриваются другие начальные участки маршрута. Для каждого из них последовательно вычисляются оптимистические оценки нижней границы длины маршрута.
-
сравниваются: оценка очередного участка маршрута с длиной эталонной ветки:
-
если оптимистическая оценка больше длины эталонной ветви, то участок - бесперспективный и дальше ветвление делать не нужно:
-
иначе, из конечной вершины участка осуществляется ветвление, то есть перебор участков, содержащих на одну вершину больше, чем рассматриваемый участок.
Процесс продолжается до получения полной последовательности.
Если длина маршрута, соответствующая эталонной последовательности, меньше длины эталонной ветви, то ее принимают за эталонную.
Последняя эталонная последовательность будет оптимальной.
Пример.
( продолжение предыдущих примеров )
Шаг 1.
1 2 3 4 5 1 - эталон
Эталонная ветвь: 1 2 3 4 5 1
Шаг 2.
Из исходной матрицы и вычеркиваем 1 строку и 2 столбец, и вычисляем оптимистичную оценку.
( )
.
Шаг 3.
Из исходной матрицы и вычеркиваем 1 и 2 строки и 4 столбец, и вычисляем оптимистичную оценку.
( )
.
Шаг 4.
Из исходной матрицы и вычеркиваем 1 и 2 строки и 5 столбец, и вычисляем оптимистичную оценку.
( )
.
...................................................................................
Шаг 9.
Из исходной матрицы и вычеркиваем 1 строку и 4 столбец, и вычисляем оптимистичную оценку.
( )
.
Шаг 10.
Из исходной матрицы и вычеркиваем 1 строку и 5 столбец, и вычисляем оптимистичную оценку.
( )
.
...................................................................................
Ответ: минимальный маршрут - 231.
9.3Разбиение графа на подграфы с минимальной связностью.
-
существует тривиальный прием решения - перебор всех возможных вариантов разбиения графа и выбор из них оптимального разбиения.
Если число вершин в графе , то число сочетаний
-
существуют алгоритмы направленного( упорядоченного ) перебора.
Алгоритмы:
-
предлагает решать целочисленную задачу квадратичного программирования с минимизацией суммы внешней связи между подграфами. Такая задача решается методом ветвей и границ, где на каждом шаге ветвления решаются линейные задачи;
-
алгоритм эвристический.
Суть первого алгоритма состоит в следующем:
если нам необходимо разрезать граф, заданный матрицей смежности на 
подграфов, то эту процедуру сводят к последовательному разрезанию на 2 подграфа.
Для реализации этой цели выделяют в матрице 
две подматрицы. Размерность подматриц равна числу вершин первого и второго подграфов.
Для каждой строки матрицы 
подсчитывают числа внешней связности - 
и числа внутренней связности - 
.
Эти числа подсчитывают следующим образом:
, 
- количество вершин, которые будут в первом подграфе.
.
Пример.
Имеется граф, содержащий 9 вершин. Требуется разбить его на 3 подграфа по 3 вершины в каждом.
|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 | 0 | 1 | 2 | 0 | 3 | 0 | 1 | 0 | 2 |
| 2 | 1 | 0 | 0 | 1 | 0 | 2 | 0 | 3 | 1 |
| 3 | 2 | 0 | 0 | 2 | 1 | 3 | 1 | 2 | 1 |
| 4 | 0 | 1 | 2 | 0 | 0 | 1 | 2 | 1 | 0 |
| 5 | 3 | 0 | 1 | 0 | 0 | 2 | 1 | 0 | 3 |
| 6 | 0 | 2 | 3 | 1 | 2 | 0 | 1 | 2 | 3 |
| 7 | 1 | 0 | 1 | 2 | 1 | 1 | 0 | 0 | 1 |
| 8 | 0 | 3 | 2 | 1 | 0 | 2 | 0 | 0 | 2 |
|
| 2 | 1 | 1 | 0 | 3 | 3 | 1 | 2 | 0 |
9 После вычисления чисел: числа внешней связности - и числа внутренней связности - вычисляются элементы вспомогательной матрицы по следующей формуле:
.
Получают матрицу 
. Элементы этой матрицы характеризуют изменение числа связей при перестановке вершин 
и 
. Анализируя матрицу находим максимальный элемент 
. При наличии нескольких одинаковых максимальных элементов выбирается один из них(любой). Осуществляется перестановка в матрице столбцов и строк с номерами 
и . Получим 
.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
