Начиная с любой вершины v присваиваем ребру vu номер 1. Вычеркиваем это ребро из списка ребер и переходим к вершине u

1. Начиная с любой вершины v присваиваем ребру vu номер 1. Вычеркиваем это ребро из списка ребер и переходим к вершине u.

2. Пусть w - вершина, в которую мы пришли в результате выполнения 1 шага алгоритма и k - номер, присвоенный очередному ребру на этом шаге. Выбираем произвольное ребро инцидентное вершине w, причем мост выбираем только в крайнем случае, если других возможностей выбора ребра не существует. Присваиваем ребру номер k+1 и вычеркиваем его. Процесс длится до тех пор, пока все ребра не вычеркнут.

Примечание: Мостом называется ребро, удаление которого лишает данный граф связности, т.е. увеличивает число компонент связности.

Пример:

П
риведем теперь строгое обоснование корректности алгоритма Флёри построения эйлерового цикла в данном эйлеровом графе.

Теорема 2. Пусть G(V,E) — эйлеров граф. Тогда следующая процедура всегда возможна и приводит к построению эйлерова цикла графа G(V,E).

Выходя из произвольной вершины, идем по ребрам графа произвольным образом, соблюдая при этом следующие правила:

Стираем ребра по мере их прохождения (вместе с изолированными вершинами, которые при этом образуются);

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

Доказательство.

Убедимся сначала, что указанная процедура может быть выполнена на каждом этапе. Пусть мы достигли некоторой вершины v, начав с вершины u, v ≠ u. Удалив ребра пути из v в u, видим, что оставшийся граф G₁ связен и содержит ровно две нечетных вершины v и u. Согласно следствию #2 из теоремы 1 граф G₁ имеет эйлеров путь P из v в u. Поскольку удаление первого ребра инцидентного u пути P либо не нарушает связности G₁, либо происходит удаление вершины u и оставшийся граф G₂ связен с двумя нечетными вершинами, то отсюда получаем, что описанное выше построение всегда возможно на каждом шаге. (Если v = u, то доказательство не меняется, если имеются ребра, инцидентные u). Покажем, что данная процедура приводит к эйлерову пути. Действительно, в G не может быть ребер, оставшихся не пройденными после использования последнего ребра, инцидентного u, поскольку в противном случае удаление ребра, смежного одному из оставшихся, привело бы к несвязному графу, что противоречит условию 2).

§4. Некоторые родственные задачи

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

Каково наименьшее число цепей или циклов необходимое для того, чтобы каждое ребро графа G содержалось точно в одной цепи или в одном цикле? Очевидно, что если G имеет эйлеров цикл или эйлерову цепь, то ответом будет число один.

Р
ебрам графа G приписаны положительные веса. Требуется найти цикл, проходящий через каждое ребро графа G по крайней мере один раз и такой, что для него общий вес (а именно сумма величин n_jc(a_j), где число n_jпоказывает, сколько раз проходилось ребро a_j, а c(a_j) — вес ребра) минимален. Очевидно, что если G содержит эйлеров цикл, то любой такой цикл будет оптимальным, так как каждое ребро проходится по один раз и вес этого цикла равен тогда

Сформулированная выше задача 2) называется задачей китайского почтальона, и ее решение имеет много потенциальных приложений, как например:

Сбор мусора. Рассмотрим проблему сбора домашнего мусора. Допустим, что определенный район города обслуживается единственной машиной. Ребра графа G представляют дороги, а вершины — пересечения дорог. Величина c(a_j) — вес ребра — будет соответствовать длине дороги. Тогда проблема сбора мусора в данном районе сводится к нахождению цикла в графе G, проходящего по каждому ребру G по крайней мере один раз. Требуется найти цикл с наименьшим километражем.

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

Проверка электрических, телефонных или железнодорожных линий. Проблема инспектирования распределенных систем (лишь некоторые из которых названы выше) связана с непременным требованием проверки всех «компонент». Поэтому она также является проблемой типа 2) или близка к ней.

§5. Задача китайского почтальона

Р
ассмотрим неориентированный граф G(X,A). Среди вершин из X некоторые вершины (скажем из множества X⁺) будут иметь четные степени, а остальные (из множества X^-=X\X⁺) — нечетные степени. Сумма степеней d_i всех вершин x_iX равна удвоенному числу ребер в A (т.к. каждое ребро добавляет по единице к степеням двух его концевых вершин) и поэтому равна четному числу 2m. Следовательно, и так как первая сумма четна, то вторая сумма также четна. Но все d_iв последней сумме нечетны, значит число |X^-| вершин нечетной степени четно.

Пусть M — множество таких цепей (скажем μ_ij) в G между концевыми вершинами x_i и x_j X^-, что никакие две цепи не имеют одинаковых конечных вершин, т.е. цепи соединяют различные пары вершин из X^- и покрывают все вершины множества X^-. Число цепей μ_ij в M равно 1/2|X^-| и всегда цело, если конечно оно определено. Предположим теперь, что все ребра, образующие цепь μ_ij, теперь удвоены (добавлены искусственные ребра). Так поступаем с каждой цепью μ_ijM и полученный граф обозначим через G^-(M). Так как некоторые ребра из G могут входить более чем в одну цепь μ_ij, то некоторые ребра из G^-(M) могут быть (после того как добавлены все «новые» цепи μ_ij) утроены, учетверены и т.д.

Теорема 3. Для любого цикла, проходящего по G, можно выбрать множество M, для которого граф G^-(M) имеет эйлеров цикл, соответствующий первоначально взятому циклу в графе G. Это соответствие таково, что если цикл проходит по ребру (x_i, x_j) из G l раз, то в G^-(M) существует l ребер (одно реальное и l-1 искусственных) между x_i и x_j, каждое из которых проходится ровно один раз эйлеровым циклом из G^-(M). Справедливо и обратное утверждение.

Доказательство.

Если цикл проходит по графу G, то по крайней мере одно ребро, инцидентное каждой вершине x_i нечетной степени, должно проходиться дважды. (Ребро, проходимое дважды, можно рассматривать как два параллельных ребра — одно реальное и одно искусственное — и каждое из них проходится один раз). Пусть это ребро (x_i, x_k). В случае нечетности степени d_k вершины x_k графа G добавление искусственного ребра прежде всего сделает d_k четным, и значит только ребро (x_i,x_k) нужно будет проходить дважды, если ограничиться рассмотрением лишь вершин x_i и x_k. В случае когда d_k четно, добавление искусственного ребра сделает d_k нечетным, а второе ребро выходящее из x_k должно быть пройдено дважды (т.е. добавляется еще одно искусственное ребро). Такая ситуация сохраняется до тех пор, пока не встретится вершина нечетной степени, о чем говорилось выше. Следовательно, чтобы удовлетворить условию возвращения в вершину x_i, нужно дважды пройти всю цепь из x_i в некоторую другую вершину нечетной степени x_rX^-_{. Это автоматически приводит к выполнению условия прохождения вершины xr. Аналогично обстоит дело для всех других вершин xiX}^-_{. Это значит что все множество M цепей из G, определенное выше, должно проходится дважды, и так как отсюда вытекает, что каждое ребро из G}^-_{(M) должно проходиться один раз, то теорема доказана.}

_{Алгоритм решения задачи китайского почтальона немедленно следует из доказанной теоремы, так как все, что для этого необходимо, состоит в нахождении множества цепей M}^* _{(цепного паросочетания для множества вершин нечетной степени), дающего наименьший дополнительный вес. Цикл наименьшего веса, проходящий по G, будет иметь вес, равный сумме весов всех ребер из G плюс сумма весов ребер в цепях из M}^*_{. Это то же самое, что и сумма весов всех ребер — реальных и искусственных — графа G}^-_(M^*_).

Описание алгоритма решения задачи китайского почтальона:

Пусть [c_ij] — матрица весов ребер G. Используя алгоритм нахождения кратчайшей цепи, образуем |X^-|_*|X^-| — матрицу D=[d_ij], где d_ij — вес цепи наименьшего веса, идущей из некоторой вершины x_iX^- _{в другую вершину xjX}^-_.

_{Найдем то цепное паросочетание M}^*_{для множества X}^-_{, которое дает наименьший вес (в соответствии с матрицей весов D). Это можно сделать эффективно с помощью алгоритма минимального паросочетания.}

_{Если вершина xαсочетается с другой вершиной xβ, то определим цепь μαβ наименьшего веса (из xα в xβ), соответствующую весу dαβ, делая шаг 1. Добавим искусственные ребра в G, соответствующие ребрам из μαβ, и проделаем это для всех других цепей из множества M}^*_{, в результате чего получится граф G}^-_(M^*_).

_{Сумма весов всех ребер графа G}^-_(M^*_{), найденная с использованием матрицы [cij] (вес искусственного ребра берется равным весу параллельного ему реального ребра), равна минимальному весу цикла, проходящего по G. При этом число прохождений цикла по ребру (xi,xj) равно общему числу параллельных ребер между xiи xj в G}^-_(M^*_).

Покажем, что указанный выше алгоритм строит минимальный цикл. Для этого следует заметить, что поскольку на шаге 2 мы используем минимальное паросочетание, никакие две кратчайшие цепи μ_ijи μ_pq при таком паросочетании (скажем, идущие из x_i в x_j и из x_p в x_q) не могут иметь общего ребра. Если бы они имели общее ребро (x_a, x_b), то сочетание вершин x_i и x_q (использующее подцепи от x_iк x_b и от x_b к x_q) и сочетание пары вершин x_pи x_j(использующее подцепи от x_pк x_aи от x_aк x_j) давало бы общее паросочетание веса 2c_ab, меньшего чем вес первоначального паросочетания, что противоречит предположению о минимальности исходного паросочетания. Следовательно, граф G^-(M^*)не должен содержать более двух параллельных ребер между любыми двумя вершинами, т.е. оптимальный цикл не проходит ни по какому ребру графа G более чем два раза.

Глава 2. Гамильтоновы циклы

Название «гамильтонов цикл» произошло от задачи «Кругосветное путешествие» предложенной ирландским математиком Вильямом Гамильтоном в 1859 году. Нужно было, выйдя из исходной вершины графа, обойти все его вершины и вернуться в исходную точку. Граф представлял собой укладку додекаэдра, каждой из 20 вершин графа было приписано название крупного города мира.

§1. Основные понятия и определения

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

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

Замечание.

Любой граф G можно превратить в гамильтонов граф, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам v₁,…,v_p графа G добавить вершины u₁,…,u_p и множество ребер {(v_i,u_i)}{(u_i,v_i+1)}.

Степенью вершины v называется число ребер d(v), инцидентных ей, при этом петля учитывается дважды. В случае ориентированного графа различают степень d_o(v) по выходящим дугам и d_i(v) — по входящим.

§2. Условия существования гамильтонова цикла

В отличии от эйлеровых графов, где имеется критерий для графа быть эйлеровым, для гамильтоновых графов такого критерия нет. Более того, задача проверки существования гамильтонова цикла оказывается NP-полной. Большинство известных фактов имеет вид: «если граф G имеет достаточное количество ребер, то граф является гамильтоновым». Приведем несколько таких теорем.

Теорема Дирака. Если в графе G(V,E) c n вершинами (n ≥ 3) выполняется условие d(v) ≥ n/2 для любого vV, то граф G является гамильтоновым.

Доказательство.

От противного. Пусть G — не гамильтонов. Добавим к G минимальное количество новых вершин u₁, … ,u_n, соединяя их со всеми вершинами G так, чтобы G’:= G + u₁ + … + u_n был гамильтоновым.

Пусть v, u₁, w, … ,v — гамильтонов цикл в графе G’, причем vG, u₁G’, u₁G. Такая пара вершин v и u₁ в гамильтоновом цикле обязательно найдется, иначе граф G был бы гамильтоновым. Тогда wG, w {u₁,…,u_n}, иначе вершина u₁ была бы не нужна. Более того, вершина v несмежна с вершиной w, иначе вершина u₁ была бы не нужна.

Далее, если в цикле v,u₁,w, … ,u’,w’, … ,v есть вершина w’, смежная с вершиной w, то вершина v’ несмежна с вершиной v, так как иначе можно было бы построить гамильтонов цикл v,v’, … ,w,w’, … ,v без вершины u₁, взяв последовательность вершин w, … ,v’ в обратном порядке. Отсюда следует, что число вершин графа G’, не смежных с v, не менее числа вершин, смежных с w. Но для любой вершины w графа G d(w) ≥ p/2+n по построению, в том числе d(v) ≥ p/2+n. Общее число вершин (смежных и не смежных с v) составляет n+p-1. Таким образом, имеем:

n+p-1 = d(v)+d(V) ≥ d(w)+d(v) ≥ p/2+n+p/2+n = 2n+p.

Следовательно, 0 ≥ n+1, что противоречит тому, что n > 0.

Теорема Оре. Если число вершин графа G(V,E) n ≥ 3 и для любых двух несмежных вершин u и v выполняется неравенство:

d(u)+d(v) ≥ nи (u,v)E, то граф G — гамильтонов.

Граф G имеет гамильтонов цикл если выполняется одно из следующих условий:

Условие Поша: d(v_k) ≥ k+1 для k < n/2.

Условие Бонди: из d(v_i) ≤ i и d(v_k) ≤ k => d(v_i)+d(v_k)≥n (k≠i)

Условие Хватала: из d(v_k)≤ k ≤ n/2 => d(v_n-k)≥ n-k.

Далее, известно, что почти все графы гамильтоновы, то есть

г
де H(p) — множество гамильтоновых графов с p вершинами, а G(p) — множество всех графов с p вершинами. Таким образом, задача отыскания гамильтонова цикла или эквивалентная задача коммивояжера являются практически востребованными, но для нее неизвестен (и, скорее всего не существует) эффективный алгоритм решения.

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

N = 8; d(v_i) = 3; 3 ≥ 8/2 = 4 не гамильтонов граф, но существует гамильтонов цикл: M = (1, 2, 3, 4, 5, 6, 7, 8, 1)

§3. Задачи связанные с поиском гамильтоновых циклов

В ряде отраслей промышленности возникает следующая задача планирования. Нужно произвести n продуктов, используя единственный тип аппаратуры. Аппарат должен быть перенастроен после того как был произведен продукт p_i(но до того как начато производство продукта p_j), в зависимости от комбинации (p_i,p_j). Стоимость перенастройки аппаратуры постоянна и не зависит от производимых продуктов. Предположим, что эти продукты производятся в непрерывном цикле, так что после производства последнего из n продуктов снова возобновляется в том же фиксированном цикле производство первого продукта.

Возникает вопрос о том, может ли быть найдена циклическая последовательность производства продуктов p_i(i=1,2,…,n), не требующая перенастройки аппаратуры. Если представить эту задачу в виде ориентированного графа, то ответ на поставленный вопрос зависит от того, имеет ли этот ориентированный граф гамильтонов цикл или нет.

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

Таким образом мы рассмотрим следующие две задачи.

Задача 1. Дан ориентированный граф G, требуется найти в G гамильтонов цикл (или все циклы), если существует хотя бы один такой цикл.

Задача 2. Дан полный ориентированный цикл G, дугам которого приписаны произвольные веса C=[c_ij], найти такой гамильтонов цикл, который имеет наименьший общий вес. Следует отметить, что если ориентированный граф G не полный, то его можно рассматривать как полный ориентированный граф, приписывая отсутствующим дугам бесконечный вес.

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

Очевидно, что сформулированная выше задача (1) является частным случаем задачи (2). В самом деле, приписывая случайным образом дугам заданного ориентированного графа G конечные веса, получаем задачу коммивояжера. Если решение для этой задачи, т.е. кратчайший гамильтонов цикл, имеет конечное значение, то это решение является гамильтоновым циклом ориентированного графа G (т.е. ответом на задачу 1). Если же решение имеет бесконечное значение, то G не имеет гамильтонова цикла.

С другой стороны можно дать еще одну интерпретацию задачи 1). Рассмотрим снова полный ориетированный граф G₁ с общей матрицей весов дуг [c_ij] и рассмотрим задачу нахождения такого гамильтонова цикла, в котором самая длинная дуга минимальна. Эту задачу можно назвать минимаксной задачей коммивояжера. Тогда классическую задачу коммивояжера в той же терминологии можно было бы назвать минисуммной задачей коммивояжера. Покажем теперь, что задача (1) действительно эквивалентна минимаксной задаче коммивояжера.

В вышеупомянутом полном ориентированном графе G₁ мы можем наверняка найти гамильтонов цикл. Пусть это будет цикл Ф₁, и пусть вес самой длинной его дуги равен ĉ₁. Удалив из G₁ любую дугу, вес которой не меньше ĉ₁, получим ориентированный граф G₂. Найдем в ориентированном графе G₂ гамильтонов цикл Ф₂, и пусть вес его самой длинной дуги равен ĉ₂. Удалим из G₂ любую дугу, вес которой не меньше ĉ₂, и так будем продолжать до тех пор, пока не получим ориентированный граф G_m+1, не содержащий никакого гамильтонова цикла. Гамильтонов цикл Ф_m в G_m(с весом ĉ_m) является тогда по определению решением минимаксной задачи коммивояжера, так как из отсутствия гамильтонова цикла в G_m+1 следует, что в G₁ не существует никакого гамильтонова цикла, не использующего по крайней мере одну дугу с весом, большим или равным ĉ_m.

Таким образом, алгоритм нахождения гамильтонова цикла в ориентированном графе решает также минимаксную задачу коммивояжера. Наоборот, если мы располагаем алгоритмом решения последней задачи, то гамильтонов цикл в произвольном ориентированном графе G может быть найден с помощью построения полного ориентированного графа G₁ с тем же самым множеством вершин, что и в G, дугам которого, соответствующим дугам из G, приписаны единичные веса, а остальным дугам — бесконечные веса. Если решение минимаксной задачи коммивояжера для G₁ имеет конечный вес (на самом деле равный единице), то в графе G может быть найден соответствующий гамильтонов цикл. Если же решение имеет бесконечный вес, то в графе G не существует никакого гамильтонова цикла. Следовательно, две указанные задачи можно рассматривать как эквивалентные, поскольку было продемонстрировано, что алгоритм нахождения гамильтонова цикла позволяет решать минимаксную задачу коммивояжера и наоборот.

Ввиду того, что обе сформулированные выше задачи (1) и (2) часто встречаются в практических ситуациях и (как мы увидим позже) задачу (1) саму по себе решить намного проще, чем как подзадачу задачи (2), мы обе эти задачи рассмотрим по отдельности.

§4. Методы построения гамильтоновых циклов в графе.

Пока неизвестно никакого простого критерия или алгебраического метода, позволяющего ответить на вопрос, существует или нет в произвольном графе G гамильтонов цикл. Критерии существования, данные выше, представляют теоретический интерес, но являются слишком общими и не пригодны для произвольных графов, встречающихся на практике. Алгебраические методы определения гаильтоновых циклов не могут быть применены с более чем несколькими десятками вершин, так как они требуют слишком большого времени работы и большой памяти компьютера. Более приемлемым является способ Робертса и Флореса, который не предъявляет чрезмерных требований к памяти компьютера, но время в котором зависит экспоненциально от числа вершин в графе. Однако другой неявный метод перебора имеет для большинства типов графов очень небольшой показатель роста времени вычислений в зависимости от числа вершин. Он может быть использован для нахождения гамильтоновых циклов в очень больших графах. Ниже будут описаны алгебраический метод, перебор с возвратами, его улучшение, мультицепной метод.

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

Этот метод включает в себя построение всех простых цепей с помощью последовательного перемножения матриц. «Внутреннее произведение вершин» цепи x₁, x₂, … ,x_k-1, x_kопределяется как выражение вида x₂*x₃* … x_k-1, не содержащее две концевые вершины x₁ и x_k. «Модифицированная матрица смежности» B=[β(i,j)] — это (nЧn)- матрица, в которой β(i,j) — x_j, если существует дуга из x_i в x_jи нуль в противном случае. Предположим теперь, что у нас есть матрица P_L= [p_L(i ,j)], где p_L(i,j) — сумма внутренних произведений всех простых цепей длины L (L≥1) между вершинами x_i и x_jдля x_i≠x_j. Положим p_L(i,i)=0 для всех i. Обычное алгебраическое произведение матриц B*P_L= P’_L+1 = [p’_L+1(s,t)] определяется как
т.е. p’_L+1(s,t) является суммой внутренних произведений всех цепей из x_s в x_tдлины l+1. Так как все цепи из x_k в x_t, представленные внутренними произведениями из p_L(k,t), являются простыми, то среди цепей, получающихся из указанного выражения, не являются простыми лишь те, внутренние произведения которых в p_L(k,t) содержат вершину x_s. Таким образом, если из p’_L+1(s,t) исключить все слагаемые, содержащие x_s(а это можно сделать простой проверкой), то получим p_L+1(s,t). Матрица P_L+1=[p_L+1(s,t)], все диагональные элементы которой равны 0, является тогда матрицей всех простых цепей длины L+1.

В
ычисляя затем B*P_L+1, находим P_L+2 и т.д., пока не будет построена матрица P_n-1, дающая все гамильтоновы цепи (имеющие длину n-1) между всеми парами вершин. Гамильтоновы циклы получаются тогда сразу из цепей в P_n-1 и тех дуг из G, которые соединяют начальную и конечную вершины каждой цепи. С другой стороны, гамильтоновы циклы даются членами внутреннего произведения вершин, стоящими в любой диагональной ячейке матрицы B*P_n-1 (все диагональные элементы этой матрицы одинаковые).

