ЗАДАЧА О КОММИВОЯЖЕРЕ (traveling salesman problem)

ЗАДАЧА О КОММИВОЯЖЕРЕ (traveling salesman problem) — вид задачи программирования матем., состоит в отыскании наилучшего маршрута для коммивояжера, который должен объехать все порученные ему города и вернуться назад за кратчайший срок или с наименьшими затратами на проезд. На языке графов теории 3. о к. формулируется как поиск такого пути, связывающего два или более узла, который минимизирует (или максимизирует) некоторый критерий оптимальности. Па допустимые пути могут быть наложены ограничения: напр., запрет возвращения к уже пройденному узлу. Алгоритмы, позволяющие решать на ЭВМ 3. о к., используются для выбора оптим. маршрутов автотранспорта, при кольцевой доставке продукции потребителям.