Если (на некотором этапе) в конце шага 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, это тот минимальный тур, который получен лексикографическим перебором.
Страницы: 1, 2, 3, 4, 5, 6, 7
