Задача коммивояжёра. Метод ветвей и границ

Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «Travelling salesman problem», TSP ). Также встречается название «задача о бродячем торговце ». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута, позволяющего объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальная длина пути.

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

Общий план решения задачи коммивояжера

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

1. Построение матрицы с исходными данными.
2. Нахождение минимума по строкам.
3. Редукция строк.
4. Нахождение минимума по столбцам.
5. Редукция столбцов.
6. Вычисление оценок нулевых клеток.
7. Редукция матрицы.
8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
9. Вычисление итоговой длины пути и построение маршрута.

Более подробно эти этапы решения задачи о бродячем торговце раскрыты ниже.

Подробная методика решения задачи коммивояжера

В целях лучшего понимания задачи будем оперировать не понятиями графа, его вершин и т.д., а понятиями простыми и максимально приближенными к реальности: вершины графа будут называться «города», ребра их соединяющие – «дороги».

Итак, методика решения задачи коммивояжера:

1. Построение матрицы с исходными данными

Сначала необходимо длины дорог соединяющих города представить в виде следующей таблицы:

В нашем примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м другим, в зависимости от направления движения (т.к. некоторые ж/д пути могут быть с односторонним движением и т.д.).

Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности. Это сделано для того, чтобы данный отрезок путь был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.

2. Нахождение минимума по строкам

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

3. Редукция строк

Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).

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

4. Нахождение минимума по столбцам

5. Редукция столбцов

Вычитаем из каждого элемента матрицы соответствующее ему dj.

В итоге в каждом столбце будет хотя бы одна нулевая клетка .

6. Вычисление оценок нулевых клеток

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

И так по всем нулевым клеткам:

7. Редукция матрицы

Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М ». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 4-ого к 2-му).

Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку, соответствующую обратному пути , ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).

8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9

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

Если все отрезки пути найдены (или найдены еще не все отрезки, но оставшаяся часть пути очевидна) – переходим к пункту 9 .

9. Вычисление итоговой длины пути и построение маршрута

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

В нашем примере маршрут получился следующий: 4 → 2 → 3 → 1 → 4 .

Общая длина пути: L = 30 .

Практическое применение задачи коммивояжера

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

Решение задачи коммивояжера онлайн

Галяутдинов Р.Р.

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

Голосование: 25, 14

Что это такое?

Иногда возникшую NP-полную задачу приходится решать. В таком случае, во-первых, иногда возможно сократить полный перебор так, что алгоритм, оставаясь в худшем случае экспоненциальным, будет работать за приемлемое время на реальных данных. Во-вторых, не точное решение, а некоторое приближение к нему может оказаться удовлетворительным. Алгоритмы, дающие такие решения, называются приближенными.

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

Методы решения труднорешаемых задач

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

Оценки качества приближенных алгоритмов

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

Мы будем говорить, что алгоритм решает задачу с ошибкой не более чем в ρ (n) раз, если

Max(C ⁄ C *, C * ⁄ C) ≤ ρ (n)

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

Иногда удобнее использовать относительную ошибку, которая определяется как | C − C *| ⁄ C *

Мы будем говорить, что алгоритм имеет ошибку не более ε (n), если

| C − C *| ⁄ C * ≤ ε (n)