Очевидно, что в качестве начального значения матрицы P (т.е. P₁) следует взять матрицу смежности A графа, положив все ее диагональные элементы равными нулю.

Недостатки этого метода совершенно очевидны. В процессе умножения матриц (т.е. когда L увеличивается) каждый элемент матрицы P_L будет состоять из все большего числа членов вплоть до некоторого критического значения L, после которого число членов снова начнет уменьшаться. Это происходит вследствие того, что для малых значений L и для графов, обычно встречающихся на практике, число цепей длины L+1, как правило, больше, чем число цепей длины L, а для больших значений L имеет место обратная картина. Кроме того, так как длина каждого члена внутреннего произведения вершин увеличивается на единицу, когда L увеличивается на единицу, то объем памяти, необходимый для хранения матрицы P_L, растет очень быстро вплоть до максимума при некотором критическом значении L, после которого этот объем снова начинает уменьшаться.

Небольшая модификация вышеприведенного метода позволяет во много раз уменьшить необходимый объем памяти и время вычислений. Так как нас интересуют только гамильтоновы циклы и, как было отмечено выше, они могут быть получены из членов внутреннего произведения любой диагональной ячейки матрицы B*P_n-1, то необходимо знать только элемент p_n-1(1,1). При этом на каждом этапе не обязательно вычислять и хранить всю матрицу P_L, достаточно лишь найти первый столбец P_L. Эта модификация уменьшает необходимый объем памяти и время вычислений в n раз. Однако даже при использовании этой модификации программа для ЭВМ, написанная на языке PL/1, который позволяет построчную обработку литер и переменное распределение памяти, не была способна найти все гамильтоновы циклы в неориентированных графах с более чем примерно 20 вершинами и средним значением степени вершины, большим 4. Использовался компьютер IBM 360/65 с памятью 120 000 байтов. Более того, даже для графа с вышеуказанными «размерами» данный метод использовал фактически весь объем памяти и время вычислений равнялось 1.8 минуты. Не такое уж незначительное время для столь небольшого графа.

§6. Метод перебора Робертса и Флореса

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

Следующая схема перебора, использующая обычную технику возвращения, была первоначально предложена Робертсом и Флоресом. Начинают с построения (kЧn)-матрицы M=[m_ij], где элемент m_ij есть i-я вершина (скажем x_q), для которой в графе G(X,Г) существует дуга (x_j,x_q). Вершины x_qво множестве Г(x_j) можно упорядочить произвольно, образовав элементы j-го столбца матрицы M. Число строк k матрицы M будет равно наибольшей полустепени исхода вершины.

Метод состоит в следующем. Некоторая начальная вершина (скажем, x₁) выбирается в качестве отправной и образует первый элемент множества S, которое каждый раз будет хранить уже найденные вершины строящейся цепи. К S добавляется первая вершина (например, вершина a) в столбце x₁. Затем к множеству S добавляется первая возможная вершина (например, вершина b) в столбце a, потом добавляется к S первая возможная вершина (например, вершина c) в столбце b и т.д. Под «возможной» вершиной мы понимаем вершину, еще не принадлежащую S. Существуют две причины, препятствующие включению некоторой вершины на шаге r во множество S = {x₁,a,b,c, … ,x_r-1,x_r}:

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

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

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

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

Дуга (x_r,x₁) не существует и не может быть получен никакой гамильтонов цикл.

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

Возвращение состоит в удалении последней включенной вершины x_rиз S, после чего остается множество S = {x₁,a,b,c, … ,x_r-1}, и добавлении к S первой возможной вершины, следующей за x_r, в столбце x_r-1 матрицы M. Если не существует никакой возможной вершины, делается следующий шаг возвращения и т.д.

Поиск заканчивается в том случае, когда множество S состоит только из вершины x₁ и не существует никакой возможной вершины, которую можно добавить к S, так что шаг возвращения делает множество S пустым. Гамильтоновы циклы, найденные к этому моменту, являются тогда всеми гамильтоновыми циклами, существующими в графе.

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

Пример:

"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 = {x₁,x₂, … ,x_r} и что следующей вершиной, которую предполагается добавить к S, является x^*S. Рассмотрим теперь две следующие ситуации, в которых вершина является изолированной в подграфе, остающемся после удаления из G(X,Г) всех вершин, образующих построенную до этого цепь.

Если существует такая вершина xX\S, что xГ(x_r) и Г^-1(x) S, то, добавляя к S любую вершину x^*, отличную от x, мы не сможем в последующем достигнуть вершины x ни из какой конечной вершины построенной цепи, и, значит, эта цепь не сможет привести нас к построению гамильтонова цикла. Таким образом, в этом случае x является единственной вершиной, которую можно добавить к S для продолжения цепи.

Если существует такая вершина xX\S, что xГ^-1(x₁) и Г(x) S{x^*} для некоторой другой вершины x^*, то x^* не может быть добавлена к S, так как тогда в остающемся подграфе не может существовать никакой цепи между x и x₁. Цепь, определяемая множеством S {x^*}, не может поэтому привести к гамильтонову циклу, а в качестве кандидата на добавление к множеству S следует рассмотреть другую вершину, отличную от x^*.

Проверка условий (a) и (b) будет, конечно, замедлять итеративную процедуру, и для небольших графов (менее чем с 20 вершинами) не получается никакого улучшения первоначального алгоритма Робертса и Флореса. Но для больших графов эта проверка приводит к заметному сокращению необходимого времени вычислений, уменьшая его обычно в 2 или более раз.

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

После внимательного изучения операций алгоритма перебора Робертса и Флореса становится очевидным, что даже после сделанного улучшения не слишком много внимания уделяется оставшейся части графа, в которой берется последовательность вершин, продолжающих построенную цепь. Обычно построение цепи S₀ в процессе поиска (S₀ рассматривается и как упорядоченное множество вершин, и как обычное множество) подразумевает существование еще каких-то цепей в других частях графа. Эти предполагаемые цепи либо помогают быстрее построить гамильтонов цикл, либо указывают на отсутствие такого цикла, содержащего цепь S₀, что позволяет сразу прибегнуть к возвращению.

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

Допустим, что на некотором этапе поиска построена цепь S₀ и возможны цепи S₁, S₂, … . Рассмотрим какую-либо «среднюю» вершину одной из этих цепей (слово «средняя» здесь означает любую вершину, отличную от начальной и конечной). Поскольку эта вершина уже включена в цепь с помощью двух дуг, то очевидно, что все другие дуги, входящие или выходящие из такой вершины, могут быть удалены из графа. Для любой начальной вершины вышеуказанных цепей можно удалить все дуги, исходящие из нее (за исключением дуги, включающей эту вершину в цепь), а для любой конечной вершины можно удалить все дуги, оканчивающиеся в ней (опять-таки за исключением дуги, включающей ее в цепь). Кроме того, за исключением случая, когда существует только одна цепь (скажем, S₀), проходящая через все вершины графа G (т.е когда S₀ — гамильтонова цепь), любая имеющаяся дуга, ведущая из конца любой цепи в начальную вершину этой же цепи, может быть удалена, так как такая дуга замыкает не гамильтоновы циклы.

Удаление всех этих дуг даст граф — со всеми «средними» вершинами цепей, в котором только одна дуга оканчивается в каждой вершине и только одна дуга исходит из нее. Все эти «средние» вершины и дуги, инцидентные им, удаляются из G, а вместо них для каждой цепи вводится единственная дуга, идущая от начальной вершины цепи до ее конечной вершины. В результате всего этого получается редуцированный граф G_k(X_k,Г_k), где k — индекс, показывающий номер шага поиска.

Рассмотрим теперь продолжение цепи S₀ (сформированной в результате поиска), осуществляемое путем добавления вершины x_j, которая является возможной в смысле алгоритма Робертса и Флореса, т.е. в G_k существует дуга, исходящая из конечной вершины цепи S₀ — обозначим эту вершину e(S₀) — и входящая в вершину x_j. Добавление x_j к S₀ осуществляется так:

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

все дуги, оканчивающиеся в x_j или исходящие из e(S₀), за исключением дуги (e(S₀), x_j);

все дуги, выходящие из x_j в начальную вершину пути S₀;

если окажется, что x_j является начальной вершиной другой цепи S_j, то следует удалить также любую дугу, идущую из конечной вершины цепи S_j в начальную вершину цепи S₀.

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

Если существует вершина x в графе G’_k, не являющаяся конечной ни для одной из цепей S₀, S₁, … и которая после удаления дуг имеет полустепень захода, равную единице, т.е. |Г^-1_k’(x)|=1, то выкинуть все дуги, исходящие из вершины v= Г^-1_k’(x), за исключением дуги (v, x).

