6. Лабораторная работа № 6 Кратчайшие пути в графе

   1. Цель работы: Изучить основные задачи поиска кратчайших путей в графах и научиться решать задачу коммивояжера

   2. Теоретические сведения

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

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

Теория графов позволяет свести эту так называемую задачу коммивояжера к вопросу о поиске кратчайшего гамильтонова цикла в орграфе. Предположим, что вершины орграфа - это города, а дуги - пути, которые соединяют эти города. Каждой дуге, которая соединяет города i и j ,соответствуетчисло l_ij(длина дуги),котороеравняется расстоянию между городами. Длины дуг в орграфе обычно задают в форме матрицы расстояний D.

При решении задачи коммивояжера широкое применение приобрелметод ветвей и границ.

Предположим, что в некоторому орграфе G существует m гамильтоновых циклов. Обозначим это множество циклов через U .Пусть L_i- длина i -го цикла. Решением задачи коммивояжера будет гамильтонов цикл, длина которого Lmin - наименьшая сравнительно с длинами других циклов

Оценкой снизумножества U всех гамільтонових циклов назовем значение L*, которое удовлетворяет неравенству

L * < Lmin .

Метод ветвей и границ дает возможность вычислить такую оценку и дальше последовательно приблизить ее к значению Lmin

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

Эту операцию осуществляют в такой последовательности: 1) из каждого элемента каждой строки отнять минимальный элемент h_iэтого же строки (приведение по строкам); 2) из каждого элемента каждого столбца после приведения по строкам отнять минимальный элемент g_jэтого же столбца (приведение по столбцам). Элементы h_iи g_j назваются константами приведения .

Вследствие приведения матрицы расстояний длины всех гамильтонових циклов уменьшаются на ,что дает оценку снизу L* множества U всех циклов, то есть

Разобьем множество Uна два подмножества, содержащее Y_i,j и не содержащее Y_i,j, и применим метод приведения матриц расстояний этих подмножеств для нахождения их оценок снизу(L₁ и L₂).

Матрицу расстояний D₁ подмножества Y ((i,j))получимизприведенной матрицы D начального графа путем вычеркивания i-й строки и j -го столбца, поскольку другие элементы из этих строк уже не могут быть использованы. По этой же причину изымают дугу (j , i ), то есть в матрицеD₁ считают dij =∞. Этот процесс имеет название стягивания дуги (i,j ).

Матрицу расстояний D₁подмножества Y ((i,j)) найдем из приведенной матрицы D начального графа, если запретить движение вдоль дуг (i ,j ) и (j , i) и считать их длины dij =∞и dij =∞.

Замечание.За дугу разбивки (i,j) должнабыть избрана та дуга, для которой подмножество Y((i,j)) получит меньшую оценку сравнительно с оценкой подмножества. Среди множества дуг, которые удовлетворяют этому условию, надо отдать преимущество той дуге, которая дает самое большое различие оценок подмножеств

Y ((i,j)) и.

Доказано, что оценки найденных подмножеств Y ((i,j)) исоответственно вычисляют за формулами

где θij -сумма констант приведения матрицы расстояний D₁подмножества Y ((i,j));

∆ij - сумма наименьших элементов i -й строки и j -го столбца в приденной матрице расстояний множества U .

Дальше процесс длится аналогично, причем для каждого следующего шага избирают неразветвленное подмножество циклов, которое имеет наименьшую оценку. В конце процесса должен остаться один цикл.

Алгоритм поиска гамильтонова цикла кратчайшей длины

1. Привести матрицу расстояний D представленного графа.

2. Вычислить оценку L* длины всех гамильтонових циклов.

3. Определить оценки всех нулевых элементов dij = 0 приведенной матрицы D .Оценка нулевого элемента dij равняется сумме наименьших элементов i -й строки и j -го столбца за исключением самого нулевой элемента dij .

7. Пусть dij = 0 - нулевой элемент, который имеет самую большую оценку. Разбить множество U всех гамільтонових циклов на подмножества Y ((i,j)) и.

