Шпаргалка по "Математическим методам"

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

    1.Постановка  общей задачи

    Задача  о коммивояжере. Имеется N городов, заданы расстояния между городами. Торговый агент, или коммивояжер, находится в городе 1, ему необходимо посетить  только по одному разу все остальные N-1 городов и вернуться в исходный город 1. Требуется установить порядок обхода городов, при котором общее пройденное им расстояние минимально.

    С точки зрения теории графов рассматриваемая  задача формулируется следующим  образом.

    Пусть дан исходный связанный граф G(X,U), где X- множество вершин, означающих объекты; U- множество дуг графа, каждая из которых означает возможную взаимосвязь между двумя вершинами (объектами). В каждой дуге u_ij поставлено в соответствие  некоторое число a_ij, называемое весом дуги.

Весом дуги может  быть расстояние между двумя вершинами, временем проезда из одной вершины  в другую, стоимостью проезда и  т.д.

    Требуется выделить на исходном графе такой  частичный граф G(X,V), который удовлетворял бы следующим условиям:

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

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

         Из существующих методов решения задачи о коммивояжере одним из наиболее эффективных яв-ся метод ветвей и границ. Суть метода состоит в том, что множество всех допустимых решений, т.е. возможных циклов и маршрутов обхода заданных N городов, разбивается на последовательно уменьшающиеся подмножества. Этот процесс сопровождается вычисление возможных длин циклов или их нижних границ. В конце концов, получается подмножество, представляющее цикл обхода, длина которого не более, чем у любого другого возможного, т.е. оптимальный цикл.

Алгоритм  метода.

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

   Нижняя граница определяется по следующей формуле:

    Шаг 2.  Просмотрим все элементы  a_ij=0  и вычислим для каждого сумму минимальных элементов строки i и столбца j, исключая сам элемент a_ij=0. Обозначим эту сумму через   и впишем в клетку (i,j), отметив ее кружком.  Величина - вероятное увеличение длины цикла при невключении в него элемента (i,j). В связи с этим целесообразно взять ту пару (i,j), для которой величина максимальна. С помощью пары (i,j) разбиваем все множество всех возможных циклов на два подмножества: включающее (i,j) и невключающее пару (i,j).

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

Шаг 1-3 повторяется  до тех пор, пока не получим матрицу  расстояний размерностью 2х2.