Задача коммивояжера: Коммивояжер должен посетить пять городов, заезжая в каждый город по одному разу. Расстояние между городами следующие: между первым городом и вторым – 12 км, между первым и третьим – 25 км, между первым и четвертым – 16 км, между первым и пятым – 31 км, между вторым и третьим – 28 км, между вторым и четвертым – 35 км, между вторым и пятым – 22 км, между третьим и четвертым – 36 км, между третьим и пятым – 20 км, между четвертым и пятым – 19 км. Его маршрут должен минимизировать суммарную длину пройденного пути.
Решение. Сначала получим приведенный вид данной матрицы. Для этого пронумеруем строки и столбцы. В каждом столбце определим минимальный элемент и запишем его в нижней строке:
.
Из каждого элемента столбца вычитаем соответствующий минимальный элемент. Получаем матрицу 
:
.
Матрица 
оказалась не приведенной, поэтому определяем минимальный элемент в каждой строке и вычитаем его из всех элементов соответствующей строки. В результате получаем приведенную матрицу 
:
.
Вычисляем константу приведения 
:
.
Находим степени каждого нуля – сумму минимальных элементов строки и столбца, в которых стоит нуль (без учета самого нуля). К каждому нулю приписываем вверху его степень. Максимальной степенью является число 12. Нули с максимальной степенью определяют дуги, которые вероятнее всего войдут в гамильтонов цикл. В нашем случае наиболее вероятной дугой гамильтонова цикла является l (3; 5).
Выбираем дугу l (3; 5).
В связи с этим рассматриваем две матрицы: 
и 
. В матрице убираем третью строку и пятый столбец, элемент 
заменяем 
. В матрице элемент 
заменяем . Получаем:
, 
.
Обе матрицы не являются приведенными. Для приведения матриц определяем минимальные элементы строк и столбцов.
Сначала работаем с матрицей . Определяем минимальные элементы строк. А потом эти элементы вычитаем из каждого элемента соответствующих строк.
Þ 
.
Теперь определяем минимальные элементы каждого столбца. А потом эти элементы вычитаем из каждого элемента соответствующего столбца.
Þ 
.
Аналогично преобразовываем матрицу .
Þ 
.
Таким образом, получаем две приведенные матрицы:
и 
.
Вычисляем константы приведения:
, 
,
где 
и 
– суммы минимальных элементов строк и столбцов матриц и .
, но далее рассматриваем матрицу . Определяем степени нулей этой матрицы:
.
Максимальная степень – число 7. Наиболее вероятными дугами гамильтонова цикла являются дуги l (1; 2), l (4; 1) и l (5;4). Выбираем, например, дугу l (1; 2).
В связи с этим рассматриваем две матрицы: 
и 
. В матрице убираем первую строку и второй столбец, элемент 
заменяем , получаем матрицу . В матрице элемент 
заменяем . Имеем:
, 
.
Обе матрицы не являются приведенными. Преобразуем их по той же схеме, как это делали выше.
Þ 
Þ 
.
Таким образом, получаем две приведенные матрицы и .
Вычисляем константы приведения:
, 
.
Так как 
, то далее рассматриваем матрицу . Определяем степени каждого нуля.
Максимальная степень – число 32. Наиболее вероятной дугой гамильтонова цикла является дуга l (5; 4).
В связи с этим рассматриваем две матрицы: 
и 
. В матрице убираем строку под номером 5 и столбец под номером 4, получаем матрицу . В матрице элемент 
заменяем . Имеем:
, 
.
Матрица не является приведенной. Преобразуем ее по той же схеме как делали выше.
Þ 
.
, 
.
Так как 
, то далее рассматриваем матрицу . Последние две дуги гамильтонова цикла определяем из матрицы : l (2; 3) и l (4; 1).
Таким образом, получаем решение, которое состоит из следующих дуг: (3; 5), (1;2), (5; 4), (2; 3), (4; 1). Гамильтонов цикл имеет вид 1®2®3®5®4®1, длина цикла равна 95 км.
Сравним константу приведения 
с константами приведения 
альтернативных вариантов (
):
: 
;
: 
;
: 
.
Так как , то возвращаемся к приведенной матрице , и от нее начинаем строить гамильтонов цикл.
Определяем степени нулей этой матрицы:
.
Максимальная степень – число 8. Наиболее вероятной дугой гамильтонова цикла является дуга l (5; 3).
В связи с этим рассматриваем две матрицы: 
и 
. В матрице убираем пятую строку и третий столбец, элемент 
уже заменен . В матрице элемент заменяем . Получаем:
, 
.
Матрица - приведенная, а матрица не является приведенной. Сделаем ее приведенной, как это делали выше.
Þ 
.
Вычисляем константы приведения:
, 
,
где 
и 
– суммы минимальных элементов строк и столбцов матриц и .
Так как 
, но далее рассматриваем матрицу . Определяем степени нулей этой матрицы:
.
Максимальная степень – число 7. Наиболее вероятными дугами гамильтонова цикла являются дуги l (1; 4), и l (4; 5). Выбираем, например, дугу l (4; 5).
В связи с этим рассматриваем две матрицы: 
и 
. В матрице убираем строку под номером 4 и столбец под номером 5, получаем матрицу . В матрице элемент 
заменяем . Имеем:
, 
.
Матрица - приведенная, а матрица не является приведенной. Сделаем ее приведенной, как это делали выше.
Þ 
.
Вычисляем константы приведения:
, 
.
Так как 
, то далее рассматриваем матрицу . Определяем степени каждого нуля.
.
Максимальная степень – число 19. Наиболее вероятной дугой гамильтонова цикла является дуга l (2; 1).
В связи с этим рассматриваем две матрицы: 
и 
. В матрице убираем строку под номером 2 и столбец под номером 1, элемент заменяем и получаем матрицу . В матрице элемент заменяем . Имеем:
, 
.
Обе матрицы не являются приведенными. Преобразуем их по той же схеме, как это делали выше.
Þ 
,
Þ 
.
, 
.
Так как 
, то далее рассматриваем матрицу . Последние две дуги гамильтонова цикла определяем из матрицы : l (1; 4) и l (3; 2).
Таким образом, получаем решение, которое состоит из следующих дуг: (5; 3), (4;5), (2; 1), (1; 4), (3; 2). Гамильтонов цикл имеет вид 1®4®5®3®2®1, длина цикла тоже равна 95 км.
Сравним константу приведения 
с константами приведения 
альтернативных вариантов ():
: 
;
: ;
: 
.
Это значит, что получили оптимальное решение.
Весь процесс отыскания оптимального плана можно изобразить в виде дерева ветвления:
Полученные гамильтоновы циклы 1®2®3®5®4®1 или 1®4®5®3®2®1 можно изобразить в виде орграфа.
Это означает следующее: коммивояжер сначала посещает город 1, потом – город 2, затем – город 3, после – город 5, и, наконец, город 4, а потом возвращается в город 1. При этом длина всего пути составит 95 км. Второе решение говорит о том, что коммивояжер может ехать в обратную сторону.
,
Практическое задание
3.1. Решить задачу: Коммивояжер должен посетить пять городов, заезжая в каждый город по одному разу. Расстояние между городами следующие: между первым городом и вторым – N км, между первым и третьим – N+5 км, между первым и четвертым – 2N км, между первым и пятым – 45-N км, между вторым и третьим – N-1 км, между вторым и четвертым – 5 км, между вторым и пятым – 12 км, между третьим и четвертым – 3N-15 км, между третьим и пятым – 20-2N км, между четвертым и пятым – 19 км. Его маршрут должен минимизировать суммарную длину пройденного пути. Укажите возможные маршруты и длину пути. Изобразите процесс отыскания оптимального плана в виде дерева ветвления.
3.2. Разработайте блок-схему алгоритма Литтла.