Легко проверить, что ε (n) может быть ограничена сверху через функцию ρ (n), а именно ε (n) ≤ ρ (n) − 1. В самом деле для задач на минимум это неравенство превращается в равенство. Для задач на максимум ε (n) = (ρ (n) − 1) ⁄ ρ (n) (далее нужно вспомнить, что ρ (n) ≥ 1.

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

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

Схема приближения называется полиномиальной, если для любого фиксированного ε > 0 время её работы не превосходит некоторого полинома от n . Схема приближения называется полностью полиномиальной, если время её работы ограничено некоторым полиномом от n и от 1 ⁄ ε .

Задача коммивояжера — полигон для испытания оптимизационных методов

Формулировка задачи коммивояжера (1934 г.):

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

В терминах теории графов задачу можно сформулировать так: имеется полный ориентированный граф G = (V , E), каждой дуге (u , v) которого сопоставлен вес c (u , v). Требуется найти в этом графе гамильтонов контур наименьшей стоимости.

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

1. В обеих формулировках предполагается c (u , v) ≥ 0; c (u , u) = ∞ для всех u , v ∈ V .
2. В наивной формулировке предполагается c (u , v) = c (v , u) для всех u , v ∈ V , т. е. граф можно считать неориентированным. Такая задача называется симметричной задачей коммивояжера. Однако, в общем случае, это необязательно.
3. В наивной формулировке предполагаем, что для всех u , v , w ∈ V с (u , v) ≤ c (u , w) + c (w , v) (неравенство треугольника), что нередко выполняется в практических задачах. Однако вообще говоря, это неверно.

Теорема

Пусть P ≠ NP , ρ ≥ 1. Тогда не существует полиномиального приближенного алгоритма, решающего общую (более того, симметричную) задачу коммивояжера с ошибкой не более чем в ρ раз.

Доказательство. Для доказательства заметим, что взяв произвольный граф G = (V , E) и сопоставив ему полный граф G ′ с функцией стоимости c (u , v) = 1, если (u , v) ∈ E и ρ | V | + 1 иначе. Убедимся, что наш полиномиальный алгоритм будет определять, есть ли в графе G гамильтонов цикл, что невозможно.

Метод ветвей и границ ("поиск с возвратом", "backtracking")

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

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

Рассмотрим дискретную экстремальную (для определенности — на минимум) задачу в общем виде:

Пусть задано дискретное множество A и определенная на нем функция f . Обозначим минимум функции f на X как F (X).

Требуется найти x 0 ∈ A: f (x 0) = F (A)

Замечание 1

Пусть A = A 0 ∪ A 1 ∪ … ∪ A k , A i ∩ A j = Ø, i ≠ j . Причем F (A) < F (A 0), т. е. на A 0 минимум не достигается.

Тогда справедливо следующее: F (A) = min { F (A i) | i ∈ 1: k }

Замечание 2

Пусть Φ — функция, заданная на совокупности подмножеств множества A так, что Φ (X) ≤ F (X) ∀ X ⊂ A

Пусть x * — произвольный элемент A и пусть f * = f (x *).

Тогда справедливо следующее: F (A) = min { f *, min { F (A i) | i ∈ 1: k , Φ (A i) ≤ f *} }

Эти два соображения позволяют предложить следующую технологию поиска минимума. Разобьем множество A на какие-либо подмножества A i и на каждом из них найдем нижнюю оценку Φ . Для элементов множества A будем вычислять значения функции f и запоминать наименьшее в качестве рекордного значения. Все подмножества, у которых оценка выше рекордного значения функции (f *), объединим в подмножество A 0 , чтобы в дальнейшем не рассматривать.

Теперь выберем какое-либо из множеств A i , i > 0. Разобьем это множество на несколько более мелких подмножеств. При этом мы будем продолжать улучшать рекордное значение f *. Этот процесс продолжается до тех пор, пока не будут просмотрены все множества A i , i > 0.

Более наглядно метод ветвей и границ (поиск с возвратом) можно объяснить с помощью дерева возможностей. Узлы такого дерева можно рассматривать как совокупности конфигураций (подмножества A i множества A), а каждый потомок некоторого узла представляет подмножество этой совокупности. Наконец, каждый лист представляет собой отдельную конфигурацию.

Пример 1. Задача коммивояжера (алгоритм Литтла)

Рассмотрим работу этого алгоритма на конкретном примере.

Пусть имеется граф, заданный матрицей смежности:

—	6	4	8	7	14
6	—	7	11	7	10
4	7	—	4	3	10
8	11	4	—	5	11
7	7	3	5	—	7
14	10	10	11	7	—

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

Приведем исходную матрицу по строкам

Исходная

—	6	4	8	7	14
6	—	7	11	7	10
4	7	—	4	3	10
8	11	4	—	5	11
7	7	3	5	—	7
14	10	10	11	7	—

Приведенная по строкам

—	2	0	4	3	10	|4
0	—	1	5	1	4	|6
1	4	—	1	0	7	|3
4	7	0	—	1	7	|4
4	4	0	2	—	4	|3
7	3	3	4	0	—	|7

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

(Отметим, что сумма констант приведения есть 4 + 6 + 3 + 4 + 3 + 7 = 27)

А затем по столбцам:

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

(Отметим, что сумма констант приведения здесь есть 0 + 2 + 0 + 1 + 0 + 4 = 7, а всех констант: 27 + 7 = 34)

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

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

Назовем оценкой нуля в позиции (i , j) в матрице сумму минимальных элементов в i -й строке и j -м столбце (не считая сам этот ноль). Оценим теперь каждый ноль в приведенной матрице:

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

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

Рассмотрим ребро, соответствующее нулю с максимальной оценкой. В данном случае это ребро (1, 2). Таким образом, как только что было замечено, класс всех туров разбивается на два: содержащих ребро (1, 2) и не содержащих его. Нижняя оценка стоимости второго класса туров увеличивается до 35. Чтобы определить оценку для первого класса туров удалим из матрицы строку 1 и столбец 2 (Обозначим ее как C [(1,2)]):

Т. к. матрицу удалось привести на 1 (по 1-му столбцу), то оценка класса туров с ребром (1, 2) увеличивается на 1 и становится равной 35.

Разбиение на классы и сами оценки можно представить в виде дерева:

Таким образом, класс (ВСЕ) был разбит на два и были вычислены соответствующие оценки.

Выберем теперь класс с наименьшей оценкой и повторим этот процесс для него. Затем из двух полученных классов выберем тот, у которого оценка минимальна и разобьем его. Так будем повторять до тех пор, пока не достигнем листа дерева. Т. е. пока не получим матрицу 0×0:

C [(1, 2); [−](a 1 , b 1); [−](a 2 , b 2); … [−](a k , b k)]

Где (каждое) −(x , y) означает, что матрица соответствует классу, не содержащему ребро (x , y) Удалив из обозначения матрицы элементы вида −(x , y), получим следующее:

(c 0 , d 0); (c 1 , d 1); … (c n , d n)

Вершина (5, 4) дерева будет соответствовать классу, содержащему ребра: (1, 2); (3, 1); (6, 5); (2, 6); (4, 3); (5, 4). Этот класс, очевидно, состоит из одного полного тура (1, 2, 6, 5, 4, 3, 1) со стоимостью = 36 (для полного тура его минимальная оценка равна точной стоимости)

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

Матрица, соответствующая классу туров, не содержащих ребро (1, 2), приведенная по второму столбцу, будет выглядеть так:

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

Она была получена из матрицы, соответствующей классу всех туров путем установки прочерка (обозначающего бесконечную стоимость перелета) вместо элемента (1, 2). Т.е. с 1,2 = ∞. Обозначим ее как C [−(1,2)]

Т. к. максимальная оценка нуля 3 (элемент 1,3) получаем, что оценка для ветви −(1,3) равна 38.

Вычеркивая первую строку и первый столбец, получим матрицу, приводимую на 1 по четвертой строке. То есть оценка ветви −(1,2)(1,3) становится равной 36. Дальнейшее ветвление будем продолжать уже с учетом найденного рекордного значения (36):

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

Удовлетворительных теоретических оценок алгоритма Литтла и ему подобных нет, но практика показывает, что на современных машинах они позволяют решать задачу коммивояжера с количеством вершин ≈ 100. Кроме того, алгоритмы типа ветвей и границ являются эффективными эвристическими процедурами. Если нет возможности доводить их до конца.

Пример 2. Задача о размыкании контуров

Тот же подход можно применить к задаче о размыкании контуров. Постановка задачи:

Пусть задан граф G = (V , E), каждой дуге (u , v) которого сопоставлено положительное число c (u , v) — вес этой дуги.

Требуется найти E 0 ⊂ E так, чтобы граф (V , E 0) не имел контуров и сумма весов дуг (из E 0) была максимальной.

Рассмотрим вспомогательную задачу (обозначим ее (E , E *)) аналогичную только что сформулированной, но с дополнительным параметром — множеством E * ⊂ E из которого дуги удалять нельзя (при этом будем требовать, чтобы в графе (V , E *) не было контуров).

Если имеется задача (E , E *) то возможно все множество ее решений разбить на два класса следующим образом.

Рассмотрим дугу (u , v) ∈ E \ E * такую, что в графе (V , E * ∪ (u , v)) нет контуров.

Тогда множество решений задачи можно разбить на два:

1. множество решений задачи (E \ (u , v), E *)
2. множество решений задачи (E , E* ∪ (u , v))

Исходная задача о размыкании контуров, очевидно, является задачей (E , Ø).

Введем теперь функцию est(E , E 0) следующим образом:

1. если граф (V , E) не содержит циклов, то est(E , E 0) = 0
2. иначе, пусть E cyc — цикл, тогда: est(E , E 0) = est(E \ E cyc , E 0) + c cyc , где c cyc = min{ c (u , v) | (u , v) ∈ E cyc \ E 0 } (т. е. мин. вес, которым можно разомкнуть этот цикл)

Несложно показать, что

V (E , E 0) ≥ est(E , E 0),

где v (E , E 0) — минимум суммы весов дуг, удаление которых из E \ E 0 размыкает все контуры графа.

Метод локальных улучшений ("локальный поиск")

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

Более конкретно стратегия локального поиска такова:

• Начните с произвольного решения
• Для улучшения текущего решения примените к нему какое-либо преобразование из заданной совокупности преобразований. Это улучшенное решение становится текущим решением
• Повторяйте указанную процедуру до тех пор, пока ни одно из преобразований в заданной совокупности не позволит улучшить текущее решение

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

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

Рассмотрим точный алгоритм нахождения минимального остовного дерева в графе с помощью метода локального поиска. Локальные преобразования будут таковы: мы берем то или иное ребро, не относящееся к текущему остовному дереву и добавляем его к дереву (получая цикл), а затем убираем из этого цикла одно ребро (с наивысшей стоимостью). Это продолжается, пока все ребра вне дерева не будут иметь наивысшую стоимость среди всех ребер в цикле, который образуется при добавлении его к дереву (одна эта проверка требует времени O (| V || E |)). Этот алгоритм работает медленнее, чем алгоритмы Прима и Крускала, и служит примером нерационального использования локального поиска для не NP-полных задач.

Пример 2. Задача коммивояжера ("двойной выбор")

Простейшее преобразование, которым можно воспользоваться в симметричной задаче коммивояжера, является так называемый "двойной выбор" . Он заключается в том, что мы выбираем любые два ребра (например (a , b) и (c , d)), удаляем их и "перекоммутируем" соединявшиеся ими точки так, чтобы образовался новый маршрут. Если сумма стоимостей двух новых ребер оказалась меньше, чем двух старых, то мы нашли улучшенный маршрут.

Рассмотрим тот же граф, для которого мы строили остовное дерево. Выберем в качестве начального маршрута (a , b , c , d , e) и применим к нему "двойной выбор". Легко убедиться, что на рисунке "в" нельзя удалить ни одну пару ребер, выгодно заменив её другой.

Двойной выбор можно обобщить на k -выбор. В этом случае мы удаляем до k ребер и "перекоммутируем" оставшиеся элементы в любом порядке, пытаясь получить маршрут. Мы, вообще говоря, не требуем, чтобы удаляемые ребра были несмежными.

Легко убедиться в том, что количество различных преобразований, которые нужно рассмотреть при k -выборе равно O (| V | k). Однако время, требуемое для получения какого-либо оптимального маршрута, может оказаться значительно больше.

На практике очень эффективным является "выбор с переменной глубиной". Он с большой вероятностью обеспечивает получение оптимального маршрута для | V | = 40 − 100.

Пример 3. Задача размещения блоков

Формулировка задачи одномерного размещения блоков: требуется упорядочить вершины неориентированного графа G = (V , E) с весами на ребрах c (u , v), пронумеровав их числами 1 … n так, чтобы минимизировать ∑ i , j = 1… n | i − j | c (v i , v j); n = | V |.

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

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

Для нахождения локально-оптимальных решений задачи размещения блоков можно использовать такие локальные преобразования:

1. Произвести взаимную перестановку смежных блоков v i и v i +1 , если результирующий порядок имеет меньшую стоимость. Пусть

   L (j) = ∑ k =1… j −1 c (v k , v j);
   R (j) = ∑ k = j +1… n c (v k , v j).

   Улучшение можно выполнить, если

   L (i) − R (i) + R (i +1) − L (i +1) + 2 c (v i , v i +1) < 0

2. Взять блок v i и вставить его между некоторыми блоками v i и v i +1 при некоторых значениях i и j .
3. Выполнить взаимную перестановку двух блоков v i и v j .

Как и в задаче коммивояжера мы не в состоянии точно оценить время, необходимое для нахождения локального оптимума. Можно показать, что, если ограничиться преобразованием (1 ), времени O (| V |) будет достаточно, чтобы проверить, является ли выполняемое преобразование улучшающим, и вычислять L (i) и R (i). Для преобразований (2 ) и (3 ) это время увеличивается до O (| V | 2). Но это не есть оценка времени нахождения локального оптимума, так как каждое улучшение может создавать возможности для новых улучшений.

Приближенные и эвристические методы

В этом разделе мы рассмотрим алгоритмы, работающие за известное нам полиномиальное время и решающие "переборные" задачи с некоторой известной нам ошибкой. Грань между приближенными и эвристическими методами размыта. Некоторые выделяют как приближенные алгоритмы те, в которых возможно регулировать погрешность, т. е. схемы приближения.

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

Пример 1. Задача коммивояжера (деревянный алгоритм)

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

Первый из них, так называемый деревянный алгоритм, состоит в следующем: построим для нашего графа минимальное покрывающее дерево с помощью алгоритма Прима, а затем совершим обход дерева в порядке root-left-right , удаляя повторяющиеся вершины.

Время работы этого алгоритма равно Θ(E) = Θ(V 2).

Пример 1. Задача коммивояжера (жадный алгоритм и алгоритм Карга-Томпсона)

Самый очевидный алгоритм решения задачи коммивояжера — жадный: из текущего города иди в ближайший из тех, куда ещё не ходил. Если выполняется неравенство треугольника, нетрудно доказать, что этот алгоритм ошибается не более, чем в два раза. Трудоемкость этого алгоритма O (V 2).

Алгоритм Карга-Томпсона (эвристика ближайшей точки) чуть менее очевиден: сначала возьмем две ближайшие вершины (вырожденный тур), затем в цикле по всем ребрам уже построенного тура для каждого ребра (u , v) выберем из свободных вершин такую w , чтобы c (u , w) + c (w , v) − c (u , v) было минимальным и включим w в тур между u и v . Для этого способа также ρ = 2, однако его трудоемкость составляет уже O (V 3).

Пример 2. Задача о вершинном покрытии

Напомним, что вершинным покрытием неориентированного графа G =(V , E) мы называем некоторое семейство его вершин V ′ с таким свойством: для всякого ребра (u , v) графа G хотя бы один из его концов u или v содержится в V ′. Размером вершинного покрытия считаем количество входящих в него вершин.

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

Пусть С — это уже построенная часть вершинного покрытия, а E ′ содержит непокрытые ребра графа. На каждом шаге мы берем ребро из E ′ и добавляем его концы u и v в C , а из E ′ изымаем все ребра имеющие своим концом u или v . И так пока множество E ′ не станет пустым. Время работы этого алгоритма есть O (E).

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

Дано конечно множество X и семейство его подмножеств F . При этом:

X =∪ S ∈ F S

Мы ищем минимальное число подмножеств из F , которые вместе покрывают множество X , т. е. семейство С наименьшей мощности, для которого:

X =∪ S ∈ C S

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

Мы будем решать задачу с помощью жадного приближенного алгоритма. Пусть множество U содержит ещё не покрытые элементы, а семейство C — уже включенные в покрытие подмножества. На каждом шаге производится жадный выбор: в качестве S берется множество, покрывающее наибольшее число ещё не покрытых элементов.

Так происходит, пока U не пусто. Трудоемкость алгоритма составляет O (| X |·| F |·min(| X |,| F |)).

Размер покрытия, даваемого этим алгоритмом, превосходит минимально возможный не более чем в H (max{| S |: S ∈ F }) раз (где H (d) — сумма первых d членов гармонического ряда) или, что тоже самое, в (ln| X | + 1) раз.

Псевдополиномиальные алгоритмы

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

Пример 1. Задача о суммах подмножеств ("табличный" алгоритм)

Пусть задана пара (S , t), где S = { x 1 , x 2 , …, x n } представляет собой множество положительных целых чисел, а t — положительное целое число. Требуется отыскать среди подмножеств множества S , сумма которых не превосходит t , такое, у которого сумма ближе всего к t .

Пусть | S | = n . Обозначим (k , w) — задачу, в которой имеется k первых чисел из S и нужно набрать сумму w . Таким образом исходная задача — это задача (n , t).

Для решения задачи построим таблицу T [ n , t + 1], в клетку T [ i , j ] которой будем записывать оптимальное решение задачи (i , j).

Первый столбец заполним нулями. Первую строку заполним сначала нулями, а начиная с клетки (1, x 1) — числами x 1 . Клетку T [ i , j ] (i , j > 1) будем заполнять по правилу:

1. Если j − x i > 0, то y:= T [ i − 1, j − x i ], иначе y:= 0;
2. T [ i , j ] := max(T [ i − 1, j ], y + x i)

	0	1	2	3	4	5	6	7	8	9	10	11	12	13
3	0	0	0	3	3	3	3	3	3	3	3	3	3	3
5	0	0	0	3	3	5	5	5	8	8	8	8	8	8
7	0	0	0	3	3	5	5	7	8	8	10	10	12	12
9	0	0	0	3	3	5	5	7	8	9	10	10	12	12
11	0	0	0	3	3	5	5	7	8	9	10	11	12	12

S = {3, 5, 7, 9, 11} t = 13;

Таблица примет такой вид. Ответ: нет подмножества весом 13, ближе всего снизу 12.

Условие (2) говорит о том, что оптимальная сумма может достигаться либо без использования x i (T [ i − 1, j ]), либо если x i входит в сумму (y + x i). В этом случае его надо прибавить к решению задачи (i − 1, j − x i), что и сохраняется в переменной y в условии (1). Из получившейся таблицы можно узнать и состав оптимальной суммы.

Трудоемкость этого алгоритма составляет O (n t) операций. Таким образом, если t будет велико, можно будет все числа поделить, к примеру, на 10, округлить и получить приближенный алгоритм.

Пример 2. Задача о суммах подмножеств ("списковый" алгоритм)

Пусть L — набор чисел, а x — некоторое число, тогда через L + x обозначим набор чисел, который получится, если ко всем элементам L прибавить x . В этом алгоритме также используется тот факт, что x i может как входить в сумму, так и не входить, то есть:

L i = L i −1 ∪ (L i −1 + x i)

Выкидывая из списка элементы, большие t получим L n — упорядоченный список всех возможных удовлетворяющих нас сумм подмножеств S . Остается взять максимальный (последний) элемент, чтобы получить решение задачи. Список L n может содержать до 2 n элементов (т. е. алгоритм экспоненциален), однако, т.к. все элементы различны, их не может быть более t . Налицо псевдополиномиальность.

Схемы приближения

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

Мы рассмотрим две схемы приближения для задачи о сумме подмножеств. Одна из них получается из "спискового" алгоритма, а другая называется алгоритмом Джонсона.

Пример 1. Задача о суммах подмножеств (полностью полиномиальная схема приближения)

Такая схема получается из "спискового" алгоритма, если хранить список L в сокращенной форме. Список L ′ называется δ -сокращением списка L , если L ′ является частью L и

∀ y ∈ L ∃ z ∈ L ′: z ≤ y , (y − z) ⁄ y ≤ δ

Например для δ = 0,1 и L = <10, 11, 12, 15, 20, 21, 22, 23, 24, 29> список L ′ = <10, 12, 15, 20, 23, 29> является δ -сокращением. Сокращение упорядоченного списка из m элементов требует Θ (m) операций. Таким образом, можно доказать, что "списковый" алгоритм, хранящий вместо полного списка сокращенный является полностью полиномиальной схемой приближения.

Пример 2. Задача о суммах подмножеств (алгоритм Джонсона)

Алгоритм, кроме множества S и числа t принимает на вход целочисленный параметр m > 2. Назовем i -е число большим, если x i > t ⁄(m +1). Описание алгоритма:

1. Перебрать все подмножества из больших чисел и найти множество больших чисел с суммой t ′: t ′ < t , Δ = t − t ′ min
2. Если Δ = 0, алгоритм закончен.
3. Перебрать все малые числа в порядке убывания. Если очередное x i ≤ Δ , то t ′:= t ′ + x i , Δ := Δ − x i ;
4. Когда перебор по малым числам закончен, выдать t ′ в качестве ответа.

Пусть k — количество больших чисел. Тогда можно доказать, что количество подходящих нам подмножеств из больших чисел составляет O (k m) ≤ O (n m). Таким образом, перебор имеет полиномиальную, возрастающую с m сложность. Корме того, можно показать, что:

T ′⁄ t ≥ 1 − 1 ⁄ (m + 1) 1 − 1 ⁄ (m + 1) ≤ t ′⁄ t* ≤ 1

то есть относительная погрешность ε = 1⁄ (m +1). Таким образом, эта схема приближения является полиномиальной, но не является полностью полиномиальной.

Метод случайного поиска

Обычно выбор решения можно представить последовательностью выборов. Если делать эти выборы с помощью какого-либо случайного механизма, то решение находится очень быстро, так что можно находить решение многократно и запоминать "рекорд", т. е. наилучшее из встретившихся решений. Этот наивный подход существенно улучшается, когда удается учесть в случайном механизме перспективность тех или иных выборов, т. е. комбинировать случайный поиск с эвристическим методом и методом локального поиска. Такие методы применяются, например, при составлении расписаний для Аэрофлота.

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

Пожалуйста. На запрос "метод случайного поиска" поисковик Google анонсирует более 300000 ссылок. Этой информации должно хватить..........

Благодарю за статью, разобрался с алгоритмом Литтла. Хотел запомнить сайт и был удивлен, увидев домен родного университета:)

Про запрет переходов выше замечено верно - хотелось бы видеть здесь пояснения.

Спасибо за понятное разъяснение алгоритма Литтла. Но не учтена важная деталь: при выборе следующего ребра нужно учитывать, чтобы путь из набора ребер последовательно охватывал все точки. Так как ребра добавляем в случайном порядке, то приходится отслеживать наличие микроциклов (например выбрали ребро 1,0 - значит 0, 1 уже нельзя выбирать, или выбрали 0,1 и 1,2 - тогда нельзя выбирать 2,0 и 2,1 и т.д.), что отследить не так уж и просто. Я реализовал алгоритм на C#, циклы отслеживал с помощью специального класса, который содержал набор микроциклов и вычеркивал запрещенные ребра при добавлении в него новых и ребер и восстанавливал ребра при удалении ребер.

Реализация алгоритма оказалась очень сложна на практике, а его отладка просто ад. Код занял 512 строк. 20 точек обрабатывает за 0.1 - 10 секунд - длительность сильно зависит от входного набора. Большее количество уже за адекватное время не решает. Простейший переборщик у меня находит решение для 13 вершин за 1 секунду.

Если нужна реализация алгоритма на C# - пишите на почту [email protected].

Решение задачи коммивояжера методом ветвей и границ (алгоритм Литтла)

http://igorvn.ucoz.ru/load/kursovye/kommivojazher/2-1-0-15

Метод Литла работает только на небольшом количестве точек поэтому во всех примерах их не более 10 Начиная 15 точек он дает приближенный результат 1-2 % больше минимального и это заложено в порядке определения каждого хода (редукции) непонятно на каком основании это делается.Ведь формально мы получаем другую матрицу.

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

Благодарим. Не сомневаемся в Вашей добросовестности и компетентности. Но файлы *.doc мы не размещаем. Если выложите его содержимое в общедоступное место со статусом постоянного хранения и включите ссылку в текст своего нового комментария, опубликуем для всеобщего обозрения.

Всем, кто хочет узнать про все теоретические ошибки метода Литтла, прошу сначала объяснить себе, что такое редукция и на каком это математическом основании оно проводится. Кроме того, Русский метод, разработанный мной, могу выслать совершенно бесплатно. Мой email: [email protected]

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

· Полный перебор;

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

· Случайный перебор;

Обычно выбор решения можно представить последовательностью выборов. Если делать эти выборы с помощью какого-либо случайного механизма, то решение находится очень быстро, так что можно находить решение многократно и запоминать «рекорд», т. е. наилучшее из встретившихся решений. Этот наивный подход существенно улучшается, когда удается учесть в случайном механизме перспективность тех или иных выборов, т. е. комбинировать случайный поиск с эвристическим методом и методом локального поиска. Такие методы применяются, например, при составлении расписаний для Аэрофлота.

