В произвольном порядке обойти все вершины графа по кратчайшему пути и вернуться в исходную вершину, причем каждая вершина проходится один раз.
Математическая модель задачи коммивояжера имеет вид:
где n – количество вершин замкнутого графа;
Cij– расстояние между городами ( затраты ресурса между работами) при наложенных ограничениях:
Cij ≥ 0 – расстояния (ресурсы) не отрицательны;
Cij = ∞ – запрет на петли внутри маршрута;
Задачу коммивояжера можно решить с помощью одного из алгоритмов:
1. Прямой алгоритм.
Идея прямого алгоритма состоит в том, что начиная со стартовой вершины из всех направлений кандидатов выбирается то направление которое даёт наименьшее приращение к сумме пройденного пути.
Определить длину (Q) кратчайшего маршрута (L) коммивояжера. Расстояние (Qij) между шестью городами представлены в таблице 1:
Алгоритм Литтла применяют для поиска решения задачи коммивояжера в виде гамильтонова контура. Данный алгоритм используется для поиска оптимального гамильтонова контура в графе, имеющем N вершин, причем каждая вершина i связана с любой другой вершиной j двунаправленной дугой. Каждой дуге приписан вес Сi,j, причем веса дуг строго положительны (Сi,j≥0). Веса дуг образуют матрицу стоимости. Все элементы по диагонали матрицы приравнивают к бесконечности (Сj,j=∞).
Алгоритм Литтла
1. В каждой строке матрицы стоимости найдем минимальный элемент и вычтем его из всех элементов строки. Сделаем это и для столбцов, не содержащих нуля. Получим матрицу стоимости, каждая строка и каждый столбец которой содержат хотя бы один нулевой элемент.
2. Для каждого нулевого элемента матрицы cij рассчитаем коэффициент Гi,j, который равен сумме наименьшего элемента i строки (исключая элемент Сi,j=0) и наименьшего элемента j столбца. Из всех коэффициентов Гi,j выберем такой, который является максимальным Гk,l=max{Гi,j}. В гамильтонов контур вносится соответствующая дуга (k,l).
3. Удаляем k-тую строку и столбец l, поменяем на бесконечность значение элемента Сl,k (поскольку дуга (k,l) включена в контур, то обратный путь из l в k недопустим).
4. Повторяем алгоритм шага 1, пока порядок матрицы не станет равным двум.
5. Затем в текущий ориентированный граф вносим две недостающие дуги, определяющиеся однозначно матрицей прядка 2. Получаем гамильтонов контур.
В ходе решения ведется постоянный подсчет текущего значения нижней границы. Нижняя граница равна сумме всех вычтенных элементов в строках и столбцах. Итоговое значение нижней границы должно совпасть с длиной результирующего контура.
Пример2. Имеется 6 пунктов, которые должен посетить коммивояжер по одному разу, минимизируя пройденный путь, и вернуться в исходный город. Расстояния между городами заданы матрицей (рисунок 1)
Запишем математическую модель задачи:
Требуется минимизировать
1. Осуществим вначале приведение по строкам, затем по столбцам, записав приводящие константы соответственно справа и снизу.
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную на рисунке 2..
То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.(рисунок 3)
Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.Г1,2=0, Г1,4=14, Г2,1=9, Г2,3=0, Г3,2=0, Г3,5=8, Г4,3=9, Г5,6=2, Г6,7=14, Г7,6=14. В результате сравнения мы получили 3 одинаковых максимальных Г=14. Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно. Рассмотрим вариант Г1,4=14
Удалим из матрицы стоимости строку 1 и столбец 4. (рисунок 4) Внесем в текущий ориентированный граф дугу (1,4)
В строке 4 и столбце 1 отсутствует элемент равный ∞. Присвоим элементу (4,1) значение бесконечности чтобы избежать преждевременного замыкания контура.
Текущая Нижняя граница=87
Нижняя граница равна сумме всех вычтенных элементов в строках и столбцах. Итоговое значение нижней границы должно совпасть с длиной результирующего контура.
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже. (рисунок 5)
То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце. (рисунок 6)
Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца. Г2,1=10, Г2,3=0, Г3,2=10, Г3,5=8, Г4,3=10, Г5,6=2, Г6,7=14, Г7,6=14,
В результате сравнения мы получили 2 одинаковых максимальных Г=14. Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно. Рассмотрим вариант Г6,7=14
Удалим из матрицы стоимости строку 6 и столбец 7. Внесем в текущий ориентированный граф дугу (6,7)
В строке 7 и столбце 6 отсутствует элемент равный ∞. Присвоим элементу (7,6) значение бесконечности чтобы избежать преждевременного замыкания контура.
Текущая Нижняя граница=87
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.
То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.
Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.Г2,1=10, Г2,3=0, Г3,2=10, Г3,5=0, Г4,3=10, Г5,6=10, Г7,5=10,
В результате сравнения мы получили 5 одинаковых максимальных Г=10. Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно. Рассмотрим вариант Г2,1=10
Удалим из матрицы стоимости строку 2 и столбец 1. Внесем в текущий ориентированный граф дугу (2,1)
В строке 4 и столбце 2 отсутствует элемент равный ∞. Присвоим элементу (4,2) значение бесконечности чтобы избежать преждевременного замыкания контура. Текущая Нижняя граница=101
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.
То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.
Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца. Г3,2=12, Г3,5=0, Г4,3=12, Г5,6=10, Г7,5=10,
В результате сравнения мы получили 2 одинаковых максимальных Г=12. Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно. Рассмотрим вариант Г3,2=12
Удалим из матрицы стоимости строку 3 и столбец 2. Внесем в текущий ориентированный граф дугу (3,2)
∞
∞
В строке 4 и столбце 3 отсутствует элемент равный ∞. Присвоим элементу (4,3) значение бесконечности чтобы избежать преждевременного замыкания контура. Текущая Нижняя граница=101
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.
∞
∞
∞
То же проделаем и со столбцами, не содержащими нуля. Получим матрицу, содержащую нули в каждой строке и каждом столбце.
∞
∞
∞
Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца. Г4,5=8, Г5,3=8, Г5,6=8, Г7,5=8,
В результате сравнения мы получили 4 одинаковых максимальных Г=8. Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно. Рассмотрим вариант Г4,5=8
Удалим из матрицы стоимости строку 4 и столбец 5. Внесем в текущий ориентированный граф дугу (4,5)
∞
В строке 5 и столбце 3 отсутствует элемент равный ∞. Присвоим элементу (5,3) значение бесконечности чтобы избежать преждевременного замыкания контура. Текущая Нижняя граница=113
После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтенные элементы матрицы к нижней границе), и добавляем к маршруту коммивояжера дуги которым соответствуют нулевые элементы. НГр=121 Маршрут коммивояжера включает в себя дуги:, (1, 4), (6, 7), (2, 1), (3, 2), (4, 5), (5, 6), (7, 3) ------------------------------------------------------------------------- Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г7,5. Удалим из матрицы стоимости строку 5 и столбец 7. Внесем в текущий ориентированный граф дугу (7,5)
∞
В строке 5 и столбце 6 отсутствует элемент равный ∞. Присвоим элементу (5,6) значение бесконечности чтобы избежать преждевременного замыкания контура. После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтенные элементы матрицы к нижней границе), и добавляем к маршруту коммивояжера дуги которым соответствуют нулевые элементы. НГр=121 Маршрут коммивояжера включает в себя дуги:, (1, 4), (6, 7), (2, 1), (3, 2), (7, 5), (4, 6), (5, 3) ------------------------------------------------------------------------- Вернемся к возникшему у нас ветвлению и рассмотрим случай при котором максимальное значение имеет Г5,6. Удалим из матрицы стоимости строку 6 и столбец 5. Внесем в текущий ориентированный граф дугу (5,6)
∞
В строке 7 и столбце 5 отсутствует элемент равный ∞. Присвоим элементу (7,5) значение бесконечности чтобы избежать преждевременного замыкания контура. После того, как ранг матрицы становится равным двум мы получаем нули в каждой ее строке и столбце (добавив как и ранее вычтенные элементы матрицы к нижней границе), и добавляем к маршруту коммивояжера дуги которым соответствуют нулевые элементы. НГр=121 Маршрут коммивояжера включает в себя дуги:, (1, 4), (6, 7), (2, 1), (3, 2), (5, 6), (4, 5), (7, 3)
Дуге (1, 4) соответствует путь (1, 4); дуге (6, 7) - путь(6, 7); дуге (2, 1) соответствует путь (2, 1); дуге (3, 2) - путь (3,2); дуге (5, 3) соответствует путь (5, 3); дуге (7, 5) - путь 7-6-5; дуге (4, 6) - путь 4-3-5-6. То есть оптимальный контур для нашего графа: 1-4-3-5-6-7-6-5-3-2-1 длиной 121 единицу.
Пример2. Имеется 6 пунктов, которые должен посетить коммивояжер по одному разу, минимизируя пройденный путь, и вернуться в исходный город. Расстояния между городами заданы матрицей (рисунок 1)
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную на рисунке 2..
Для каждого нулевого элемента рассчитаем значение Гij, равное сумме наименьшего элемента i строки (исключая элемент Сij=0) и наименьшего элемента j столбца.Г1,2=0, Г1,4=14, Г2,1=9, Г2,3=0, Г3,2=0, Г3,5=8, Г4,3=9, Г5,6=2, Г6,7=14, Г7,6=14. В результате сравнения мы получили 3 одинаковых максимальных Г=14. Это означает что алгоритм разветвляется и мы должны рассмотреть все получившиеся варианты поочередно. Рассмотрим вариант Г1,4=14
Текущая Нижняя граница=87
В строке 7 и столбце 6 отсутствует элемент равный ∞. Присвоим элементу (7,6) значение бесконечности чтобы избежать преждевременного замыкания контура.
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.
Найдем минимальные элементы в каждой строке и затем вычтем его из остальных элементов строки (минимальные элементы записаны напротив соответствующих строк). Получим матрицу представленную ниже.