Изменения
Нет описания правки
== Представление: ==
Чтобы использовать математические процессы смогли использоваться для решения, реальная ситуация должна отображаться сначала простой моделью. Задачу коммивояжера можно смоделировать с помощью графа. При этом вершины принято можно считать городами, в то время как каждая дуга (i, j) описывает связь между этими городами между 2 вершинами i и j. Каждая дуга имеет свой вес с(i, j). Поездка (также цикл Гамильтона) - это цикл в этом графе, который проходит через каждую вершину ровно один раз. Целью является найти более короткую поездку.
Если же граф симметрический (т.е. для всех пар вершин (i, j) длины дуг в обоих направлениях одинаковы ), то каждая поездка в обоих направлениях имеет одну и ту же длину/стоимость. Симметрия делит пополам количество возможных поездок.
Можно предположить, что для решения задачи необходимо просто сгенерировать все n! всевозможных перестановок вершин полного графа,подсчитать для перестановки длину маршрута и выбрать минимальный. Но тогда задача оказывается неосуществимой для достаточно небольших n.
Так же известно, что Задача задача о коммивояжере относится к NP-полным задачам. ==
