[M.A.D.M.A.N.]

Второй тип задачи выбора маршрута называется задачей коммивояжера. Такое название сложилось исторически и связано с поиском оптимального маршрута передвижения представителя торговой фирмы - коммивояжера. Последний, выйдя из своего города, должен обойти все города, входящие в сферу обслуживания фирмы, и вернуться обратно. При этом каждый город посещается один раз. Известны показатели переходов между всеми парами городов и требуется найти маршрут, обеспечивающий минимальные затраты времени или минимальный расход горючего, или минимальную стоимость проезда. Если показатели переходов зависят от направления движения, задача является асимметричной, иначе - симметричной. Эта задача отличается замкнутостью искомого маршрута и необходимостью прохождения всех пунктов. В теории графов такой маршрут называют гамильтоновым циклом.

Первоначально задача коммивояжера рассматривалась как математическая головоломка, но в последние десятилетия обнаружили, что к ней сводится ряд важных практических проблем. Например, если на одном оборудовании каждый месяц нужно производить фиксированную номенклатуру изделий, а затраты на переналадку зависят от предшествующего и последующего видов изделий, то определение последовательности запуска изделий в производство, обеспечивающей минимальные затраты на переналадку в течение месяца, представляет собой типичную задачу коммивояжера. Другой пример: составляется программа для станка с ЧПУ на сверление нескольких десятков отверстий в плате и требуется определить порядок, в котором будет производиться сверление, так, чтобы общее время операции было минимальным. Совершенно очевидно, что это тоже задача коммивояжера. В чем трудности решения таких задач, если число возможных вариантов всегда конечно? При трех городах имеется два варианта решения, при четырех - уже шесть, а при 11- более 3,6 млн. В общем случае задача коммивояжера с n городами (пунктами) имеет (-1)! замкнутых маршрутов, проходящих через все пункты. Таким образом, в реальных задачах число возможных вариантов исчисляется астрономическими величинами и в этом заключается основная проблема решения задачи.

Рассматриваемая задача может быть обобщена на коммивояжеров. В базовом городе находится коммивояжеров, обслуживающих всех клиентов фирмы (клиент-город). Необходимо составить замкнутых маршрутов, охватывающих всех клиентов по одному разу и имеющих наилучший суммарный показатель, например, минимальную суммарную длину. Увеличение числа коммивояжеров повышает сложность задачи.

Мы чето как-то быстро их решали.