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

момента, когда либо получается гамильтонов цикл, либо становится ясно, что

эта цепь не может привести к гамильтонову циклу. Тогда цепь модифицируется

некоторым систематическим способом (который гарантирует, что в конце концов

будут исчерпаны все возможности), после чего продолжается поиск

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

объем памяти и за один раз находится один гамильтонов цикл.

Следующая схема перебора, использующая обычную технику возвращения,

была первоначально предложена Робертсом и Флоресом. Начинают с построения

(kЧn)-матрицы M=[mij], где элемент mij есть i-я вершина (скажем xq), для

которой в графе G(X,Г) существует дуга (xj,xq). Вершины xq во множестве

Г(xj) можно упорядочить произвольно, образовав элементы j-го столбца

матрицы M. Число строк k матрицы M будет равно наибольшей полустепени

исхода вершины.

Метод состоит в следующем. Некоторая начальная вершина (скажем, x1)

выбирается в качестве отправной и образует первый элемент множества S,

которое каждый раз будет хранить уже найденные вершины строящейся цепи. К S

добавляется первая вершина (например, вершина a) в столбце x1. Затем к

множеству S добавляется первая возможная вершина (например, вершина b) в

столбце a, потом добавляется к S первая возможная вершина (например,

вершина c) в столбце b и т.д. Под «возможной» вершиной мы понимаем вершину,

еще не принадлежащую S. Существуют две причины, препятствующие включению

некоторой вершины на шаге r во множество S = {x1,a,b,c, … ,xr-1,xr}:

В столбце xr нет возможной вершины.

Цепь, определяемая последовательностью вершин в S, имеет длину n-1, т.е.

является гамильтоновой цепью.

В случае 2) возможны следующие случаи:

В графе G существует дуга (xr,x1), и поэтому найден гамильтонов цикл.

Дуга (xr,x1) не существует и не может быть получен никакой гамильтонов

цикл.

В случаях (1) и (2b) следует прибегнуть к возвращению, в то время как

в случае (2a) можно прекратить поиск и напечатать результат (если требуется

найти только один гамильтонов цикл), или (если нужны все такие циклы)

произвести печать и прибегнуть к возвращению.

Возвращение состоит в удалении последней включенной вершины xr из S,

после чего остается множество S = {x1,a,b,c, … ,xr-1}, и добавлении к S

первой возможной вершины, следующей за xr, в столбце xr-1 матрицы M. Если

не существует никакой возможной вершины, делается следующий шаг возвращения

и т.д.

Поиск заканчивается в том случае, когда множество S состоит только из

вершины x1 и не существует никакой возможной вершины, которую можно

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

Гамильтоновы циклы, найденные к этому моменту, являются тогда всеми

гамильтоновыми циклами, существующими в графе.

Рассмотрим пример поиска гамильтонова цикла в графе переборным методом

Робертса и Флореса.

Пример:

[pic]

"2"

1) S = {1}

2) S = {1, 2}

3) S = {1, 2, 3}

4) S = {1, 2, 3, 4}

5) S = {1, 2, 3, 4, 5} - Г 4>3 4>5

6) S = {1, 2, 3, 4}

7) S = {1, 2, 3} 3>1 3>2 3>4

8) S = {1, 2}

9) S = {1}

"3"

10) S = {1, 3} 3>2

11) S = {1, 3, 2} 2>1

12) S = {1, 3} 2>3

13) S = {1, 3, 4} 3>4 4>5

14) S = {1, 3, 4, 5, 4} 5>нет

15) S = {1, 3, 4}

16) S = {1, 3}

17) S = {1}

"5"

18) S = {1, 5}

19) S = {1, 5, 4}

20) S = {1, 5, 4, 3}

21) S = {1, 5, 4, 3, 2} - Г

22) S = {1, 5, 4, 3}

23) S = {1, 5, 4}

24) S = {1, 5}

25) S = {1}

26) S = Ш

§8. Улучшение метода Робертса и Флореса

Рассмотрим улучшение основного переборного метода Робертса и Флореса.

Допустим, что на некотором этапе поиска построенная цепь задается

множеством S = {x1,x2, … ,xr} и что следующей вершиной, которую

предполагается добавить к S, является x*[pic]S. Рассмотрим теперь две

следующие ситуации, в которых вершина является изолированной в подграфе,

остающемся после удаления из G(X,Г) всех вершин, образующих построенную до

этого цепь.

Если существует такая вершина x[pic]X\S, что x[pic]Г(xr) и Г-1(x)[pic] S,

то, добавляя к S любую вершину x*, отличную от x, мы не сможем в

последующем достигнуть вершины x ни из какой конечной вершины построенной

цепи, и, значит, эта цепь не сможет привести нас к построению гамильтонова

цикла. Таким образом, в этом случае x является единственной вершиной,

которую можно добавить к S для продолжения цепи.

Если существует такая вершина x[pic]X\S, что x[pic]Г-1(x1) и Г(x)[pic]

