Кратчайший путь между двумя вершинами.

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

Алгоритм Дейкстры для нахождения кратчайшего пути (Dijkstra, 1959).

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

В начальный момент вершина имеет постоянную метку , а все остальные вершины графа – временные метки . На первом шаге алгоритма каждая вершина , для которой существует дуга , получает временную метку (помечается из вершины ). Затем вершина , для которой имеет минимальное значение, получает постоянную метку (если минимум достигается на нескольких вершинах, то берется любая из них). Кратчайший путь из в проходит по ребру .

На втором шаге алгоритма для каждой вершины , которая имеет временную метку и для которой существует дуга , вычисляется сумма и, если эта сумма меньше, чем , то вершина получает новую временную метку

(помечается из вершины ).

Затем среди всех вершин, имеющих временные метки, находится вершина , для которой имеет минимальное значение, и её временная метка делается её постоянной меткой .

Пусть - вершина, получившая на () – ом шаге постоянную метку. Тогда на – ом шаге алгоритма для каждой вершины с временной меткой, для которой существует дуга , вычисляется сумма и, если эта сумма меньше чем , то вершина v получает новую временную метку

(помечается из вершины ). Затем среди всех вершин, имеющих временные метки, выбирается вершина с минимальной временной меткой и полагается .

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

Для вершины постоянная метка есть, очевидно, длина кратчайшего пути из x в . Пусть после () – го шага множество вершин, имеющих постоянные метки, есть и длины кратчайших путей от x до этих вершин совпадают с их постоянными метками , , ,…, . Пусть на k- том шаге вершина , имевшая к этому моменту временную метку , полученную из некоторой вершины , получает постоянную метку . Покажем, что есть длина кратчайшего пути из х в . Допустим противное, что длина кратчайшего из х в меньше, чем . Тогда кратчайший путь не может проходить только через вершины множества , т.к. в этом случае вершина имела бы перед k – ым шагом метку, полученную не из вершины , а из другой вершины, а именно, из вершины, предшествующей на кратчайшем пути. С другой стороны, этот путь не может проходить и через вершины, не принадлежащие , т.к. первая такая вершина на кратчайшем пути должна была бы получить постоянную метку раньше вершины . Поэтому длина кратчайшего пути из x в обязана быть равной .

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

Рассмотрим работу алгоритма на примере представленного на рисунке графа.

 

Работу алгоритма представим в виде таблицы, элемент на пересечении i – ой строки и j – го столбца которой есть метка j – ой вершины после i – го шага. В скобках около метки каждой вершины указано, из какой вершины она была помечена.

Вершины Шаги алгоритма X y
0*
0*
0*
0*
0*
0*
0*

Длина кратчайшего пути из x в y равна 12. выписывая вершины, из которых была помечена вершина , получаем . Инвертируя данную последовательность, получаем кратчайший путь .

 

Тест.

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

2. Трудоемкость алгоритма Дейкстры равна а) ; б) ; в) .

3. Вершины получают постоянные метки в порядке а) неубывания от x; б) невозрастания расстояния от х; в) порядок не является монотонным относительно расстояния.

 

 

2.5. Задача коммивояжера. Метод «ветвей и границ».

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

В качестве её практического приложения можно указать следующее. Пусть имеется станок, способный выполнять несколько операций. Его перенастройка с одной операции на другую требует определенных затрат. Требуется использовать станок в циклическом режиме, минимизируя суммарные затраты на перенастройку.

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

Для решения задачи коммивояжера можно попытаться использовать «жадный алгоритм», успешно примененный в задаче о минимальном остовном дереве. Упорядочим предварительно дуги по весам и будем включать дуги минимального веса, следя за тем, чтобы не возникли вершины, полустепень исхода или захода которых превышает единицу, и не появились негамильтоновы циклы. Однако, как легко убедиться, данный подход не гарантирует получение оптимального решения. В качестве простейшего контрпримера можно рассмотреть следующий граф.

Здесь каждому ребру соответствует две дуги такого же веса.

«Жадный алгоритм» прежде всего включит в цикл ребро , как имеющее минимальный вес. Включение этого ребра, как непосредственно легко проверить, необходимо ведет к гамильтонову циклу веса 29. Оптимальный

же гамильтонов цикл имеет вес 12. Поэтому «жадный алгоритм» не гарантирует получения оптимального решения, хотя он может быть использован на практике в качестве полезной эвристики, во многих случаях приводящей к решениям, близким к оптимальным.

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

Под методом «ветвей и границ» понимается широкий класс методов сокращенного перебора, суть которых сводится к следующему. Множество допустимых решений А разбивается на два подмножества А0 и А1, затем каждое из подмножеств также разбивается на два подмножества и т.д. Схематически это можно представить в виде дерева, начинающегося с множества всех решений и заканчивающегося его одноэлементными подмножествами, т.е. допустимыми решениями, которыми в нашем случае являются гамильтоновы циклы.

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

Рассмотрим метод «ветвей и границ» на примере задачи коммивояжера. Пусть взвешенный орграф задан матрицей расстояний. Если некоторая дуга в графе отсутствует, то соответствующий элемент матрицы будем полагать равным ∞. Заметим, что если длины всех дуг, входящих в некоторую вершину, уменьшить на одно и то же число, то и длина оптимального гамильтонова цикла уменьшится на это же число. То же самое относится и к множеству выходящих дуг. Будем последовательно вычитать из строк и столбцов матрицы расстояний положительные числа так, чтобы элементы матрицы оставались неотрицательными. Так как длина оптимального гамильтонова цикла для графа с неотрицательной матрицей расстояний также неотрицательна, то сумма вычтенных количеств будет нижней границей для длины оптимального цикла исходного графа.

Рассмотрим пример. Пусть задан граф G с симметрической матрицей расстояний.

  1 2 3 4 5
1 ∞
2 ∞
3 ∞
4 ∞
5 ∞

Значки « ∞ » на диагонали соответствуют отсутствию в графе петель – дуг, ведущих из вершины в эту же вершину. Получим, прежде всего, нижнюю границу для длины кратчайшего гамильтонового цикла. Из первой, второй, третьей и четвертой строк можно вычесть по единице, из пятой строки – два, а из пятого столбца можно вычесть ещё единицу. Это дает нижнюю границу 7, а матрица расстояний приобретает вид

  1 2 3 4 5
1 ∞
2 ∞
3 ∞
4 ∞
5 ∞

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

  1 2 3 4 5
1 ∞ ∞
2 ∞
3 ∞
4 ∞
5 ∞

из первой строки и второго столбца которой можно вычесть по единице, что увеличивает нижнюю границу на 2 и делает её равной 9.

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

  1 3 4 5
2 ∞
3 ∞
4 ∞
5 ∞

Из её первой строки и первого столбца можно вычесть по единице, что приводит к матрице

  1 3 4 5
2 ∞
3 ∞
4 ∞
5 ∞

Нижняя оценка здесь возрастает на 2 и также становится равной 9.

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

  1 3 5
2 ∞
4 ∞
5 ∞

Нижняя оценка длины оптимального цикла остается неизменной.

Далее, в соответствии с принятой стратегией, включаем в цикл дугу (5,1). Из матрицы удаляется строка, соответствующий вершине 1. Строящийся гамильтонов цикл принимает вид

 

 

Дуга (2,5) должна быть запрещена, как ведущая к появлению негамильтонова цикла, и матрица принимает вид

  3 5
2 ∞
4 ∞

Нижняя оценка длины гамильтонова цикла остается, по – прежнему, равной 9.

Включая далее в произвольном порядке дуги (2,3) и (4,5) получаем гамильтонов цикл длины 9.

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

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

 

Тест

1. Существует ли эффективный алгоритм для решения задачи коммивояжера? а) да; б) нет; в) неизвестно.

2. Является ли описанный метод « ветвей и границ» эффективным алгоритмом для решения задачи коммивояжера? а) да; б) нет; в) неизвестно.

3. Что следует вычитать из строки матрицы расстояний при получении нижней оценки длины гамильтонова цикла? а) минимальный элемент строки; б) максимальный элемент строки; в) произвольный элемент строки.