5. Построить матрицы расстояний этих подмножеств. Матрица расстояний D₁ подмножестваY((i,j )) может быть построенная из приведенной матрицы D графа путем вычеркивания i -й строки и j -го столбца. Матрица расстояний D₁ подмножестваможет быть получена из приведенной матрицы D графа, если предположить, что dij =∞и dij =∞.

6. Привести матрицу расстояний подмножества Y ((i ,j ))по строкам и столбцам.

7. Определить оценки подмножеств Y ((i ,j ))и.

8. Выбрать из двух подмножеств Y ((i ,j ))ито, что имеет наименьшую оценку и является неразветвленным (обозначим это множество черезZ). Выполнить для этого подмножества шаги 3,4,5,6,7,8. Процесс заканчивается, если будет найдено подмножество, составленное из одного цикла, который имеет наименьшую оценку, или все неразветвленные подмножества будут иметь оценку+ ∞( в этом случае задача не имеет решения). Размерность2 Х 2матрици расстояний множестваZ -признак того, что множествоZсоставляется с одного цикла.

Пример. Найти гамільтонів цикл иайкоротшої длины в графе, матрица расстояний которого имеет вид

Решение. Справа от строк выписанные константы возведения за строками. После возведения матрицы за строками выписываем внизу под столбцами константы возведения за столбцами. Оценка всего множества циклов будет

Тогда приведенная матрица расстояний Dбудет :

	1	2	3	4	5
1	∞	5	4	0^5	2
2	5	∞	0^0	3	0^1
3	5	0^1	∞	8	1
4	0^6	1	5	∞	3
5	5	0^0	0^0	4	∞

В правом верхнем углу клетки даны оценки нулевых элементов. Максимальную оценку имеет нулевой элемент d₄₁. После изъятия 4-го строки и 1-го столбца из приведенной матрицы она превратится на матрицуD₁расстояний подмножестваY((4;1)):

Здесь d₁₄ = ∞, чтобы предотвратить возникновение цикла.

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

	2	3	4	5
1	3	2	∞	0^2
2	∞	0^0	0^1	0^0
3	0^1	∞	5	1
5	0^0	0^0	1	∞

Вычисляем оценки * снизу подмножеств

где ∆₄₁- оценка нулевого элемента d₄₁матрице D .

Максимальное увеличение оценки подмножества Y ((4;1)) должна дать дуга (1;5), поскольку оценка нулевого элемента d₁₅- самая большая. Изымем из приведенной матрицы D₁первуйю строкуи пятый столбец и положим d₅₄=∞, потому что дуга (5;4) замыкает избраннаю цепь вершин (4;1;5) и порождает цикл. Тогда матрицаD ₂ расстояний подмножества Y ((4;1), (1;5)) приобретает вид:

	2	3	4
2	∞	0^0	0^5
3	0^5	∞	5
5	0^0	0^0	∞

Эта матрица приведена, поэтому в правом верхнем углу выписываем оценки нулевых элементов.

Определим оценки снизу подмножеств Y((4;1), (1;5)) и Y ((4;1),

Поскольку это предопределяет необходимость разветвлять подмножествоY ((4;1),(1;5)).Оптимальный относительно дальнейшего разветвления этого подмножества - выбор дуги с максимальной оценкой нулевого элемента. В матрицеD₂существует два таких элемента: (2;4) и (3;2). Итак, обе эти дуги можно отнести к искомому гамильтоновому циклу. Выбираем любую из них, например, дугу (2;4). Имеем уже приведенную матрицу D₃:

Таким образом, получена последовательность дуг (3;2), (2;4), (4;1), (1;5).Чтобы замкнуть эту последовательность, не хватает дуги(5;3).Если добавить ее, получим искомый гамильтонов цикл, который можно представить в виде(3, 2, 4, 1, 5, 3).Его длина равняется 13.

Анализ не рассмотренных выше подмножеств указывает на то, что их оценки снизу больше L³¹=13, поэтому эти подмножества не могут содержать гамильтоновых контуров, которые меньше чем найденный. Итак, дальнейшая их проверка не нужна и найденный гамильтонов цикл - кратчайший.