· Жадные алгоритмы (метод ближайшего соседа, метод включения ближайшего города, метод самого дешевого включения);

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

· Метод минимального остовного дерева (деревянный алгоритм);

В основе алгоритма лежит утверждение: «Если справедливо неравенство треугольника, то для каждой цепи верно, что расстояние от начала до конца цепи меньше (или равно) суммарной длины всех ребер цепи». Это обобщение расхожего убеждения, что прямая короче кривой. Деревянный алгоритм для решения задачи коммивояжера будет следующим: строится на входной сети задачи коммивояжера кратчайшее остовное дерево и удваиваются все его ребра. В результате получаем граф - связный с вершинами, имеющими только четные степени. Затем строится эйлеров цикл, начиная с вершины 1, цикл задается перечнем вершин. Просматривается перечень вершин, начиная с 1, и зачеркивается каждая вершина, которая повторяет уже встреченную в последовательности. Останется тур, который и является результатом алгоритма.

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

· Метод имитации отжига.

Экзотическое название данного алгоритма связано с методами имитационного моделирования в статистической физике, основанными на технике Монте-Карло. Исследование кристаллической решетки и поведения атомов при медленном остывании тела привело к появлению на свет вероятностных алгоритмов, которые оказались чрезвычайно эффективными в комбинаторной оптимизации. Впервые это было замечено в 1983 году. Сегодня этот алгоритм является популярным как среди практиков благодаря своей простоте, гибкости и эффективности, так и среди теоретиков, поскольку для данного алгоритма удается аналитически исследовать его свойства и доказать асимптотическую сходимость. Алгоритм имитации отжига относится к классу пороговых алгоритмов локального поиска. На каждом шаге этого алгоритма для текущего решения i k в его окрестности N(i k) выбирается некоторое решение j и, если разность по целевой функции между новым и текущим решением не превосходит заданного порога t k , то новое решение j заменяет текущее. В противном случае выбирается новое соседнее решение. На практике применяются различные модификации более эффективных методов:

· Метод ветвей и границ;

Метод ветвей и границ предложен в 1963 году группой авторов Дж. Литлом, К. Мурти, Д. Суини, К. Кэролом. Широко используемый вариант поиска с возвращением, фактически является лишь специальным частным случаем метода поиска с ограничениями 4 . Ограничения в данном случае основываются на предположении, что на множестве возможных и частичных решений задана некоторая функция цены и что нужно найти оптимальное решение, т.е. решение с наименьшей ценой. Для применения метода ветвей и границ функция цены должна обладать тем свойством, что цена любого частичного решения не превышает цены любого расширения этого частичного решения (Заметим, что в большинстве случаев функция цены неотрицательна и даже удовлетворяет более сильному требованию). Столь большой успех применения данного метода объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера.

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

· Метод генетических алгоритмов;

«Отцом-основателем» генетических алгоритмов считается Джон Холланд, книга которого «Адаптация в естественных и искусственных системах» (1975) является основополагающим трудом в этой области исследований. Генетический алгоритм - это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе. Генетические алгоритмы служат, главным образом, для поиска решений в многомерных пространствах поиска.

· алгоритм муравьиной колонии.

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

2.4 Метод ветвей и границ

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

(1) Построение матрицы с исходными данными.

(2) Нахождение минимума по строкам.

(3) Редукция строк.

(4) Нахождение минимума по столбцам.

(5) Редукция столбцов.

(6) Вычисление оценок нулевых клеток.

(7) Редукция матрицы.

(8) Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.

(9) Вычисление итоговой длины пути и построение маршрута.

Подробная методика решения

В целях лучшего понимания задачи будем оперировать не понятиями графа, его вершин и т.д., а понятиями простыми и максимально приближенными к реальности: вершины графа будут называться «города», ребра их соединяющие – «дороги».

Итак, методика решения задачи коммивояжера:

1. Построение матрицы с исходными данными

Сначала необходимо длины дорог соединяющих города представить в виде следующей таблицы:

Таблица 1

В нашем примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м другим, в зависимости от направления движения (т.к. некоторые ж/д пути могут быть с односторонним движением и т.д.).

Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности. Это сделано для того, чтобы данный отрезок путь был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.

2. Нахождение минимума по строкам

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

Таблица 2

3. редукция строк

Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).

Таблица 3

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

4. Нахождение минимума по столбцам

Таблица 4

5. редукция столбцов

Вычитаем из каждого элемента матрицы соответствующее ему dj.

Таблица 5

В итоге в каждом столбце будет хотя бы одна нулевая клетка .

6. Вычисление оценок нулевых клеток

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

Таблица 6

И так по всем нулевым клеткам:

Таблица 7

7. редукция матрицы

Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 4-ого к 2-му).

Таблица 8

Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку соответствующую обратному пути ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).

Таблица 9

8. если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9

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

Если все отрезки пути найдены (или найдены еще не все отрезков, но оставшаяся часть пути очевидна) – переходим к пункту 9.

9. вычисление итоговой длины пути и построение маршрута

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

В нашем примере маршрут получился следующий: 4 → 2 → 3 → 1 → 4.

Общая длина пути: L = 30.

Заключение

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

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

Список использованной литературы

1. Кирсанов М.Н. «Графы в Maple», М. Физматлит, 2007.

2. Зыков А.А. «Основы теории графов» , М. «Вузовская книга», 2014

3. Уилсон Р. «Введение в теорию графов» , М. «Мир», 2010

4. Берж К. "Теория графов и ее применение", М., ИЛ, 2008;

5. Гарднер М. "Математические досуги", М. "Мир", 2009(глава 35);

6. "В помощь учителю математики", Йошкар-Ола, 2011 (ст. "Изучение элементов теории графов");

7. Олехник С.Н., Нестеренко Ю.В., Потапов М.К. "Старинные занимательные задачи", М. "Наука", 2008;

8. Гарднер М. "Математические головоломки и развлечения", М. "Мир",2012;

9. Оре О. "Графы и их применения", М. "Мир", 2011;

10. Зыков А.А. "Теория конечных графов", Новосибирск, "Наука", 2009;

11. Реньи А., "Трилогия о математике", М., "Мир", 2010.

Размещено на Allbest.ru

©2015-2019 сайт
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-08-08

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

Назначение сервиса . С помощью сервиса можно проверить свое решение или получить новое решение задачи коммивояжёра двумя методами: методом ветвей и границ и венгерским методом .

Математическая модель задачи коммивояжера

Сформулированная задача - задача целочисленная. Пусть х ij =1 , если путешественник переезжает из i -ого города в j -ый и х ij =0 , если это не так.
Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.
Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u 1 =0 , u n +1 =n . Для того, чтобы избежать замкнутых путей, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные x ij и переменные u i (u i целые неотрицательные числа).

U i -u j +nx ij ≤ n-1, j=2..n+1, i=1..n, i≠j, при i=1 j≠n+1
0≤u i ≤n, x in+1 =x i1 , i=2..n

Методы решения задачи коммивояжера

1. метод ветвей и границ (алгоритм Литтла или исключения подциклов). Пример решения методом ветвей и границ ;
2. венгерский метод. Пример решения венгерским методом .

Алгоритм Литтла или исключения подциклов

1. Операция редукции по строкам: в каждой строке матрицы находят минимальный элемент d min и вычитают его из всех элементов соответствующей строки. Нижняя граница: H=∑d min .
2. Операция редукции по столбцам: в каждом столбце матрицы выбирают минимальный элемент d min , и вычитают его из всех элементов соответствующего столбца. Нижняя граница: H=H+∑d min .
3. Константа приведения H является нижней границей множества всех допустимых гамильтоновых контуров.
4. Поиск степеней нулей для приведенной по строкам и столбцам матрицы. Для этого временно нули в матице заменяэт на знак «∞» и находят сумму минимальных элементов строки и столбца, соответствующих этому нулю.
5. Выбирают дугу (i,j) , для которой степень нулевого элемента достигает максимального значения.
6. Разбивают множество всех гамильтоновых контуров на два подмножества: подмножество гамильтоновых контуров содержащих дугу (i,j) и не содержащих ее (i*,j*) . Для получения матрицы контуров, включающих дугу (i,j) , вычеркивают в матрице строку i и столбец j . Чтобы не допустить образования негамильтонова контура, заменяют симметричный элемент (j,i) на знак «∞». Исключение дуги достигается заменой элемента в матрице на ∞.
7. Проводят приведение матрицы гамильтоновых контуров с поиском констант приведения H(i,j) и H(i*,j*) .
8. Сравнивают нижние границы подмножества гамильтоновых контуров H(i,j) и H(i*,j*) . Если H(i,j)
9. Если в результате ветвлений получается матрица (2x2) , то определяют полученный ветвлением гамильтонов контур и его длину.
10. Сравнивают длину гамильтонова контура с нижними границами оборванных ветвей. Если длина контура не превышает их нижних границ, то задача решена. В противном случае развивают ветви подмножеств с нижней границей, меньшей полученного контура, до тех пор, пока не получится маршрут с меньшей длиной.

Пример . Решить по алгоритму Литтла задачу коммивояжера с матрицей

	1	2	3	4
1	-	5	8	7
2	5	-	6	15
3	8	6	-	10
4	7	15	10	-

Решение . Возьмем в качестве произвольного маршрута: X 0 = (1,2);(2,3);(3,4);(4,5);(5,1). Тогда F(X 0) = 20 + 14 + 6 + 12 + 5 = 57
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент: d i = min(j) d ij

i j	1	2	3	4	5	d i
1	M	20	18	12	8	8
2	5	M	14	7	11	5
3	12	18	M	6	11	6
4	11	17	11	M	12	11
5	5	5	5	5	M	5

Затем вычитаем d i из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

i j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	0	0	0	M

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
d j = min(i) d ij

i j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	0	0	0	M
d j	0	0	0	0	0

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

i j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	0	0	0	M

