Задача коммивояжера, ДП по подмножествам — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вариант "наивного" решения:)
Строка 10: Строка 10:
 
Если же граф симметрический (т.е. для всех пар вершин (i, j) длины дуг в обоих направлениях одинаковы ), то каждая поездка в обоих направлениях имеет одну и ту же длину/стоимость. Симметрия делит пополам количество возможных поездок.
 
Если же граф симметрический (т.е. для всех пар вершин (i, j) длины дуг в обоих направлениях одинаковы ), то каждая поездка в обоих направлениях имеет одну и ту же длину/стоимость. Симметрия делит пополам количество возможных поездок.
  
== Вариант "наивного" решения: ==
+
== Варианты решения: ==
  
 
Можно предположить, что для решения задачи необходимо просто сгенерировать все n! всевозможных перестановок вершин полного графа,подсчитать для перестановки длину маршрута и выбрать минимальный. Но тогда задача оказывается неосуществимой для достаточно небольших n.
 
Можно предположить, что для решения задачи необходимо просто сгенерировать все n! всевозможных перестановок вершин полного графа,подсчитать для перестановки длину маршрута и выбрать минимальный. Но тогда задача оказывается неосуществимой для достаточно небольших n.
  
 
Так же известно, что задача о коммивояжере относится к NP-полным задачам.
 
Так же известно, что задача о коммивояжере относится к NP-полным задачам.

Версия 03:51, 13 декабря 2010

Задача о коммивояжере (англ. travelling-salesman problem) - это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из n точек на плоскости.

Формулировка задачи:

Коммивояжер должен посетить N городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?

Представление:

Чтобы использовать математические процессы для решения, реальная ситуация должна отображаться сначала простой моделью. Задачу коммивояжера можно смоделировать с помощью графа. При этом вершины можно считать городами, в то время как каждая дуга (i, j) описывает связь между этими 2 вершинами i и j. Каждая дуга имеет свой вес с(i, j). Поездка (также цикл Гамильтона) - это цикл в этом графе, который проходит через каждую вершину ровно один раз. Целью является найти более короткую поездку.

Если же граф симметрический (т.е. для всех пар вершин (i, j) длины дуг в обоих направлениях одинаковы ), то каждая поездка в обоих направлениях имеет одну и ту же длину/стоимость. Симметрия делит пополам количество возможных поездок.

Варианты решения:

Можно предположить, что для решения задачи необходимо просто сгенерировать все n! всевозможных перестановок вершин полного графа,подсчитать для перестановки длину маршрута и выбрать минимальный. Но тогда задача оказывается неосуществимой для достаточно небольших n.

Так же известно, что задача о коммивояжере относится к NP-полным задачам.