Xreferat.com » Рефераты по информатике и программированию » Эйлеровы и гамильтоновы графы

Эйлеровы и гамильтоновы графы

100.155n (секунд на CDC6600).

Улучшенный вариант алгоритма Робертса и Флореса не намного лучше первоначального алгоритма. Необходимое время вычисления в нем все еще зависит (более или менее) экспоненциально от n. Зависимость отношения времен вычисления при использовании этих двух алгоритмов для неориентированных графов со степенями вершин 3 — 5 приведена на рисунке 2. Из этого рисунка видно, что «улучшенный» вариант в действительности хуже для графов малых размеров, хотя для больших графов (с более чем 20 вершинами) он позволяет сэкономить более 50% времени вычисления.

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

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

Кроме того, эксперименты показывают, что для графов, степени вершин которых лежат в вышеприведенных пределах 3 — 5, метод по существу не чувствителен к степеням вершин. Вычислительные результаты, показанные на рисунках 1-3, относятся к поиску одного гамильтонова цикла в графе.

Небезынтересно сказать несколько слов о вычислениях с тремя алгоритмами, когда искались все гамильтоновы циклы. Так, для неориентированного графа с 20 вершинами со степенями вершин 3 — 5, потребовалось 2 сек, чтобы найти все гамильтоновы циклы, следуя

Рис.1 Вычислительная реализация алгоритма Робертса и Флореса

Рис.2 Реализация улучшенного алгоритма Робертса и Флореса

Время вычисления: T0-основной алгоритм, T1-улучшенный алгоритм

алгоритму Робертса и Флореса (этих циклов оказалось 18). Улучшенный вариант того же алгоритма потребовал 1.2 сек, а мультицепной алгоритм — 0.07 сек. Вычисления проводились на ЭВМ CDC6600.

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


Задача коммивояжера (в дальнейшем сокращённо - ЗК) является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великую теорему Ферма обламывали зубы лучшие математики. В своей области (оптимизации дискретных задач) ЗК служит своеобразным полигоном, на котором испытываются всё новые методы. Ниже будет показано, что решение ЗК методом полного перебора оказывается практически неосуществимым даже для сравнительно небольших задач. Более того, известно, что ЗК принадлежит к числу NP-полных задач.


§1. Общее описание


Постановка задачи следующая.

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по одному разу в неизвестном порядке города 1,2,3..n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Чтобы привести задачу к научному виду, введём некоторые термины. Итак, города перенумерованы числами jТ=(1,2,…,n). Тур коммивояжера может быть описан циклической перестановкой t=(j1,…,jn, j1), причём все j1,…,jn – разные номера; повторяющийся в начале и в конце j1, показывает, что перестановка зациклена. Расстояния между парами вершин Сij образуют матрицу С. Далее введем n2 альтернативных переменных xij, принимающих значение 0, если переход из i-го пункта в j-ый не входит в маршрут и 1 в противном случае. Условия прибытия в каждый пункт и выхода из каждого пункта только по одному разу выражаются равенствами (1) и (2).

(1)

(2)

Для обеспечения непрерывности маршрута вводятся дополнительно n переменных и n2 дополнительных ограничений (3).

(3)

Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать суммарную протяженность маршрута F, которая запишется в следующем виде:

(4)

Относительно математической формулировки ЗК уместно сделать два замечания. Первое, в постановке Сij означали расстояния, поэтому должны выполняться следующие условия:

    • неотрицательными, т.е. для всех jТ:

Cij 0;

Cjj = ∞ (5)

(последнее равенство означает запрет на петли в туре),

    • симметричными, т.е. для всех i, j:

Сij = Сji (6)

    • удовлетворять неравенству треугольника, т.е. для всех:

Cij + Cjk Cik (7)

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (5)-(7) не удовлетворяют. Особенно часто нарушается условие (7) (например, если Сij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому мы будем различать два варианта ЗК: симметричную задачу, когда условие (7) выполнено, и несимметричную - в противном случае. Условия (5)-(7) по умолчанию мы будем считать выполненными.

Второе замечание касается числа всех возможных туров. В несимметричной ЗК все туры t=(j1,j2,…,jn,j1) и t’=(j1,jn,…,j2,j1) имеют разную длину и должны учитываться оба. Всего разных туров очевидно (n-1)!

Зафиксируем на первом и последнем месте в циклической перестановке номер j1, а оставшиеся n-1 номеров переставим всеми (n-1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t’.

Можно представить, что X состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j) проведено, если xij=0 и не проведено, если xij=1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём).

