Задача о коммивояжере (англ. '''travelling - salesman problem''') - это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из <tex> N </tex> точек на плоскости.
== Формулировка задачи ==
Коммивояжер должен посетить <tex> N </tex> городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?
== Представление ==
Чтобы использовать математические процессы для решения, реальная ситуация должна отображаться сначала простой моделью. Задачу коммивояжера можно смоделировать с помощью графа. При этом вершины можно считать городами, в то время как каждая дуга <tex>(i, j) </tex> описывает связь между этими 2 вершинами <tex>i</tex> и <tex>j</tex>. Каждая дуга имеет свой вес <tex> с(i, j) </tex>. Поездка - это цикл в этом графе, который проходит через каждую вершину ровно один раз. Целью является найти более короткую поездку.
== Варианты решения ==
Задача о коммивояжере относится к классу NP-полных задач.
Рассмотрим два варианта решения.
==== Перебор перестановок ====
==== Решение Можно решить задачу перебором ==== Можно предположить, что для решения задачи необходимо всевозможных перестановок. Для этого нужно сгенерировать все <tex> N! </tex> всевозможных перестановок вершин полного графа, подсчитать для перестановки длину маршрута и выбрать минимальный из них. Но тогда задача оказывается неосуществимой даже для достаточно небольших <tex>N</tex>. Так же известно, что задача о коммивояжере относится к NP-полным задачам.
==== Динамическое программирование по подмножествам ====
