Кратчайший путь между двумя вершинами.
Пусть задан взвешенный ориентированный граф , неотрицательные веса на дугах которого будем интерпретировать как расстояния от вершины до вершины . Длиной пути называется сумма длин составляющих путь дуг. Требуется найти кратчайший путь из вершины в вершину .
Алгоритм Дейкстры для нахождения кратчайшего пути (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. Что следует вычитать из строки матрицы расстояний при получении нижней оценки длины гамильтонова цикла? а) минимальный элемент строки; б) максимальный элемент строки; в) произвольный элемент строки.