Доказательство, что модель (1-4) описывает задачу о коммивояжере.

Условие (2) означает, что коммивояжер из каждого города выезжает только один раз; условие (3) - въезжает в каждый город только один раз; условие (4) - обеспечивает замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутренних петель.

Рассмотрим условие (4) подробнее. Применим метод доказательства от противного, то есть предположим, что условие (4) выполняется для некоторого подцикла T из R городов, где R

.

Так как

,

то N·R (N -1), где R < N, R 0.

Следовательно, не существует замкнутого подцикла с числом городов меньшим, чем N.

Покажем, что существует Ui, которое для замкнутого цикла, начинающегося в некотором начальном пункте, удовлетворяют условию (4). При всех Xij (j-й город не посещается после i-го) в (4) имеем Ui-Uj N-1, что допустимо в силу произвольных Ui и Uj.

Пусть на некотором R-ом шаге i-й город посещается перед j-м, то есть Xij = 1. В силу произвольности значений Ui и Uj положим Ui = R, а Uj = R+1, тогда из (4) имеем:

Ui-Uj+N·Xij R-(R-1)+N = N-1

Итак, существуют такие конечные значения для Ui и Uj, что для маршрута, содержащего N городов, условие (4) удовлетворяется как неравенство или строгое равенство. А следовательно, модель (1)-(4) описывает задачу о коммивояжере.

В терминах теории графов симметричную ЗК можно сформулировать так:

Дана полная сеть с n вершинами, длина ребра (i,j)= Сij. Найти гамильтонов цикл минимальной длины.

В несимметричной ЗК вместо «цикл» надо говорить «контур», а вместо «ребра» - «дуги», «стрелки».

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


§2. “Жадный” алгоритм решения ЗК


Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. “Жадным” этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.

Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь алгоритм превратится в стратегию “иди в ближайший, в который еще не входил, город”. Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рис. 2, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди вы ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

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

Как видим, жадный алгоритм ошибается. Можно ли доказать, что он ошибается умеренно, что полученный им тур хуже минимального, положим, в 1000 раз? Мы докажем, что этого доказать нельзя, причем не только для жадного алгоритма, а для алгоритмов го­раздо более мощных. Но сначала нужно договориться, как оценивать погрешность неточных алгоритмов, для определенности, в задаче минимизации. Пусть fB - настоящий минимум, а fA - тот квазиминимум, который получен по алгоритму. Ясно, что fA/ fB≥1, но это – тривиальное утверждение, что может быть погрешность. Чтобы оценить её, нужно «зажать» отношение оценкой сверху:

fA/fB ≥ 1+nε (8)

где, как обычно в высшей математике, ε≥0, но, против обычая, может быть очень большим. Величина ε и будет служить мерой погрешности. Если алгоритм минимизации будет удовлетворять неравенству (8), мы будем говорить, что он имеет погрешность ε.

Предположим теперь, что имеется алгоритм А решения ЗК, погрешность которого нужно оценить. Возьмем произвольный граф G(V,E) и по нему составим входную матрицу ЗК:

С[i,j]={ 1, если ребро (i,j) принадлежит Е
1+nε, в противном случае
Если в графе G есть гамильтонов цикл, то минимальный тур проходит по этому циклу и fB = n. Если алгоритм А тоже всегда будет находить этот путь, то по результатам алгоритма можно судить, есть ли гамильтонов цикл в произвольном графе. Однако, не переборного алгоритма, который мог бы ответить, есть ли гамильтонов цикл в произвольном графе, до сих пор никому не известно. Таким образом, наш алгоритм А должен иногда ошибаться и включать в тур хотя бы одно ребро длины 1+nε. Но тогда fA (n-1)+(1+nε) так что fA/fB = 1+nε, т.е. превосходит погрешность ε на заданную неравенством (8). О величине ε в нашем рассуждении мы не договаривались, так что ε может быть произвольно большим.

Таким образом доказана следующая теорема.

Либо алгоритм А определяет, существует ли в произвольном графе гамильтонов цикл, либо погрешность А при решении ЗК может быть произвольно велика.

Это соображение было впервые опубликовано Сани и Гонзалесом в 1980 г. Теорема Сани-Гонзалеса основана на том, что нет никаких ограничений на длину ребер. Теорема не проходит, если расстояния подчиняются неравенству треугольника (7).


§3. “Деревянный” алгоритм решения ЗК


Теперь можно обсудить алгоритм решения ЗК через построение кратчайшего остовного дерева. Для краткости будет называть этот алгоритм “деревянным”.

Вначале обсудим свойство спрямления. Рассмотрим какую-нибудь цепь, например, на рис. 5. Если справедливо неравенство треугольника, то d[1,3] d[1,2]+d[2,3] и d[3,5] d[3,4]+d[4,5]. Сложив эти два неравенства, получим:

d[1,3]+d[3,5]d[1,2]+d[2,3]+d[3,4]+d[4,5].

По неравенству треугольника получим: d[1,5] d[1,3]+d[3,5]. Окончательно,

d[1,5] d[1,2]+d[2,3]+d[3,4]+d[4,5]

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

Вернемся к ЗК и опишем решающий ее “деревянный” алгоритм.

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

  2. Построим эйлеров цикл в G, начиная с вершины 1, цикл задается перечнем вершин.

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

Пример 1. Дана полная сеть, показанная на рис.5. Найти тур “жадным” и “деревянным” алгоритмами.

Решение.

1. “Жадный” алгоритм (иди в ближайший город из города 1) дает тур 1–(4)–3-(3)–5-(5)–4–(11)–6–(10)–2–(6)–1, где без скобок показаны номера вершин, а в скобках – длины ребер. Длина тура равна 39, тур показана на рис. 5.

2. “Деревянный” алгоритм вначале строит остовное дерево, показанное на рис. 6 штриховой линией, затем эйлеров цикл 1-2-1-3-4-3-5-6-5-3-1, затем тур 1-2-3-4-5-6-1 длиной 43, который показан сплошной линией на рис. 6.

Теорема. Погрешность “деревянного” алгоритма равна 1.

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

fB > LHC LMT (9)


—

1

2

3

4

5

6

1

— 6 4 8 7 14

2

6 — 7 11 7 10

3

4 7 — 4 3 10

4

8 11 4 — 5 11

5

7 7 3 5 — 7

6

14 10 10 11 7 —
Но удвоенное дерево – оно же эйлеров граф – мы свели к туру посредством спрямлений, следовательно, длина полученного по алгоритму тура удовлетворяет неравенству 2LMT > fA (10)

Умножая (9) на два и соединяя с (10), получаем цепочку неравенств

2fB > 2LHC 2LMT fA (11)

Т.е. 2fB>fA, fA/fB>1+; =1. Теорема доказана.

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


§4. Метод лексикографического перебора


Известно еще несколько простых алгоритмов, гарантирующих в худшем случае =1. Для того, чтобы найти среди них алгоритм поточнее, зайдем с другого конца и для начала опишем “brute-force enumeration” - “перебор грубой силой”, как его называют в англоязычной литературе. Понятно, что полный перебор практически применим только в задачах малого размера. Напомним, что ЗК с n городами требует при полном переборе рассмотрения (n-1)!/2 туров в симметричной задаче и (n-1)! Туров в несимметричной, а факториал, как показано в следующей таблице, растет удручающе быстро:

5! 10! 15! 20! 25! 30! 35! 40! 45! 50!

~102

~106

~1012

~1018

~1025

~1032

~1040

~1047

~1056

~1064

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

Говорят, что перестановка (a1,…,an) лексикографически предшествует перестановке (b1,…,bn), если существует k ≤ n ak < bk и для любого i > k ai = bi.

Пусть имеется некоторый алфавит и наборы символов алфавита (букв), называемые словами. Буквы в алфавите упорядочены: например, в русском алфавите порядок букв абя (символ читается “предшествует”). Если задан порядок букв, можно упорядочить и слова. Скажем, дано слово u=(u1,u2,…,um) – состоящее из букв u1,u2,…,um — и слово v=(v1,v2,…,vb). Тогда если u1v1, то и uv, если же u1=v1, то сравнивают вторые буквы и т.д. Этот порядок слов и называется лексикографическим. Рассмотрим, скажем, перестановки из пяти элементов, обозначенных цифрами 1…5. Лексикографически первой перестановкой является 1-2-3-4-5, второй 1-2-3-5-4,… ,последней 5-4-3-2-1. Нужно осознать общий алгоритм преобразования любой перестановки в непосредственно следующую за ней.

Правило такое: скажем, дана перестановка 1-3-5-4-2. Нужно двигаться по перестановке справа налево, пока впервые не увидим число, меньшее, чем предыдущее (в примере это 3 после 5). Это число, Pi-1 надо увеличить, поставив вместо него какое-то число из чисел, расположенных правее, от Pi до Pn. Число большее, чем Pi-1, несомненно, найдется, так как Pi-1 < Pi. Если есть несколько больших чисел, то, очевидно, надо ставить меньшее из них. Пусть это будет Pj, j > i-1. Затем число Pi-1 и все числа от Pi до Pn, не считая Pj нужно упорядочить по возрастанию. В результате получится непосредст­венно следующая перестановка, в примере — 1-4-2-3-5. Потом получится 1-4-2-5-3 (тот же алгоритм, но упрощенный случай) и т.д.

Нужно понимать, что в ЗК с n городами не нужны все переста­новки из n элементов. Потому что перестановки, скажем, 1-3-5-4-2 и 3-5-4-2-1 (последний элемент соединен с первым) задают один и тот же тур, считанный сперва с города 1, а потом с города 3. Поэтому нужно зафиксировать начальный город 1 и присоединять к нему все перестановки из остальных элементов. Этот перебор даст (n-1)! разных туров, т.е. полный перебор в несимметричной ЗК (мы по-прежнему будем различать туры 1-3-5-4-2 и 1-2-4-5-3).

Если мы решим, поставленную в примере 1 задачу коммивояжера, методом лексикографического перебора, то получим следующий тур 1-2-6-5-4-3-1 длиной 36.


§5. Метод ветвей и границ решения ЗК


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

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

Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.

Входные данные.

Алгоритм метода ветвей и границ предназначен для нахождения минимального гамильтонова контура на графе с N вершинами. В матрице расстояний задачи коммивояжера если между вершинами i и j нет дуги, то ставится символ "бесконечность". Этот же символ ставится по диагонали, что означает запрет на возвращение в вершину, через которую уже проходил контур.

Идея алгоритма.

Основная идея метода состоит в том, что вначале строят нижнюю границу длин множества гамильтоновых контуров ω0. Затем множество контуров разбивается на два подмножества таким образом, чтобы первое подмножество ω1ij состояло из гамильтоновых контуров, содержащих некоторую дугу (i,j), а другое подмножество ω1not ij не содержало этой дуги. Для каждого из подмножеств определяются нижние границы по тому же правилу, что и для первоначального множества гамильтоновых контуров. Полученные нижние границы подмножеств ω1ij и ω1not ij оказываются не меньше нижней границы всего множества гамильтоновых контуров, т.е.

Ф(ω0)<=Ф1ij,

Ф(ω0)<=Ф1not ij

Сравнивая нижние границы Ф1ij и Ф1not ij, можно выделить среди них то, которое с большей вероятностью содержит гамильтонов контур минимальной длины.

Затем одно из подмножеств ω1ij или ω1not ij по аналогичному правилу разбивается на два новых ω2ij и ω2ij. Для них снова отыскиваются нижние границы Ф2ij и Ф2not ij и т.д. Процесс ветвления продолжается до тех пор, пока не отыщется единственный гамильтонов контур. Его называют первым рекордом. Затем просматривают оборванные ветви. Если их нижние границы больше длины первого рекорда, то задача решена. Если же есть такие, для которых нижние границы меньше, чем длина первого рекорда, то подмножество с наименьшей нижней границей подвергается дальнейшему ветвлению, пока не убеждаются, что оно не содержит лучшего гамильтонова контура.

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

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

Определение нижних границ

Если к элементам любого ряда матрицы задачи коммивояжера (строке или столбцу) прибавить или вычесть из них некоторое число, то от этого оптимальность плана не изменится. Длина же любого гамильтонова контура изменится на данную величину.

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

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

Разбиение множества контуров на подмножества

Для выделения претендентов на включение в множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы, равные нулю. Найдем степени θij нулевых элементов этой матрицы. Степень нулевого элемента cij равна сумме минимальных элементов в строке i и столбце j при блокировании перехода (i,j) бесконечностью. С наибольшей вероятностью искомому гамильтонову контуру принадлежат дуги с максимальной степенью нуля.

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

Множество контуров, не включающих дугу (i,j) получаем путем замены элемента cij на бесконечность.

- 1 2 3 4 5 6
1 - 0 0 3 3 6
2 0 - 1 4 1 0
3 1 2 - 0 0 3
4 4 5 0 - 1 3
5 4 2 0 1 - 0
6 7 1 3 3 0 -


2
1
4
табл. 4
- 1 2 3 4 5 6
1 - 2 0 4 3 10 4
2 0 - 1 5 1 4 6
3 1 4 - 1 0 7 3
4 4 7 0 - 1 7 4
5 4 4 0 2 - 4 3
6 7 3 3 4 0 - 7
табл. 3
- 1 2 3 4 5 6
1 - 6 4 8 7 14
2 6 - 7 11 7 10
3
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: