Материал из Викиконспекты
|
|
| (не показана 91 промежуточная версия 9 участников) |
| Строка 1: |
Строка 1: |
| − | Задача о коммивояжере (англ. ''travelling-salesman problem'') - это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из n точек на плоскости.
| + | #перенаправление [[Гамильтоновы графы]] |
| − | | |
| − | == Формулировка задачи: ==
| |
| − | Коммивояжер должен посетить N городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?
| |
| − | | |
| − | == Представление: ==
| |
| − | | |
| − | Чтобы использовать математические процессы для решения, реальная ситуация должна отображаться сначала простой моделью. Задачу коммивояжера можно смоделировать с помощью графа. При этом вершины можно считать городами, в то время как каждая дуга (i, j) описывает связь между этими 2 вершинами i и j. Каждая дуга имеет свой вес с(i, j). Поездка (также цикл Гамильтона) - это цикл в этом графе, который проходит через каждую вершину ровно один раз. Целью является найти более короткую поездку.
| |
| − | | |
| − | Если же граф симметрический (т.е. для всех пар вершин (i, j) длины дуг в обоих направлениях одинаковы ), то каждая поездка в обоих направлениях имеет одну и ту же длину/стоимость. Симметрия делит пополам количество возможных поездок.
| |
| − | | |
| − | == Варианты решения: ==
| |
| − | | |
| − | Можно предположить, что для решения задачи необходимо просто сгенерировать все n! всевозможных перестановок вершин полного графа,подсчитать для перестановки длину маршрута и выбрать минимальный. Но тогда задача оказывается неосуществимой для достаточно небольших n.
| |
| − | | |
| − | Так же известно, что задача о коммивояжере относится к NP-полным задачам.
| |
Текущая версия на 20:48, 9 января 2016
