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

ЗАДАЧА О КОММИВОЯЖЕРЕ, О БРОДЯЧЕМ ТОРГОВЦЕ [travelling salesman problem] — вид задачи математического программирования; состоит в отыскании наилучшего маршрута для коммивояжера (бродячего торговца), который должен объехать все порученные ему города и вернуться назад за кратчайший срок или с наименьшими затратами на проезд. В обобщенной форме З. о к. формулируется как определение на сети такого пути, связывающего два или более узла, который минимизирует (или максимизирует) некоторый критерий оптимальности, представляющий собой функцию (как правило, сумму) известных характеристик ребер этой сети. На допустимые маршруты могут быть наложены ограничения (напр., запрет возвращения к уже пройденному узлу). З. о к. — одна из типичных задач, решаемых методом динамического программирования. О сложности ее говорит такой факт: если рассматриваются 4 города (точки), то число возможных маршрутов равно 6, а уже при 11 городах существует более 3,5 млн допустимых маршрутов. В общем случае, когда число городов n, количество маршрутов равно (n – 1)!, т. е. 1 × 2 × ... (n – 1). Задача, следовательно, заключается в поиске сокращенных способов расчета, позволяющих отказаться от сплошного перебора возможных маршрутов. Такие способы есть. Они основаны на использовании сетевых и матричных моделей. Алгоритмы, позволяющие решать на компьютерах З. о к., используются не только для выбора оптимальных маршрутов автотранспорта при кольцевой доставке товаров (напр., в торговую сеть), но и при решении таких задач, которые на первый взгляд никакого отношения к З. о к. не имеют (напр., в планировании производства на конвейерах, выпускающих машины различных моделей). С помощью таких алгоритмов рассчитывают оптимальные партии, позволяющие выпускать заданный объем продукции с минимумом затрат на переналадку конвейера.