Условие задачи
Задача коммивояжера.
Имеется 5 городов, выезжая из исходного города А1, коммивояжер должен побывать во всех городах по 1 разу и вернуться в город А1. Задача заключается в определении последовательности объезда городов, при которой коммивояжеру требуется минимизировать некоторый критерий эффективности: стоимость проезда, время пути, суммарное расстояние и т.д.
Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого (в матрице как бы вычеркивается диагональ). Целью решения является нахождения маршрута,удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат.
Ответ
В последнем столбце таблицы записаны минимальные значения по строкам. Вычитая эти числа из соответствующих строк, получим следующую таблицу:
Вычитая число 2 из столбца А2, мы получаем новую таблицу, которая называется приведенной:
