i>Шаг 3. Если вершина сочетается с другой вершиной, то определим цепь наименьшего веса (из), соответствующую весу , делая шаг 1. Добавим искусственные ребра в соответствующие ребрам из и проделаем это для всех других цепей из множества в результате чего получится -граф (М*).. Сумма весов всех ребер графа (М*). ,найденная с использованием матрицы (вес искусственного ребра берется равным весу параллельного ему реального ребра), равна минимальному весу цикла, проходящего по . При этом число прохождений цикла по ребру равно общему числу параллельных ребер между в (М*).Следует заметить, что поскольку на шаге 2 используется минимальное паросочетание, никакие две кратчайшие цепи и при таком паросочетании (скажем, идущие из и из в не могут иметь общего ребра.Рисунок 6. Цепи и ,имеющие общее ребро Если бы они имели общее ребро (), как показано на рисунке. 6 то сочетание вершин (использующее подцепи от ) и сочетание пары вершин (использующее подцепи от ) давало бы общее паросочетание веса, меньшего чем вес первоначального паросочетания, что противоречит предположению о минимальности исходного паросочетания. Следовательно, граф (М*).не должен содержать более двух параллельных ребер между любыми двумя вершинами, т. е. оптимальный цикл не проходит ни по какому ребру графа G более чем два раза.Коротко данный алгоритм можно записать:1. В исходном графе Г' находятся все вершины нечетной степени, если таковыхнетто пункт 6. 2. Для каждой такой вершины находятся кратчайшие пути до всех остальных, эти пути запоминаются. 3. На этих вершинах строится двудольный граф Г' с весами, равными кратчайшему расстоянию 4.Ищем максимальное паросочетание минимального веса. 5. По паросочетанию добавляем в исходный граф дополнительные ребра. Т.е. если у нас в паросочетании Г' есть ребро (A,B), то в Г добавляется цепь кратчайшего пути между вершинами А и В. Получаем эйлеров граф.
6.Находимэйлерову цепь. Для реализации данного алгоритма нам необходимо реализовать три алгоритма:· Алгоритм Дейкстры( пункт 2) · Венгерский алгоритм (пункт 4) · Алгоритм Флёри (пункт 6) 1.6.2 Алгоритм ДейкстрыАлгоритм Демйкстры (Dijkstra's algorithm) -- алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов.Обозначения V -- множество вершин графа E -- множество ребер графа w[ij] -- вес (длина) ребра ij a -- вершина, расстояния от которой ищутся U -- множество посещенных вершин d[u] -- по окончании работы алгоритма равно длине кратчайшего пути из a до вершины u p[u] -- по окончании работы алгоритма содержит кратчайший путь из a в u Псевдокод Присвоим Для всех отличных от a присвоим Пока Пусть -- вершина с минимальным Для всех таких, что если то изменим изменим Описание В простейшей реализации для хранения чисел можно использовать массив чисел, а для хранения принадлежности элемента множеству -- массив булевых переменных. В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом (большим максимального возможного пути вграфе). Массив флагов заполняется нулями. Затем запускается основной цикл. На каждом шаге цикла мы ищем вершину с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0 . Последний случай возможен тогда и только тогда, когда граф не связан. 1.6.3 Венгерский алгоритмВенгерский алгоритм -- алгоритм оптимизации, решающий задачу о назначениях за полиномиальное время (см. исследование операций). Он был разработан и опубликован Харолдом Куном в 1955 году. Автор дал ему имя «венгерский метод» в связи с тем, что алгоритм в значительной степени основан на более ранних работах двух венгерских математиков (Кёнига и Эгервари). Джеймс Манкрес в 1957 году заметил, что алгоритм является (строго) полиномиальным. С этого времени алгоритм известен также как алгоритм Куна -- Манкреса или алгоритм Манкреса решения задачи о назначениях. Временная сложность оригинального алгоритма была O(n4), однако Эдмондс и Карп (а также Томидзава независимо от них) показали, что его можно модифицировать так, чтобы достичь времени выполнения O(n3). Форд и Фалкерсон распространили метод на общие транспортные задачи. В 2006 году было обнаружено, что Якоби нашёл решение задачи о назначениях в XIX веке и опубликовал его в 1890 году на латыни. Так как алгоритм сложен для понимания. В данной работе он будет рассмотрен на примере, через матричную инетерпритацию. Матричная интерпретация Для n работников и работ, дана матрица, задающая стоимость выполнения каждой работы каждым работником. Найти минимальную стоимость выполнения работ, такую что каждый работник выполняет ровно одну работу, а каждую работу выполняет ровно один работник. В дальнейшем мы под назначением понимаем соответствие между работниками и работами, имеющее нулевую стоимость, после того как мы произвели трансформации, влияющие лишь на общую стоимость работ. Прежде всего запишем задачу в матричной форме: где a, b, c, d -- работники, которые должны выполнить работы 1, 2, 3, 4. Коэффициенты a1, a2, a3, a4 обозначают стоимость выполнения работником «a» работ 1, 2, 3, 4 соответственно. Аналогичный смысл имеют остальные символы. Матрица квадратная, поэтому каждый работник может выполнить только одну работу. Шаг 1 Уменьшаем элементы построчно. Находим наименьший из элементов первой строки (а1, а2, а3, а4), и вычитаем его из всех элементов первой строки. При этом хотя бы один из элементов первой строки обнулится. То же самое выполняем и для всех остальных строк. Теперь в каждой строке матрицы есть хотя бы один ноль. Иногда нулей уже достаточно, чтобы найти назначение. Пример показан в таблице. Красные нули обозначают назначенные работы. |
0 | a2' | 0 | a4' | | b1' | b2' | b3' | 0 | | 0 | c2' | c3' | c4' | | d1' | 0 | d3' | d4' | | |
При большом количестве нулей для поиска назначения (нулевой стоимости) можно использовать алгоритм нахождения максимального паросочетания двудольных графов, например алгоритм Хопкрофта-Карпа. Кроме того, если хотя бы в одном столбце нет нулевых элементов, то назначение невозможно. Шаг 2 Часто на первом шаге нет назначения, как, например, в следующем случае: |
0 | a2' | a3' | a4' | | b1' | b2' | b3' | 0 | | 0 | c2' | c3' | c4' | | d1' | 0 | d3' | d4' | | |
Задача 1 может быть эффективно (за нулевую стоимость) выполнена как работником a, так и работником c, зато задача 3 не может быть эффективно выполнена никем. В таких случаях мы повторяем шаг 1 для столбцов и вновь проверяем, возможно ли назначение. Шаг 3 Во многих случаях мы достигнем желаемого результата уже после шага 2. Но иногда это не так, например: |
0 | a2' | a3' | a4' | | b1' | b2' | b3' | 0 | | 0 | c2' | c3' | c4' | | d1' | 0 | 0 | d4' | | |
Если работник d выполняет работу 2, некому выполнять работу 3, и наоборот. В таких случаях мы выполняем процедуру, описанную ниже. Сначала, используя любой алгоритм поиска максимального паросочетания в двудольном графе, назначаем как можно больше работ тем работникам, которые могут их выполнить за нулевую стоимость. Пример показан в таблице, назначенные работы выделены красным. |
0 | a2' | a3' | a4' | | b1' | b2' | b3' | 0 | | 0 | c2' | c3' | c4' | | d1' | 0 | 0 | d4' | | |
Отметим все строки без назначений (строка 1). Отметим все столбцы с нулями в этих строках (столбец 1). Отметим все строки с нулями в этих столбцах (строка 3). Продолжаем, пока новые строки и столбцы не перестали отмечаться. |
Ч | | | | | | 0 | a2' | a3' | a4' | Ч | | b1' | b2' | b3' | 0 | | | 0 | c2' | c3' | c4' | Ч | | d1' | 0 | 0 | d4' | | | |
Теперь проводим линии через все отмеченные столбцы и неотмеченные строки. |
Ч | | | | | | 0 | a2' | a3' | a4' | Ч | | b1' | b2' | b3' | 0 | | | 0 | c2' | c3' | c4' | Ч | | d1' | 0 | 0 | d4' | | | |
Все эти действия преследовали лишь одну цель: провести наименьшее количество линий (вертикалей и горизонталей), чтобы покрыть все красные нули. Можно было воспользоваться любым другим методом вместо описанного. Шаг 4 Из непокрытых линиями элементов матрицы (в данном случае это a2', a3', a4', c2', c3', c4') найти наименьший. Вычесть его из всех не отмеченных строк и прибавить ко всем пересечениям отмеченных строк и столбцов. Так, например, если наименьший элемент из перечисленных равен а2', мы получим |
Ч | | | | | | 0 | 0 | a3'-а2' | a4'-a2' | Ч | | b1'+a2' | b2' | b3' | 0 | | | 0 | c2'-а2' | c3'-а2' | c4'-а2' | Ч | | d1'+a2' | 0 | 0 | d4' | | | |
Страницы: 1, 2, 3, 4
|