S[pic]{x*} для некоторой другой вершины x*, то x* не может быть добавлена к

S, так как тогда в остающемся подграфе не может существовать никакой цепи

между x и x1. Цепь, определяемая множеством S [pic] {x*}, не может поэтому

привести к гамильтонову циклу, а в качестве кандидата на добавление к

множеству S следует рассмотреть другую вершину, отличную от x*.

Проверка условий (a) и (b) будет, конечно, замедлять итеративную

процедуру, и для небольших графов (менее чем с 20 вершинами) не получается

никакого улучшения первоначального алгоритма Робертса и Флореса. Но для

больших графов эта проверка приводит к заметному сокращению необходимого

времени вычислений, уменьшая его обычно в 2 или более раз.

§9. Мультицепной метод

После внимательного изучения операций алгоритма перебора Робертса и

Флореса становится очевидным, что даже после сделанного улучшения не

слишком много внимания уделяется оставшейся части графа, в которой берется

последовательность вершин, продолжающих построенную цепь. Обычно построение

цепи S0 в процессе поиска (S0 рассматривается и как упорядоченное множество

вершин, и как обычное множество) подразумевает существование еще каких-то

цепей в других частях графа. Эти предполагаемые цепи либо помогают быстрее

построить гамильтонов цикл, либо указывают на отсутствие такого цикла,

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

Метод, описанный ниже, был предложен первоначально для

неориентированных графов; здесь дается его небольшое видоизменение для

ориентированных графов. Метод состоит в следующем.

Допустим, что на некотором этапе поиска построена цепь S0 и возможны

цепи S1, S2, … . Рассмотрим какую-либо «среднюю» вершину одной из этих

цепей (слово «средняя» здесь означает любую вершину, отличную от начальной

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

то очевидно, что все другие дуги, входящие или выходящие из такой вершины,

могут быть удалены из графа. Для любой начальной вершины вышеуказанных

цепей можно удалить все дуги, исходящие из нее (за исключением дуги,

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

все дуги, оканчивающиеся в ней (опять-таки за исключением дуги, включающей

ее в цепь). Кроме того, за исключением случая, когда существует только одна

цепь (скажем, S0), проходящая через все вершины графа G (т.е когда S0 —

гамильтонова цепь), любая имеющаяся дуга, ведущая из конца любой цепи в

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

замыкает не гамильтоновы циклы.

Удаление всех этих дуг даст граф — со всеми «средними» вершинами

цепей, в котором только одна дуга оканчивается в каждой вершине и только

одна дуга исходит из нее. Все эти «средние» вершины и дуги, инцидентные им,

удаляются из G, а вместо них для каждой цепи вводится единственная дуга,

идущая от начальной вершины цепи до ее конечной вершины. В результате всего

этого получается редуцированный граф Gk(Xk,Гk), где k — индекс,

показывающий номер шага поиска.

Рассмотрим теперь продолжение цепи S0 (сформированной в результате

поиска), осуществляемое путем добавления вершины xj, которая является

возможной в смысле алгоритма Робертса и Флореса, т.е. в Gk существует дуга,

исходящая из конечной вершины цепи S0 — обозначим эту вершину e(S0) — и

входящая в вершину xj. Добавление xj к S0 осуществляется так:

Сначала удаляются из Gk все необходимые дуги, т.е.

a) все дуги, оканчивающиеся в xj или исходящие из e(S0), за исключением

дуги (e(S0), xj);

b) все дуги, выходящие из xj в начальную вершину пути S0;

c) если окажется, что xj является начальной вершиной другой цепи Sj, то

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

начальную вершину цепи S0.

Обозначим граф, оставшийся после удаления всех дуг, через G’k(Xk,Гk’).

Если существует вершина x в графе G’k, не являющаяся конечной ни для

одной из цепей S0, S1, … и которая после удаления дуг имеет полустепень

захода, равную единице, т.е. |Г-1k’(x)|=1, то выкинуть все дуги, исходящие

из вершины v= Г-1k’(x), за исключением дуги (v, x).

Если существует вершина x графа G’k, не являющаяся начальной ни для

какой цепи и которая после удаления дуг имеет полустепень исхода, равную

единице, т.е. |Гk’(x)|=1, то выкинуть все дуги, исходящие из вершины x, за

исключением дуги (x, Гk’(x)).

Перестроить все цепи и удалить дуги, ведущие из конечных в начальные

вершины.

Повторить шаг 2 до тех пор, пока можно удалять дуги.

Удалить из оставшегося графа G’k все вершины, полустепени захода и исхода

которых равны единице, т.е. вершины, которые стали теперь «средними»

вершинами цепей. Это удаление производится так, как это было описано выше,

в результате чего получается новый редуцированный граф Gk+1, заменяющий

предыдущий граф Gk.

Совершенно очевидно, что если добавление вершины xj к цепи S0 делает

полустепень захода или полустепень исхода (или обе) некоторой вершины x в

конце шага 2 равной нулю, то не существует никакого гамильтонова цикла. В

этом случае вершина xj удаляется из множества S0 и в качестве другой

вершины xj, позволяющей продолжить цепь S0, выбирается некоторая другая

вершина из множества Гk’[e(S0)]. И так до тех пор, пока не будет исчерпано

все множество Гk’[e(S0)] и придется прибегнуть к возвращению (т.е. e(S0)

удаляется из S0 и заменяется другой вершиной и т.д.). Отметим, что операция

возвращения предполагает хранение достаточной информации об удаленных дугах

в шагах 1 и 2 на каждом этапе k, чтобы можно было по графу Gk+1

восстановить граф Gk при любых k, если приходится прибегать к возвращению.

Если (на некотором этапе) в конце шага 2 установлено, что только одна

цепь проходит далее через все вершины, то в этом случае существование

гамильтонова цикла может быть выявлено непосредственно. Если цикл при этом

не найден (или если он найден, но надо найти все гамильтоновы циклы), то

нужно прибегнуть к возвращению.

Лучший вычислительный путь состоит в том, чтобы при каждой итерации

шага 2 (за исключением последней) проверять отличие от нуля полустепеней

захода и исхода всех вершин графа G’k. Поэтому как только одна из них

станет равной нулю, сразу же применяется операция возвращения, и если

найдена гамильтонова цепь, то получается и гамильтонов цикл без проверки

существования дуги возврата.

Если не возникает ни один из вышеупомянутых случаев, т.е. если (на

некотором этапе k) в конце шага 2 остается более чем одна цепь и все

полустепени являются ненулевыми, то нельзя еще сделать никаких выводов.

Тогда вершина xj добавляется к S0 и выбирается другая вершина для

дальнейшего продолжения цепи. Шаги 1, 2, 3 повторяются, начиная с нового

редуцированного графа.

§10. Сравнение методов поиска гамильтоновых циклов

В этом параграфе сравниваются первоначальный вариант алгоритма

Робертса и Флореса, его улучшенный вариант и мультицепной метод. Эти три

метода мы будем сравнивать по необходимому времени вычислений для

нахождения одного гамильтонова цикла, если таковой существует, или

доказательства его отсутствия. Проверка была проведена на случайно

выбранных графах, степени вершин которых лежат в предписанных границах.

Всего было использовано около 200 графов, для которых приводятся средние

результаты. Во всех графах оказались гамильтоновы циклы.

Ниже на рисунке 1 показана зависимость требуемого алгоритмом Робертса

и Флореса времени вычисления от числа вершин графа; степени вершин лежат в

пределах 3 — 5. Ввиду сильных вариаций требуемого времени для графов

одинаковых размеров приводятся три ломанные, характеризующие среднее,

максимальное и минимальное время, полученное для различных графов с

одинаковым числом вершин. Следует заметить, что на рисунке 1 применен

полулогарифмический масштаб, что говорит об экспоненциальном характере

зависимости. Формула, дающая приближенную зависимость времени T от числа

вершин n графа со степенями вершин в пределах 3 — 5, такова:

T = 0.85·10-4 · 100.155n (секунд на CDC6600).

Улучшенный вариант алгоритма Робертса и Флореса не намного лучше

первоначального алгоритма. Необходимое время вычисления в нем все еще

зависит (более или менее) экспоненциально от n. Зависимость отношения

времен вычисления при использовании этих двух алгоритмов для

неориентированных графов со степенями вершин 3 — 5 приведена на рисунке 2.

Из этого рисунка видно, что «улучшенный» вариант в действительности хуже

для графов малых размеров, хотя для больших графов (с более чем 20

вершинами) он позволяет сэкономить более 50% времени вычисления.

По отношению к тому же вышеупомянутому множеству графов мультицепной

алгоритм оказался очень эффективным. Это видно из рисунка 3, на котором

показано необходимое для этого алгоритма время вычисления (здесь применен

линейный масштаб). График показывает, что время растет очень медленно в

зависимости от числа вершин и поэтому алгоритм применим для очень бльших

графов.

Другим преимуществом этого метода является очень слабая вариация

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

разумной степенью доверительности время вычисления, необходимое для

различных задач.

Кроме того, эксперименты показывают, что для графов, степени вершин

которых лежат в вышеприведенных пределах 3 — 5, метод по существу не

чувствителен к степеням вершин. Вычислительные результаты, показанные на

рисунках 1-3, относятся к поиску одного гамильтонова цикла в графе.

Небезынтересно сказать несколько слов о вычислениях с тремя

алгоритмами, когда искались все гамильтоновы циклы. Так, для

неориентированного графа с 20 вершинами со степенями вершин 3 — 5,

потребовалось 2 сек, чтобы найти все гамильтоновы циклы, следуя [pic]

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

[pic]

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

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

[pic]

алгоритму Робертса и Флореса (этих циклов оказалось 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).

[pic] (1)

[pic] (2)

Для обеспечения непрерывности маршрута вводятся дополнительно n

переменных [pic] и n2 дополнительных ограничений (3).

[pic] (3)

Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать

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

[pic] (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 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 |

|1 |- |0 |0 |3 |3 |6 |

|2 |0 |- |1 |4 |1 |0 |

|3 |1 |2 |- |0 |0 |3 |

|табл. 4 |

|-|1 |2 |3 |4 |5|6 |

|1|- |6 |4 |8 |7|14|

Изложим алгоритм Литтла на примере 1 предыдущего раздела…

Повторно запишем матрицу:

Вычитание константы из элементов любой строки или столбца матрицы С,

не изменяет минимальный тур.

Для алгоритма нам будет удобно получить побольше нулей в матрице С, не

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

строки ее минимальный элемент (это называется приведением по строкам, см.

табл. 3), а затем вычтем из каждого столбца матрицы, приведенной по

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

(см. табл.4).

Прочерки по диагонали означают, что из города i в город i ходить

нельзя. Заметим, что сумма констант приведения по строкам равна 27, сумма

по столбцам 7, сумма сумм равна 34.

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

цветом) элементов матрицы С, например, такой, как показано на табл. 2.

Подчеркивание элемента означает, что в туре из i-го элемента идут именно в

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

так как в туре из шести городов есть шесть ребер. Каждый столбец должен

содержать ровно один подчеркнутый элемент (в каждый город коммивояжер

въехал один раз), в каждой строке должен быть ровно один подчеркнутый

элемент (из каждого города коммивояжер выехал один раз); кроме того,

подчеркнутые элементы должны описывать один тур, а не несколько меньших

циклов. Сумма чисел подчеркнутых элементов есть стоимость тура. В таблице 2

стоимость равна 36, это тот минимальный тур, который получен

лексикографическим перебором.

Теперь будем рассуждать от приведенной матрицы в табл. 2. Если в ней

удастся построить правильную систему подчеркнутых элементов, т.е. систему,

удовлетворяющую трем вышеописанным требованиям, и этими подчеркнутыми

элементами будут только нули, то ясно, что для этой матрицы мы получим

минимальный тур. Но он же будет минимальным и для исходной матрицы С,

только для того, чтобы получить правильную стоимость тура, нужно будет

обратно прибавить все константы приведения, и стоимость тура изменится с 0

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

оценку снизу для всех туров.

Теперь приступим к ветвлению. Для этого проделаем шаг оценки нулей.

Рассмотрим нуль в клетке (1,2) приведенной матрицы. Он означает, что цена

перехода из города 1 в город 2 равна 0. А если мы не пойдем из города 1 в

город 2? Тогда все равно нужно въехать в город 2 за цены, указанные во

втором столбце; дешевле всего за 1 (из города 6). Далее, все равно надо

будет выехать из города 1 за цену, указанную в первой строке; дешевле всего

в город 3 за 0. Суммируя эти два минимума, имеем 1+0=1: если не ехать «по

нулю» из города 1 в город 2, то надо заплатить не меньше 1. Это и есть

оценка нуля. Оценки всех нулей поставлены на табл. 5 правее и выше

нуля (оценки нуля, равные нулю, не ставились).

Выберем максимальную из этих оценок (в примере есть несколько оценок,

равных единице, выберем первую из них, в клетке (1,2)).

Итак, выбрано нулевое ребро (1,2). Разобьем все туры на два класса –

включающие ребро (1,2) и не включающие ребро (1,2). Про второй класс можно

сказать, что придется приплатить еще 1, так что туры этого класса стоят 35

или больше.

Что касается первого класса, то в нем надо рассмотреть матрицу в табл.

6 с вычеркнутой первой строкой и вторым столбцом.

Дополнительно в уменьшенной матрице поставлен запрет в клетке (2,1),

т. к. выбрано ребро (1,2) и замыкать преждевременно тур ребром (2,1)

нельзя.

|1|3 |4|5 |6|

|2|1 |4|1 |0|

|3|01|-|1 |3|

|4|0 |1|- |0|

|5|3 |3|01|-|

|табл. 8 |

|-|1 |2 |3 |4 |5 |6|

|1|- |01|0 |3 |3 |6|

|2|01|- |1 |4 |1 |0|

|3|1 |2 |- |01|0 |3|

|-|1 |3 |4 |5 |6|

|2|01|1 |4 |1 |0|

|3|1 |- |01|0 |3|

|4|4 |01|- |1 |3|

|5|4 |0 |1 |- |0|

|6|7 |3 |3 |01|-|

|-|1 |3 |4 |5 |6|

|2|01|1 |4 |1 |0|

|3|03|- |01|0 |3|

|4|3 |01|- |1 |3|

|5|3 |0 |1 |- |0|

|6|6 |3 |3 |01|-|

|табл. 7 |

табл.6

Уменьшенную матрицу можно привести на 1 по первому столбцу, так что

каждый тур, ей отвечающий, стоит не меньше 35. Результат наших ветвлений и

получения оценок показан на рис.6.

Кружки представляют классы: верхний кружок – класс всех туров; нижний

левый – класс всех туров, включающих ребро (1,2); нижний правый – класс

всех туров, не включающих ребро (1,2). Числа над кружками – оценки снизу.

Продолжим ветвление в положительную сторону: влево - вниз. Для этого

оценим нули в уменьшенной матрице C[1,2] на табл. 7. Максимальная оценка в

клетке (3,1) равна 3. Таким образом, оценка для правой нижней вершины на

рис. 7 есть

|-|3 |4 |6 |

|2|1 |3 |03|

|4|03|- |3 |

|5|0 |03|0 |

|табл. 10 |

|- |3 |4 |5 |6 |

|2 |1 |3 |1 |0 |

|4 |01|- |1 |3 |

|5 |0 |02|- |0 |

|6 |3 |2 |03|- |

|табл. 9 |

35+3=38. Для оценки левой нижней вершины на рис. 7 нужно вычеркнуть из

матрицы C[1,2] еще строку 3 и столбец 1, получив матрицу C(1,2),(3,1) на

табл. 8. В эту матрицу нужно поставить запрет в клетку (2,3), так как уже

построен фрагмент тура из ребер (1,2) и (3,1), т.е. [3,1,2] и нужно

запретить преждевременное замыкание (2,3). Эта матрица приводится по

столбцу на 1 (табл. 9), таким образом, каждый тур соответствующего класса

(т.е. тур, содержащий ребра (1,2) и (3,1)) стоит 36 и более.

Оцениваем теперь нули в приведенной матрице C[(1,2),(3,1)] нуль с

максимальной оценкой 3 находится в клетке (6,5). Отрицательный вариант

имеет оценку 38+3=41. Для получения оценки положительного варианта убираем

строчку 6 и столбец 5, ставим запрет в клетку (5,6), см. табл. 10. Эта

матрица неприводима. Следовательно, оценка положительного варианта не

увеличивается (рис.8).

|- |3 |4 |

|4 |0 |- |

|5 |0 |0 |

| табл. 11|

Оценивая нули в матрице на табл. 10, получаем ветвление по выбору

ребра (2,6), отрицательный вариант получает оценку 36+3=39, а для получения

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

получая матрицу на табл. 11.

В матрицу надо добавить запрет в клетку (5,3), ибо уже построен

фрагмент тура [3,1,2,6,5] и надо запретить преждевременный возврат (5,3).

Теперь, когда осталась матрица 2х2 с запретами по диагонали, достраиваем

тур ребрами (4,3) и (5,4). Мы не зря ветвились, по положительным вариантам.

Сейчас получен тур: 1>2>6>5>4>3>1 стоимостью в 36. При достижении низа по

дереву перебора класс туров сузился до одного тура, а оценка снизу

превратилась в точную стоимость.

Итак, все классы, имеющие оценку 36 и выше, лучшего тура не содержат.

Поэтому соответствующие вершины вычеркиваются. Вычеркиваются также вершины,

оба потомка которой вычеркнуты. Мы колоссально сократили полный перебор.

Осталось проверить, не содержит ли лучшего тура класс, соответствующий

матрице С[Not(1,2)], т.е. приведенной матрице С с запретом в клетке 1,2,

приведенной на 1 по столбцу (что дало оценку 34+1=35). Оценка нулей дает 3

для нуля в клетке (1,3), так что оценка отрицательного варианта 35+3

превосходит стоимость уже полученного тура 36 и отрицательный вариант

отсекается.

Для получения оценки положительного варианта исключаем из матрицы

первую строку и третий столбец, ставим запрет (3,1) и получаем матрицу. Эта

матрица приводится по четвертой строке на 1, оценка класса достигает 36 и

кружок зачеркивается. Поскольку у вершины «все» убиты оба потомка, она

убивается тоже. Вершин не осталось, перебор окончен. Мы получили тот же

минимальный тур, который показан подчеркиванием на табл. 2.

Удовлетворительных теоретических оценок быстродействия алгоритма

Литтла и родственных алгоритмов нет, но практика показывает, что на

современных ЭВМ они часто позволяют решить ЗК с n = 100. Это огромный

прогресс по сравнению с полным перебором. Кроме того, алгоритмы типа ветвей

и границ являются, если нет возможности доводить их до конца, эффективными

эвристическими процедурами.

§6. Применение алгоритма Дейкстры к решению ЗК

Одним из вариантов решения ЗК является вариант нахождения кратчайшей

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

городом – получается искомый тур.

Известно множество простых алгоритмов. Один из них – алгоритм

Дейкстры, предложенный Дейкстрой ещё в 1959г. Этот алгоритм решает общую

задачу:

В ориентированной, неориентированной или смешанной сети найти

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

При небольшой модификации алгоритм Дейкстры позволяет найти

кратчайшие пути из данной вершины во все остальные. Матрица расстояний Dik

задаёт длины дуг dik между i-ой и k-ой вершинами; если такой дуги нет, то

dik присваивается большое число Б, равное “машинной бесконечности”.

Алгоритм Дейкстры имеет квадратичную сложность O(n2).

Таким образом, для решения ЗК нужно n раз применить алгоритм Дейкстры

следующим образом.

Возьмём произвольную пару вершин j,k. Исключим непосредственное ребро

D[j,k]. С помощью алгоритма Дейкстры найдём кратчайшее расстояние между

городами j,…,k. Пусть это расстояние включает некоторый город m. Имеем

часть тура j,m,k. Теперь для каждой пары соседних городов (в данном примере

– для j,m и m,k) удалим соответственное ребро и найдём кратчайшее

расстояние. При этом в кратчайшее расстояние не должен входить уже

использованный город.

Далее аналогично находим кратчайшее расстояние между парами вершин

алгоритмом Дейкстры, до тех пор, пока все вершины не будут задействованы.

Соединим последнюю вершину с первой и получим тур. Чаще всего это последнее

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

алгоритм Дейкстры можно отнести к приближённым алгоритмам.

§7. Метод выпуклого многоугольника для решения ЗК

Рассмотрим рис. 9-10 и попытаемся найти в них кратчайшие туры.

Очевидно, что кратчайший тур не должен содержать пересекающихся ребёр (в

противном случае, поменяв вершины при пересекающихся рёбрах местами,

получим более короткий тур). В первом случае кратчайшим является тур 1-2-4-

5-3-1, а во втором – тур 1-2-3-4-5-1. Анализируя множество других

аналогичных расположении пяти и более городов, можно сделать следующее

общее предположение:

Если можно построить выпуклый многоугольник, по периметру которого

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

туром.

Однако не всегда можно построить выпуклый многоугольник, по периметру

которого лежали бы все города. Велика вероятность того, что некоторые

города не войдут в выпуклый многоугольник. Такие города будем называть

“центральными”. Так как построить выпуклый многоугольник довольно легко, то

задача сводится к тому, чтобы включить в тур в виде выпуклого

многоугольника все центральные города с минимальными потерями. Пусть

имеется массив T[n+1], содержащий в себе номера городов по порядку, которые

должен посетить коммивояжер, т. е. вначале коммивояжер должен посетить

город T[1], затем T[2], потом T[3] и т.д., причём T[n+1]=T[1] (коммивояжер

должен вернуться в начальный город). Тогда, если выполняется равенство

(i[pic] [1,2..n] C[T[i],p]+ C[p,T[i+1]]–C[T[I],T[i+1]] = min, то

центральный город с номером p нужно включить в тур между городами T[i] и

T[i+1]. Проделав эту операцию для всех центральных городов, в результате

получим кратчайший тур. Для задачи, решённой нами методом ветвей и границ,

этот алгоритм даёт правильное решение.

Попробуем решить данным алгоритмом ЗК для восьми городов. Пусть имеем

восемь городов, расположение которых показано на рис. 11. Матрица

расстояний приведена рядом на табл. 13. Промежуточные построения

кратчайшего тура показаны пунктирными линиями, цифры – порядок удаления

рёбер. Таким образом, имеем для данного случая кратчайший тур 1-3-7-5-4-8-6-

2-1. Длина этого тура: D=6+7+5+2+6+5+ 13+13=57. Этот результат является

правильным, т.к. алгоритм лексического перебора, который никогда не

ошибается, даёт точно такой же тур. (Следует также отметить, что жадный

алгоритм для этого случая ошибается всего на 1 и даёт тур 1-3-4-5-7-8-6-2-1

длиной в 58).

Одним из возможных недостатков такого алгоритма является необходимость

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

нам известна матрица расстояний между городами, но неизвестны их

координаты, то для их нахождения нужно будет решить n систем квадратных

уравнений с n неизвестными для каждой координаты. Уже для 6 городов это

сделать очень сложно. Если же, наоборот, имеются координаты всех городов,

но нет матрицы расстояний между ними, то создать эту матрицу несложно. Это

можно легко сделать в уме для 5-6 городов. Для большего количества городов

можно воспользоваться возможностями компьютера, в то время как

промоделировать решение системы квадратных уравнений на компьютере довольно

сложно.

На основе вышеизложенного можно сделать вывод, что этот алгоритм,

наряду с деревянным алгоритмом и алгоритмом Дейкстры, можно отнести к

приближённым (хотя за этим алгоритмом ни разу не было замечено выдачи

неправильного варианта).

§8. Генетические алгоритмы

Пусть дана некоторая сложная функция (целевая функция), зависящая от

нескольких переменных, и требуется найти такие значения переменных, при

которых значение функции максимально. Задачи такого рода называются

задачами оптимизации и встречаются на практике очень часто.

Генетический алгоритм - это простая модель эволюции в природе,

реализованная в виде компьютерной программы. В нем используются как аналог

механизма генетического наследования, так и аналог естественного отбора.

При этом сохраняется биологическая терминология в упрощенном виде. Вот как

моделируется генетическое наследование:

|Хромосома |Вектор (последовательность) из нулей и единиц. |

| |Каждая позиция (бит) называется геном. |

|Индивидуум = |Набор хромосом = вариант решения задачи. |

|генетический | |

|код | |

|Кроссовер |Операция, при которой две хромосомы обмениваются своими |

| |частями. |

|Мутация |Случайное изменение одной или нескольких позиций в |

| |хромосоме. |

Чтобы смоделировать эволюционный процесс, сгенерируем вначале

случайную популяцию - несколько индивидуумов со случайным набором хромосом

(числовых векторов). Генетический алгоритм имитирует эволюцию этой

популяции как циклический процесс скрещивания индивидуумов и смены

поколений.

Жизненный цикл популяции - это несколько случайных скрещиваний

(посредством кроссовера) и мутаций, в результате которых к популяции

добавляется какое-то количество новых индивидуумов. Отбором в генетическом

алгоритме называется процесс формирования новой популяции из старой

популяции, после чего старая популяция погибает. После отбора к новой

популяции опять применяются операции кроссовера и мутации, затем опять

происходит отбор, и так далее.

Отбор в генетическом алгоритме тесно связан с принципами естественного

отбора в природе следующим образом:

|Приспособленность |Значение целевой функции на этом индивидууме. |

|индивидуума | |

|Выживание |Популяция следующего поколения формируется в |

|наиболее |соответствии с целевой функцией. Чем приспособленнее |

|приспособленных |индивидуум, тем больше вероятность его участия в |

| |кроссовере, т.е. размножении. |

Таким образом, модель отбора определяет, каким образом следует строить

популяцию следующего поколения. Как правило, вероятность участия

индивидуума в скрещивании берется пропорциональной его приспособленности.

Часто используется так называемая стратегия элитизма, при которой несколько

лучших индивидуумов переходят в следующее поколение без изменений, не

участвуя в кроссовере и отборе. В любом случае каждое следующее поколение

будет в среднем лучше предыдущего. Когда приспособленность индивидуумов

перестает заметно увеличиваться, процесс останавливают и в качестве решения

задачи оптимизации берут наилучшего из найденных индивидуумов.

Генетический алгоритм - новейший, но не единственно возможный способ

решения задач оптимизации. С давних пор известны два основных пути решения

таких задач - переборный и локально-градиентный. У этих методов свои

достоинства и недостатки, и в каждом конкретном случае следует подумать,

какой из них выбрать.

Рассмотрим достоинства и недостатки стандартных и генетических методов

на примере классической задачи коммивояжера (TSP - traveling salesman

problem). Суть задачи состоит в том, чтобы найти кратчайший замкнутый путь

обхода нескольких городов, заданных своими координатами. Оказывается, что

уже для 30 городов поиск оптимального пути представляет собой сложную

задачу, побудившую развитие различных новых методов (в том числе нейросетей

и генетических алгоритмов).

Каждый вариант решения (для 30 городов) - это числовая строка, где на

j-ом месте стоит номер j-ого по порядку обхода города. Таким образом, в

этой задаче 30 параметров, причем не все комбинации значений допустимы.

Естественно, первой идеей является полный перебор всех вариантов обхода.

Переборный метод наиболее прост по своей сути и тривиален в

программировании. Для поиска оптимального решения (точки максимума целевой

функции) требуется последовательно вычислить значения целевой функции во

всех возможных точках, запоминая максимальное решение. Недостатком этого

метода является большая вычислительная стоимость. В частности, в задаче

коммивояжера потребуется просчитать длины более 1030 вариантов путей, что

совершенно нереально. Однако, если перебор всех вариантов за разумное время

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

действительно оптимально.

Второй популярный способ основан на методе градиентного спуска. При

этом вначале выбираются некоторые случайные значения параметров, а затем

эти значения постепенно изменяют, добиваясь наибольшей скорости роста

целевой функции. Достигнув локального максимума, такой алгоритм

останавливается, поэтому для поиска глобального оптимума потребуются

дополнительные усилия.

Градиентные методы работают очень быстро, но не гарантируют

оптимальности найденного решения. Они идеальны для применения в так

называемых унимодальных задачах, где целевая функция имеет единственный

локальный максимум (он же - глобальный). Легко видеть, что задача

коммивояжера унимодальной не является.

Типичная практическая задача, как правило, мультимодальна и

многомерна, то есть содержит много параметров. Для таких задач не

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

быстро найти абсолютно точное решение.

Однако, комбинируя переборный и градиентный методы, можно надеяться

получить хотя бы приближенное решение, точность которого будет возрастать

при увеличении времени расчета.

Генетический алгоритм представляет собой именно такой комбинированный

метод. Механизмы скрещивания и мутации в каком-то смысле реализуют

переборную часть метода, а отбор лучших решений - градиентный спуск. На

рисунке показано, что такая комбинация позволяет обеспечить устойчиво

хорошую эффективность генетического поиска для любых типов задач.

Итак, если на некотором множестве задана сложная функция от нескольких

переменных, то генетический алгоритм - это программа, которая за разумное

время находит точку, где значение функции достаточно близко к максимально

возможному. Выбирая приемлемое время расчета, мы получим одно из лучших

решений, которые вообще возможно получить за это время.

§9. Применение генетических алгоритмов

Определим теперь понятия, соответствующие мутации и кроссинговеру в

генетическом алгоритме.

Мутация — это преобразование хромосомы, случайно изменяющее одну или

несколько ее позиций (генов). Наиболее распространенный вид мутаций —

случайное изменение только одного из генов хромосомы.

Кроссинговер (в литературе по генетическим алгоритмам также

употребляется название кроссовер или скрещивание) — это операция, при

которой из двух хромосом порождается одна или несколько новых хромосом. В

простейшем случае кроссинговер в генетическом алгоритме реализуется так же,

как и в биологии (см. рис. 1). При этом хромосомы разрезаются в случайной

точке и обмениваются частями между собой. Например, если хромосомы (1, 2,

3, 4, 5) и (0, 0, 0, 0, 0) разрезать между третьим и четвертым генами и

обменять их части, то получатся потомки (1, 2, 3, 0, 0) и (0, 0, 0, 4, 5).

Блок-схема генетического алгоритма изображена на рис. 1. Вначале

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

набор решений задачи. Как правило, это делается случайным образом. Затем мы

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

отбираются несколько пар индивидуумов, производится скрещивание между

хромосомами в каждой паре, а полученные новые хромосомы помещаются в

популяцию нового поколения. В генетическом алгоритме сохраняется основной

принцип естественного отбора — чем приспособленнее индивидуум (чем больше

соответствующее ему значение целевой функции), тем с большей вероятностью

он будет участвовать в скрещивании. Теперь моделируются мутации — в

нескольких случайно выбранных особях нового поколения изменяются некоторые

гены. Затем старая популяция частично или полностью уничтожается и мы

переходим к рассмотрению следующего поколения. Популяция следующего

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

же особей, сколько начальная, но в силу отбора приспособленность в ней в

среднем выше. Теперь описанные процессы отбора, скрещивания и мутации

повторяются уже для этой популяции и т. д.

В каждом следующем поколении мы будем наблюдать возникновение

совершенно новых решений нашей задачи. Среди них будут как плохие, так и

хорошие, но благодаря отбору число хороших решений будет возрастать.

Заметим, что в природе не бывает абсолютных гарантий, и даже самый

приспособленный тигр может погибнуть от ружейного выстрела, не оставив

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

нежелательных событий и всегда сохранять жизнь лучшему из индивидуумов

текущего поколения — такая методика называется “стратегией элитизма”.

Чтобы использовать генетический алгоритм для решения практических

задач, необходимо рассматривать более сложные варианты введенных выше

понятий. Поясним это на примере задачи коммивояжера для 20 городов.

В качестве индивидуумов будем рассматривать маршруты обхода.

Информацию о маршруте можно записать в виде одной хромосомы — вектора длины

20, где в первой позиции стоит номер первого города на пути следования,

затем — номер второго города и т. д. Первое затруднение возникает, когда мы

пытаемся определить мутации для таких хромосом — стандартная операция,

изменяющая только одну позицию вектора, недопустима, так как приводит к

некорректному маршруту. Но можно определить мутацию как перестановку

значений двух случайно выбранных генов. При таком преобразовании путь

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

Найденный маршрут, вероятно, не является самым оптимальным, но близок

к нему по длине — как правило, генетические алгоритмы “ошибаются” не более

чем на 5—10%. Этот недостаток компенсируется для комбинаторных задач

относительно высокой скоростью работы — в нашем примере ответ был получен

за 25 секунд. На практике генетические алгоритмы нередко используют

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

Эксперименты показали, что погрешность разработанного алгоритма не

зависит от погрешности начального решения и составляет (максимальные

значения) для ориентированных графов - 5%, для неориентированных 1%. Причем

в 90% случаев алгоритм находил точное решение. Эксперименты проводились для

графов с количеством вершин, меньшим 75 (где было возможным нахождение

точного решения).

Список литературы

В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования, 1998

г.

Н. Кристофидес. Теория графов: алгоритмический подход, Мир, 1978 г.

Ф.А. Новиков. Дискретная математика для программистов, Питер, 2001 г.

В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999 г.

О. Оре. Теория графов, Наука, 1982 г.

www.codenet.ru

www.algolist.ru

-----------------------

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

Страницы: 1, 2