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

Вид задачи программирования матем., состоит в отыскании наилучшего маршрута для коммивояжера, который должен объехать все порученные ему города и вернуться назад за кратчайший срок или с наименьшими затратами на проезд. На языке теории графов задача о коммивояжёре формулируется как поиск такого пути, связывающего два или более узла, который минимизирует (или максимизирует) некоторый критерий оптимальности. На допустимые пути могут быть наложены ограничения: например, запрет возвращения к уже пройденному узлу. Алгоритмы, позволяющие решать на ЭВМ задачу о коммивояжёре, используются для выбора оптимальных маршрутов автотранспорта, при кольцевой доставке продукции потребителям.