Сумма констант приведения определяет нижнюю границу H: H = ∑d i + ∑d j = 8+5+6+11+5+0+0+0+0+0 = 35
Элементы матрицы d ij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d ij ≥ 0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением: F(M k) = ∑d ij
Причем каждая строка и столбец входят в маршрут только один раз с элементом d ij .
Шаг №1 .
Определяем ребро ветвления

i j	1	2	3	4	5	d i
1	M	12	10	4	0(5)	4
2	0(2)	M	9	2	6	2
3	6	12	M	0(5)	5	5
4	0(0)	6	0(0)	M	1	0
5	0(0)	0(6)	0(0)	0(0)	M	0
d j	0	6	0	0	1	0

d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 0 = 5; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,2) = 0 + 6 = 6; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Исключение ребра (5,2) проводим путем замены элемента d 52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.

i j	1	2	3	4	5	d i
1	M	12	10	4	0	0
2	0	M	9	2	6	0
3	6	12	M	0	5	0
4	0	6	0	M	1	0
5	0	M	0	0	M	0
d j	0	6	0	0	0	6

Нижняя граница гамильтоновых циклов этого подмножества: H(5*,2*) = 35 + 6 = 41
Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d 25 заменяем на М, для исключения образования негамильтонова цикла.

i j	1	3	4	5	d i
1	M	10	4	0	0
2	0	9	2	M	0
3	6	M	0	5	0
4	0	0	M	1	0
d j	0	0	0	0	0

Нижняя граница подмножества (5,2) равна: H(5,2) = 35 + 0 = 35 ≤ 41
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 35
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	3	4	5	d i
1	M	10	4	0(5)	4
2	0(2)	9	2	M	2
3	6	M	0(7)	5	5
4	0(0)	0(9)	M	1	0
d j	0	9	2	1	0

d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 2 = 7; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 9 = 9;
Наибольшая сумма констант приведения равна (0 + 9) = 9 для ребра (4,3), следовательно, множество разбивается на два подмножества (4,3) и (4*,3*).
Исключение ребра (4,3) проводим путем замены элемента d 43 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,3*), в результате получим редуцированную матрицу.

i j	1	3	4	5	d i
1	M	10	4	0	0
2	0	9	2	M	0
3	6	M	0	5	0
4	0	M	M	1	0
d j	0	9	0	0	9

Нижняя граница гамильтоновых циклов этого подмножества: H(4*,3*) = 35 + 9 = 44
Включение ребра (4,3) проводится путем исключения всех элементов 4-ой строки и 3-го столбца, в которой элемент d 34 заменяем на М, для исключения образования негамильтонова цикла.

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

i j	1	4	5	d i
1	M	4	0	0
2	0	2	M	0
3	6	M	5	5
d j	0	2	0	7

Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 7
Нижняя граница подмножества (4,3) равна: H(4,3) = 35 + 7 = 42 ≤ 44
Поскольку 42 > 41, исключаем подмножество (5,2) для дальнейшего ветвления.
Возвращаемся к прежнему плану X 1 .
План X 1 .

i j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	M	0	0	M

Операция редукции .

i j	1	2	3	4	5
1	M	6	10	4	0
2	0	M	9	2	6
3	6	6	M	0	5
4	0	0	0	M	1
5	0	M	0	0	M

Шаг №1 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	2	3	4	5	d i
1	M	6	10	4	0(5)	4
2	0(2)	M	9	2	6	2
3	6	6	M	0(5)	5	5
4	0(0)	0(6)	0(0)	M	1	0
5	0(0)	M	0(0)	0(0)	M	0
d j	0	6	0	0	1	0

d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 0 = 5; d(4,1) = 0 + 0 = 0; d(4,2) = 0 + 6 = 6; d(4,3) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (4,2), следовательно, множество разбивается на два подмножества (4,2) и (4*,2*).
Исключение ребра (4,2) проводим путем замены элемента d 42 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,2*), в результате получим редуцированную матрицу.

i j	1	2	3	4	5	d i
1	M	6	10	4	0	0
2	0	M	9	2	6	0
3	6	6	M	0	5	0
4	0	M	0	M	1	0
5	0	M	0	0	M	0
d j	0	6	0	0	0	6

Нижняя граница гамильтоновых циклов этого подмножества: H(4*,2*) = 41 + 6 = 47
Включение ребра (4,2) проводится путем исключения всех элементов 4-ой строки и 2-го столбца, в которой элемент d 24 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j	1	3	4	5	d i
1	M	10	4	0	0
2	0	9	M	6	0
3	6	M	0	5	0
5	0	0	0	M	0
d j	0	0	0	0	0

Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 0
Нижняя граница подмножества (4,2) равна: H(4,2) = 41 + 0 = 41 ≤ 47
Поскольку нижняя граница этого подмножества (4,2) меньше, чем подмножества (4*,2*), то ребро (4,2) включаем в маршрут с новой границей H = 41
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	3	4	5	d i
1	M	10	4	0(9)	4
2	0(6)	9	M	6	6
3	6	M	0(5)	5	5
5	0(0)	0(9)	0(0)	M	0
d j	0	9	0	5	0

d(1,5) = 4 + 5 = 9; d(2,1) = 6 + 0 = 6; d(3,4) = 5 + 0 = 5; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 9 = 9; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (4 + 5) = 9 для ребра (1,5), следовательно, множество разбивается на два подмножества (1,5) и (1*,5*).
Исключение ребра (1,5) проводим путем замены элемента d 15 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,5*), в результате получим редуцированную матрицу.

i j	1	3	4	5	d i
1	M	10	4	M	4
2	0	9	M	6	0
3	6	M	0	5	0
5	0	0	0	M	0
d j	0	0	0	5	9

Нижняя граница гамильтоновых циклов этого подмножества: H(1*,5*) = 41 + 9 = 50
Включение ребра (1,5) проводится путем исключения всех элементов 1-ой строки и 5-го столбца, в которой элемент d 51 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j	1	3	4	d i
2	0	9	M	0
3	6	M	0	0
5	M	0	0	0
d j	0	0	0	0

Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 0
Нижняя граница подмножества (1,5) равна: H(1,5) = 41 + 0 = 41 ≤ 50
Поскольку нижняя граница этого подмножества (1,5) меньше, чем подмножества (1*,5*), то ребро (1,5) включаем в маршрут с новой границей H = 41
Шаг №3 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	3	4	d i
2	0(15)	9	M	9
3	6	M	0(6)	6
5	M	0(9)	0(0)	0
d j	6	9	0	0

d(2,1) = 9 + 6 = 15; d(3,4) = 6 + 0 = 6; d(5,3) = 0 + 9 = 9; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (9 + 6) = 15 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).
Исключение ребра (2,1) проводим путем замены элемента d 21 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу.

i j	1	3	4	d i
2	M	9	M	9
3	6	M	0	0
5	M	0	0	0
d j	6	0	0	15

Нижняя граница гамильтоновых циклов этого подмножества: H(2*,1*) = 41 + 15 = 56
Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d 12 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j	3	4	d i
3	M	0	0
5	0	0	0
d j	0	0	0

Сумма констант приведения сокращенной матрицы:
∑d i + ∑d j = 0
Нижняя граница подмножества (2,1) равна: H(2,1) = 41 + 0 = 41 ≤ 56
Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей H = 41.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,4) и (5,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(4,2), (2,1), (1,5), (5,3), (3,4). Длина маршрута равна F(Mk) = 41

Дерево решений.

																														1
								(5*,2*), H=41																																												(5,2)
(4*,2*), H=47																	(4,2)																															(4*,3*), H=44								(4,3)
								(1*,5*), H=50																	(1,5)
																(2*,1*), H=56																		(2,1)
																												(3,4)												(3*,4*), H=41
																								(5,3)								(5*,3*), H=41

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

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

Таблица 2

Таблица 3

Таблица 4

Изложим алгоритм Литтла на примере 1 предыдущего раздела. Повторно запишем матрицу:

Нам будет удобнее трактовать С ij как стоимость проезда из города i в город j. Допустим, что добрый мэр города j издал указ выплачивать каждому въехавшему в город коммивояжеру 5 долларов. Это означает, что любой тур подешевеет на 5 долларов, поскольку в любом туре нужно въехать в город j. Но поскольку все туры равномерно подешевели, то прежний минимальный тур будет и теперь стоить меньше всех. Добрый же поступок мэра можно представить как уменьшение всех чисел j-го столбца матрицы С на 5. Если бы мэр хотел спровадить коммивояжеров из j-го города и установил награду за выезд в размере 10 долларов, это можно было бы выразить вычитанием 10 из всех элементов j-й той строки. Это снова бы изменило стоимость каждого тура, но минимальный тур остался бы минимальным. Итак, доказана следующая лемма.

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

Для алгоритма нам будет удобно получить побольше нулей в матрице С, не получая там, однако, отрицательных чисел. Для этого мы вычтем из каждой строки ее минимальный элемент (это называется приведением по строкам, см. табл. 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 с вычеркнутой первой строкой и вторым столбцом.

Таблица 5

Таблица 7

Дополнительно в уменьшенной матрице поставлен запрет в клетке (2,1), т.к. выбрано ребро (1,2) и замыкать преждевременно тур ребром (2,1) нельзя. Уменьшенную матрицу можно привести на 1 по первому столбцу, так что каждый тур, ей отвечающий, стоит не меньше 35. Результат наших ветвлений и получения оценок показан на рис. 6.

Кружки представляют классы: верхний кружок - класс всех туров; нижний левый - класс всех туров, включающих ребро (1,2); нижний правый - класс всех туров, не включающих ребро (1,2). Числа над кружками - оценки снизу.

Продолжим ветвление в положительную сторону: влево - вниз. Для этого оценим нули в уменьшенной матрице C на табл. 7. Максимальная оценка в клетке (3,1) равна 3. Таким образом, оценка для правой нижней вершины на рис. 7 есть 35+3=38. Для оценки левой нижней вершины на рис. 7 нужно вычеркнуть из матрицы C еще строку 3 и столбец 1, получив матрицу C[(1,2), (3,1)] на табл. 8. В эту матрицу нужно поставить запрет в клетку (2,3), так как уже построен фрагмент тура из ребер (1,2) и (3,1), т.е. , и нужно запретить преждевременное замыкание (2,3). Эта матрица приводится по столбцу на 1 (табл. 9), таким образом, каждый тур соответствующего класса (т.е. тур, содержащий ребра (1,2) и (3,1)) стоит 36 и более.

Таблица 9

Таблица 11

Оцениваем теперь нули в приведенной матрице C[(1,2), (3,1)] нуль с максимальной оценкой 3 находится в клетке (6,5). Отрицательный вариант имеет оценку 38+3=41. Для получения оценки положительного варианта убираем строчку 6 и столбец 5, ставим запрет в клетку (5,6), см. табл. 10. Эта матрица неприводима. Следовательно, оценка положительного варианта не увеличивается (рис. 8).

Оценивая нули в матрице на табл. 10, получаем ветвление по выбору ребра (2,6), отрицательный вариант получает оценку 36+3=39, а для получения оценки положительного варианта вычеркиваем вторую строку и шестой столбец, получая матрицу на табл. 11.

В матрицу надо добавить запрет в клетку (5,3), ибо уже построен фрагмент тура и надо запретить преждевременный возврат (5,3). Теперь, когда осталась матрица 2х2 с запретами по диагонали, достраиваем тур ребрами (4,3) и (5,4). Мы не зря ветвились, по положительным вариантам. Сейчас получен тур: 1>2>6>5>4>3>1 стоимостью в 36. При достижении низа по дереву перебора класс туров сузился до одного тура, а оценка снизу превратилась в точную стоимость.

Итак, все классы, имеющие оценку 36 и выше, лучшего тура не содержат. Поэтому соответствующие вершины вычеркиваются. Вычеркиваются также вершины, оба потомка которой вычеркнуты. Мы колоссально сократили полный перебор. Осталось проверить, не содержит ли лучшего тура класс, соответствующий матрице С , т.е. приведенной матрице С с запретом в клетке 1,2, приведенной на 1 по столбцу (что дало оценку 34+1=35). Оценка нулей дает 3 для нуля в клетке (1,3), так что оценка отрицательного варианта 35+3 превосходит стоимость уже полученного тура 36 и отрицательный вариант отсекается.

Для получения оценки положительного варианта исключаем из матрицы первую строку и третий столбец, ставим запрет (3,1) и получаем матрицу. Эта матрица приводится по четвертой строке на 1, оценка класса достигает 36 и кружок зачеркивается. Поскольку у вершины «все» убиты оба потомка, она убивается тоже. Вершин не осталось, перебор окончен. Мы получили тот же минимальный тур, который показан подчеркиванием на табл. 2.

Удовлетворительных теоретических оценок быстродействия алгоритма Литтла и родственных алгоритмов нет, но практика показывает, что на современных ЭВМ они часто позволяют решить ЗК с n = 100. Это огромный прогресс по сравнению с полным перебором. Кроме того, алгоритмы типа ветвей и границ являются, если нет возможности доводить их до конца, эффективными эвристическими процедурами.