1.6. Алгоритмы.
Существует много методов и алгоритмов для решения задачи коммивояжера:
Метод «ветвей и границ» или метод Литтла
Метод полного перебора.
Генетический алгоритм.
Алгоритм Дейкстры
«Жадные» алгоритмы
Метод «ближайшего соседа».
Метод «ближайшего соседа с двух сторон».
Метод дешевого включения
«Деревянный» алгоритм
Эвристический метод
Алгоритм Эйлера и Кристофидеса
Метод локального поиска
Рассмотрим только три наиболее распространенные и эффективные.
1.6.1 Прямой алгоритм
Идея прямого алгоритма состоит в том, что начиная со стартовой вершины из всех направлений кандидатов выбирается то направление, которое дает наименьшее приращение к сумме пройденного пути. Таким образом, глубина просмотра путей (ветвей) направлений движения составляет один шаг. На первых шагах алгоритм показывает хорошие результаты, а на последних – плохие, так как отсутствуют варианты выбора направления движения и идти приходится по оставшемуся свободному пути. Отсутствие анализа на несколько шагов вперед (на два, три, четыре шага и т.д.) приводит к нахождению далеко не оптимального решения.
Рассмотрим прямой алгоритм на примере:
Задача: Определить
длину (Д) кратчайшего маршрута (К)
коммивояжера. Расстояния (
)
между шестью городами представлены в
таблице 1.1
Табл. 1.1
Город |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
|
6 |
4 |
12 |
14 |
22 |
2 |
6 |
|
3 |
8 |
7 |
20 |
3 |
4 |
3 |
|
10 |
11 |
18 |
4 |
12 |
8 |
10 |
|
9 |
16 |
5 |
44 |
7 |
11 |
9 |
|
10 |
6 |
22 |
20 |
18 |
16 |
10 |
|
;
К=1;
;
К=1
3;
;
К=1 3 2;
;
;
:
;
:
;
;
Ответ: длина маршрута 61,
порядок объезда городов:
.
Условия примера представляют собой симметричную задачу (матрица смежности относительно главной диагонали). На практике встречаются и несимметричные задачи. Например, проезд на автобусе в прямом и обратном направлении составляют разную сумму или две дороги с односторонним движением и различной протяженностью соединяют два города и т.д. Также возможны и смешанные задачи, в графах которых отсутствуют некоторые ребра (два города не имеют прямой дороги, т.е. проезд осуществляется через третий город).
1.6.2.Алгоритм Литтла (метод ветвей и границ)
Так же как и в целочисленном программировании, при использовании алгоритма Литтла необходимо определить верхнюю и нижнюю оценки для разделения множества решений на два класса. Различают две группы задач, решаемых этим алгоритмом: задачи на минимум(определяют нижнюю оценку или границу) и задачи на максимум (определяют верхнюю границу или оценку).
Идея алгоритма такова: определяют нижнюю оценку (для задач на минимум) и разделяют исходную матрицу на две примерно равные части. Затем уменьшают размер матрицы и определяют «плату» за уменьшение размера матрицы. Размер платы может быть или положительный или нулевой, т.е. увеличивать или не изменять размеры нижней оценки. Размер матрицы уменьшается до 2*2. Затем выполняют движение в обратном порядке и получают оптимальный по стоимости маршрут.
Рассмотрим работу алгоритма Литтла на примере.
Выполним «зануление» матрицы . Результаты представлены в таблицах 1.2 – 1.4
Таблица1.2 Исходная
Город |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
|
6 |
4 |
12 |
14 |
22 |
2 |
6 |
|
3 |
8 |
7 |
20 |
3 |
4 |
3 |
|
10 |
11 |
18 |
4 |
12 |
8 |
10 |
|
9 |
16 |
5 |
14 |
7 |
11 |
9 |
|
10 |
6 |
22 |
20 |
18 |
16 |
10 |
|
Таблица1.3 Зануление по строкам
№ |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
|
2 |
0 |
8 |
10 |
18 |
2 |
3 |
|
0 |
5 |
4 |
17 |
3 |
1 |
0 |
|
7 |
8 |
15 |
4 |
4 |
0 |
2 |
|
1 |
8 |
5 |
7 |
0 |
4 |
2 |
|
3 |
6 |
12 |
10 |
8 |
6 |
0 |
|
Таблица1.4 Зануление по столбцам
№ |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
|
2 |
0 |
6 |
10 |
15 |
2 |
2 |
|
0 |
3 |
4 |
14 |
3 |
0 |
0 |
|
5 |
8 |
12 |
4 |
4 |
0 |
2 |
|
1 |
5 |
5 |
6 |
0 |
4 |
0 |
|
0 |
6 |
11 |
10 |
8 |
4 |
0 |
|
После зануления матрицы ее элементы должны содержать или положительные, или нулевые значения. Сумма вычтенных значений по строкам равна 35 (4+3+3+8+7+10), по столбцам – 6 (1+0+0+2+0+3). Общая сумма всех вычитаний – 41. Это и есть нижняя оценка.
Из условия задачи ясно, что надо побывать в каждом городе один раз. То есть замкнутый цикл (маршрут) должен содержать уникальные номера городов и переходы из одного города в другой должны выполняться по одному разу в каждой сроке и в каждом столбце. Также надо помнить, что стоимость маршрута не может быть меньше нижней оценки (общей суммы выполненных вычитаний).
Далее для каждой клетки матрицы, содержащей ноль, надо вычислить частную оценку клетки или просто оценку клетки.
Оценка клетки определяется как сумма минимальных элементов соответствующей строки и столбца.
Клетка 1-3 содержит значение ноль. Оценка этой клетки будет равна сумме минимального элемента по первой сроке и минимального элемента по третьему столбцу 2+0=2. Для клетки 2-3 оценка составит 2+0=2. Для клетки 3-2 оценка будет 0+0=0.
Клетка 3-1: 2+0=2
Клетка 4-2: 1+0=1
Клетка 5-2: 0+0=0
Клетка 5-4: 3+0=3
Клетка 5-6: 0+5=5
Клетка 6-5: 4+1=5
Начиная с этого момента приступаем к построению дерева ветвления алгоритма. Максимальная оценка 5 принадлежит двум клеткам 5-6 и 6-5. Поэтому за нулевое ребро принимается или ребро 5-6, или ребро 6-5. Возьмем ребро 5-6. Все маршруты разобьем на содержащее ребро 5-6 и не содержащее это ребро. Обе группы маршрутов (содержащие и не содержащие ребро 5-6) будут иметь стоимость не менее нижней оценки (более может быть).
Из дальнейшего рассмотрения исключаем пятую строку и шестой столбец (табл.1.5)
Таблица1.5 Снижение размера матрицы
№ |
1 |
2 |
3 |
4 |
5 |
1 |
|
2 |
|
6 |
10 |
2 |
2 |
|
|
3 |
4 |
3 |
|
|
|
5 |
8 |
4 |
3 |
|
2 |
|
1 |
6 |
11 |
10 |
8 |
4 |
|
Этим действием снижаем размер матрицы. Ребро 5-6 ( на таблицах представлены в виде клеток) помечено как запрещенное (голубым цветом) для рассмотрения. К уменьшенной матрице применяем процедуру зануления (табл.1.6)
Таблица1.6 Зануление матрицы
№ |
1 |
2 |
3 |
4 |
5 |
1 |
|
2 |
|
6 |
9 |
2 |
2 |
|
|
3 |
3 |
3 |
|
|
|
5 |
4 |
4 |
3 |
|
2 |
|
0 |
6 |
7 |
6 |
4 |
0 |
|
Из последней строки вычтем 4, а из последнего столбца – 1. Заново определим оценки нулевых клеток (табл.1.7).
Таблица1.7 Расчет оценок клеток
№ |
1 |
2 |
3 |
4 |
5 |
1 |
|
2 |
|
6 |
9 |
2 |
2 |
|
|
3 |
3 |
3 |
|
|
|
5 |
7 |
4 |
3 |
|
2 |
|
|
6 |
7 |
6 |
4 |
|
|
Клетка 6-4 имеет наибольшую оценку 7. За «нулевое ребро» возьмем 6-4. Далее процедура снижения размера матрицы повторяется. Результат преобразований показан в приведенных ниже таблицах.
Таблицы 1.8 – 1.10 Продолжение ветвления алгоритма
Второй шаг
а б в
№ |
1 |
2 |
3 |
5 |
1 |
|
2 |
|
9 |
2 |
2 |
|
|
3 |
3 |
|
|
|
7 |
4 |
3 |
|
2 |
|
№ |
1 |
2 |
3 |
5 |
|||||||||
1 |
|
2 |
|
6 |
|||||||||
2 |
2 |
|
|
0 |
|||||||||
3 |
|
|
|
4 |
|||||||||
4 |
3 |
|
2 |
|
|||||||||
|
|
|
|
|
|
||||||||
|
|
|
|
|
|||||||||
|
|
|
|
|
|||||||||
|
|
|
|
|
|||||||||
|
|
|
|
|
|||||||||
№ |
1 |
2 |
3 |
5 |
1 |
|
2 |
|
6 |
2 |
2 |
|
|
|
3 |
|
|
|
4 |
4 |
3 |
|
2 |
|
Третий шаг
а б в
№ |
1 |
2 |
3 |
|
№ |
1 |
2 |
3 |
|
№ |
1 |
2 |
3 |
|
№ |
1 |
2 |
3 |
1 |
|
2 |
|
1 |
|
2 |
|
1 |
|
2 |
|
1 |
|
2 |
|
|||
3 |
|
|
|
3 |
3 |
|
2 |
3 |
1 |
|
0 |
3 |
1 |
|
|
|||
4 |
3 |
|
2 |
4 |
|
|
|
4 |
|
|
|
4 |
|
|
|
Четвертый шаг
а б, в
№ |
1 |
3 |
|
№ |
1 |
3 |
1 |
|
|
1 |
|
|
|
4 |
1 |
|
4 |
0 |
|
Проанализируем выполненные работы и построим дерево алгоритма. В результате расчета «зануления» исходной матрицы была получена нижняя оценка – 41. Таким образом, стоимость любого допустимого маршрута будет не менее 41. После вычисления оценок нулевых клеток, была выбрана клетка 5-6 с максимальной оценкой 5. Соответственно, ребро, соединяющее города 5 и 6, было объявлено нулевым, и все возможные маршруты были разделены на две группы: содержащие ребро 5-6 и не содержащие этого ребра. Новая нижняя оценка для маршрутов, не содержащих ребра 5-6, должна быть увеличена на оценку клетки 5-6 и составит 41+5=46.
На первом шаге нулевое ребро было помечено серым цветом и изъято из дальнейшего рассмотрения. Далее рассматривалась только левая ветвь (рис. 12) дерева ветвления алгоритма. Общая сумма «зануления» по строкам и столбцам равна 5. Нижняя оценка для левой группы маршрутов (включающих ребро 5-6) составит 41+5=46.
На втором шаге была выбрана клетка 6-4 с оценкой 7. Новая нижняя оценка для маршрутов группы, не содержащих ребро 4-5, будет 53 и ветвление будет выполнено по ребру 6-4. Общая сумма «зануления» (по строкам и столбцам) составит 3. Нижняя оценка для левой группы маршрутов (содержащих ребро 4-5) будет 46+3=49.
На третьем шаге будет удалено ребро 2-5. Оценка клетки 2-5 составляет 4. Следовательно, нижняя оценка правой группы маршрутов будет 49+4=53. Общая сумма «зануления» - 2. Нижняя оценка левой группы маршрутов равна 49+2=51.
На четвертом шаге выбрана клетка 3-2 с оценкой 2. Нижняя оценка правой группы маршрутов равна 51+2=53. Общая сумма «зануления» - 1. Нижняя оценка левой группы маршрутов равна 51+1=52. В результате анализа было составлено дерево ветвления алгоритма (рис. 1.10)
Рис.1.10. Дерево ветвления алгоритма
Построение оптимального маршрута выполним, используя рис. 12 и таблиц, приведенных выше. На последнем (четвертом шаге) остались два свободных (не запрещенных) ребра 1-3 и 4-1. Оба ребра включаем в маршрут и добавляем ребра из левой ветви рис. 12.
Оптимальный маршрут будет состоять из ребер: 1-3; 4-1; 3-2; 2-5; 6-4; и 5-6. После упорядочения получим:1-3-2-5-6-4-1.
Ответ: Длина оптимального маршрута не менее 52, порядок объезда городов:1-3-2-5-6-4-1.
Из исходной матрицы подставим значения ребер и определим стоимость маршрута: 4+3+7+10+16+12=52.
Для того, чтобы
убедиться, действительно ли найден
оптимальный маршрут, надо проанализировать
«правые» группы маршрутов. Все правые
группы, кроме первой, имеют нижнюю оценку
более 52. Следовательно, эти группы не
могут содержать лучшего решения. Остается
проверить первую правую группу, нижняя
оценка которой составляет 46. Маршруты
этой группы не содержат ребра 5-6. Анализ
ребра 5-6 выполнялся в начале работы
алгоритма. Поэтому из исходной матрицы
надо исключить ребро 5-6. Исключение
ребра выполним следующим образом: ребрам
5-6 и 6-5 поставим значение
.
Процесс доказательства минимальности
алгоритма представлен на таблице 1.11,
1.12 и рисунке 1.11. Так как исходная задача
симметричная, то исключались два ребра
5-6 и 6-5. Если задача несимметричная, то
исключается одно ребро, и доказательство
правильности решения увеличивается на
один шаг.
Таблица 1.11. Исключение ребра 5-6: а- исходная матрица;
б – исключение ребер5-6 и 6-5;
в – расчет оценок.
а б в
№ |
1 |
2 |
3 |
4 |
5 |
6 |
|
№ |
1 |
2 |
3 |
4 |
5 |
6 |
|
№ |
1 |
2 |
3 |
4 |
5 |
|
|
|
|
|
|
1 |
|
6 |
4 |
12 |
14 |
22 |
1 |
|
2 |
0 |
8 |
10 |
18 |
1 |
|
2 |
|
8 |
9 |
|
|
|
|
|
|||
2 |
6 |
|
3 |
8 |
7 |
20 |
2 |
3 |
|
0 |
5 |
4 |
17 |
2 |
2 |
|
|
5 |
3 |
|
|
|
|
|
|||
3 |
4 |
3 |
|
10 |
11 |
18 |
3 |
1 |
0 |
|
7 |
8 |
15 |
3 |
|
|
|
7 |
7 |
|
|
|
|
|
|||
4 |
12 |
8 |
10 |
|
9 |
16 |
4 |
4 |
0 |
2 |
|
1 |
8 |
4 |
3 |
|
2 |
|
|
|
|
|
|
|
|||
5 |
14 |
7 |
11 |
9 |
|
10 |
5 |
7 |
0 |
4 |
2 |
|
|
5 |
6 |
|
4 |
2 |
|
|
|
|
|
|
|||
6 |
22 |
20 |
18 |
16 |
10 |
|
6 |
6 |
4 |
2 |
0 |
|
|
6 |
5 |
4 |
2 |
|
|
|
|
|
|
|
Таблица 1.12. Первый шаг доказательства оптимальности:
а – исключение ребра 4-6;
б – перестановка строк;
в – «зануление»матрицы
а б в
№ |
1 |
2 |
3 |
4 |
5 |
|
№ |
1 |
2 |
3 |
4 |
5 |
|
№ |
1 |
2 |
3 |
4 |
5 |
1 |
|
2 |
|
8 |
9 |
1 |
|
2 |
|
8 |
9 |
1 |
|
2 |
|
6 |
6 |
||
2 |
2 |
|
|
5 |
3 |
2 |
2 |
|
|
5 |
3 |
2 |
2 |
|
|
3 |
0 |
||
3 |
|
|
|
7 |
7 |
3 |
|
|
|
7 |
7 |
3 |
|
|
|
5 |
4 |
||
4 |
6 |
|
4 |
2 |
|
4 |
5 |
4 |
2 |
|
|
4 |
3 |
2 |
0 |
|
|
||
6 |
5 |
4 |
2 |
|
|
6 |
6 |
|
4 |
2 |
|
6 |
6 |
|
4 |
0 |
|
Рис. 1.11. Дерево доказательства оптимальности алгоритма
Таким образом, в результате проведенного анализа установлено, что оба разветвления правой ветви «Без ребра 5 – 6» дают оценки 58. Строить последующие ветви не имеет смысла, так как все маршруты будут иметь большую стоимость по сравнению с левой ветвью алгоритма.