Задача коммивояжера. Имеется 5 городов, выезжая из исходного города А1, коммивояжер должен побывать во всех городах по 1 разу и вернуться в город А1. Задача заключается в определении последовательности объезда городов, при которой коммивояжеру требуется

Задача коммивояжера.

Имеется 5 городов, выезжая из исходного города А1, коммивояжер должен побывать во всех городах по 1 разу и вернуться в город А1. Задача заключается в определении последовательности объезда городов, при которой коммивояжеру требуется минимизировать некоторый критерий эффективности: стоимость проезда, время пути, суммарное расстояние и т.д.

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