Если существует вершина x графа G’_k, не являющаяся начальной ни для какой цепи и которая после удаления дуг имеет полустепень исхода, равную единице, т.е. |Г_k’(x)|=1, то выкинуть все дуги, исходящие из вершины x, за исключением дуги (x, Г_k’(x)).

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

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

Удалить из оставшегося графа G’_kвсе вершины, полустепени захода и исхода которых равны единице, т.е. вершины, которые стали теперь «средними» вершинами цепей. Это удаление производится так, как это было описано выше, в результате чего получается новый редуцированный граф G_k+1, заменяющий предыдущий граф G_k.

Совершенно очевидно, что если добавление вершины x_j к цепи S₀ делает полустепень захода или полустепень исхода (или обе) некоторой вершины x в конце шага 2 равной нулю, то не существует никакого гамильтонова цикла. В этом случае вершина x_j удаляется из множества S₀ и в качестве другой вершины x_j, позволяющей продолжить цепь S₀, выбирается некоторая другая вершина из множества Г_k’[e(S₀)]. И так до тех пор, пока не будет исчерпано все множество Г_k’[e(S₀)] и придется прибегнуть к возвращению (т.е. e(S₀) удаляется из S₀ и заменяется другой вершиной и т.д.). Отметим, что операция возвращения предполагает хранение достаточной информации об удаленных дугах в шагах 1 и 2 на каждом этапе k, чтобы можно было по графу G_k+1 восстановить граф G_kпри любых k, если приходится прибегать к возвращению.

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

Лучший вычислительный путь состоит в том, чтобы при каждой итерации шага 2 (за исключением последней) проверять отличие от нуля полустепеней захода и исхода всех вершин графа G’_k. Поэтому как только одна из них станет равной нулю, сразу же применяется операция возвращения, и если найдена гамильтонова цепь, то получается и гамильтонов цикл без проверки существования дуги возврата.

Если не возникает ни один из вышеупомянутых случаев, т.е. если (на некотором этапе k) в конце шага 2 остается более чем одна цепь и все полустепени являются ненулевыми, то нельзя еще сделать никаких выводов. Тогда вершина x_jдобавляется к S₀ и выбирается другая вершина для дальнейшего продолжения цепи. Шаги 1, 2, 3 повторяются, начиная с нового редуцированного графа.

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

В этом параграфе сравниваются первоначальный вариант алгоритма Робертса и Флореса, его улучшенный вариант и мультицепной метод_. Эти три метода мы будем сравнивать по необходимому времени вычислений для нахождения одного гамильтонова цикла, если таковой существует, или доказательства его отсутствия. Проверка была проведена на случайно выбранных графах, степени вершин которых лежат в предписанных границах. Всего было использовано около 200 графов, для которых приводятся средние результаты. Во всех графах оказались гамильтоновы циклы.

Ниже на рисунке 1 показана зависимость требуемого алгоритмом Робертса и Флореса времени вычисления от числа вершин графа; степени вершин лежат в пределах 3 — 5. Ввиду сильных вариаций требуемого времени для графов одинаковых размеров приводятся три ломанные, характеризующие среднее, максимальное и минимальное время, полученное для различных графов с одинаковым числом вершин. Следует заметить, что на рисунке 1 применен полулогарифмический масштаб, что говорит об экспоненциальном характере зависимости. Формула, дающая приближенную зависимость времени T от числа вершин n графа со степенями вершин в пределах 3 — 5, такова:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

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

(3)

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

(4)

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

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

C_ij  0;

C_jj= ∞ (5)

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

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

С_ij= С_ji (6)

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

C_ij + C_jk  C_ik (7)

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

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

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

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

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

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

Рассмотрим условие (4) подробнее. Применим метод доказательства от противного, то есть предположим, что условие (4) выполняется для некоторого подцикла T из R городов, где R L_HC  L_MT (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	—

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

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

2f_B > 2L_HC 2L_MT  f_A (11)

Т.е. 2f_B>f_A, f_A/f_B>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 элементов. Это можно сделать несколькими способами, но самый распространенный (т.е. приложимый для переборных алгоритмов решения других задач) – это перебор в лексикографическом порядке.

Говорят, что перестановка (a₁,…,a_n) лексикографически предшествует перестановке (b₁,…,b_n), если существует k ≤ n a_k< b_k и для любого i > k a_i = b_i.

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

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

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

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

Ф(ω⁰)