Коммивояжёр (фр. commis voyageur) — разъездной посредник, который, перемещаясь по рынку, играет роль простого посредника или действует по поручению своего клиента (продавца); разъездной торговый агент какой-либо фирмы, предлагающий покупателям товары по образцам и каталогам.
Коммивояжёр выступает посредником между продавцом товара и покупателем. Действует, как правило, по поручению фирмы. Занимается сбытом товара за определённое вознаграждение, которое зависит от количества или суммы проданного товара, разъезжая по указанным адресам (в том числе и иногородним, иногда зарубежным).
Коммивояжёр вправе сам получать деньги за товары и устанавливать сроки платежей.
Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), метрическая задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.
Оптимизационная постановка задачи относится к классу очень NP-трудных задач, впрочем как и большинство её частных случаев. Версия «decision problem» (то есть такая, в которой ставится вопрос существует ли маршрут не длиннее, чем заданное значение) относится к классу NP-полных задач. Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.
Непременным условием и единственным смыслом задачи коммивояжёра является поиск самого выгодного пути. Для этого необходимо найти и описать все возможные пути при любом из вариантов способов поиска решения. Если мы не просчитали все пути в выбранном варианте решения, то мы не можем утверждать, что найденное решение самое выгодное. Что такое проверка решения? — это поиск ошибки в процессе решения или сверка полученного результата с заведомо правильным. Второй вариант временно отбрасываем, так как нет практического смысла в решении задачи, если уже есть решение (в свою очередь, использование ранее выполненного верного решения для части имеющейся задачи — способ уменьшить решение). В рамках данной работы не ставилось целью сравнение различных методов и способов решения, поэтому принимаем, что проверяющий также считает выбранный способ решения оптимальным и проверяет его на правильность. Что нужно сделать проверяющему? — повторить работу, проделанную при решении, в полном объёме для поиска ошибки на каждом этапе решения. Если будет найдена ошибка, то проверяющему будет необходимо продолжить процесс решения для поиска более выгодного маршрута. Таким образом, мы получаем, что проверка решения задачи коммивояжёра равна или больше самого решения.
Источники: