КОММИВОЯЖЁРА ЗАДАЧА
задача
о бродячем торговце, одна из известных задач конечной математики; в
простейшем случае формулируется следующим образом: даны п городов
и известны расстояния между каждыми двумя городами; коммивояжёр, выходящий
из к.-н. города, должен посетить п-1 других городов и вернуться
в исходный. В каком порядке ему нужно посещать города (по одному разу каждый),
чтобы общее пройденное расстояние было минимальным? К такого типа задачам,
связанным с объездом ряда пунктов и возвращением в исходную точку, относятся:
задачи доставки продуктов питания в магазины, подвода электроэнергии к
потребителям, построения кольцевой линии электропередач, различные задачи,
возникающие при автоматизации монтажа схем, и т. д. Такова, напр., задача
отыскания оптимальной программы работы автоматич. фрезерного станка для
просверливания отверстий в заданных точках панели радиоприёмника, т. е.
нахождения такого порядка прохождения этих точек, при к-ром длина маршрута
головки сверла была бы минимальной. Здесь начало маршрута не обязательно
должно совпадать с его концом, но математически такая постановка сводится
к приведённой выше простейшей К. з. Методы решения К. з., по существу,
сводятся к организации полного перебора вариантов; никакого эффективного
алгоритма не известно.
Лит.: М у д р о в В. И., Задача
о ком мивояжёре, М., 1969; Гольштейн Е.Г., Юдин Д. Б., Новые направления
в линейном программировании, М., 1966. В. Я. Козырев.
А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я