|
|
| (не показано 90 промежуточных версий 9 участников) |
| Строка 1: |
Строка 1: |
| − | Задача о коммивояжере (англ. ''travelling-salesman problem'') - это задача, в которой определяется кратчайший замкнутый путь, соединяющий заданное множество, которое состоит из <tex> N </tex> точек на плоскости.
| + | #перенаправление [[Гамильтоновы графы]] |
| − | | |
| − | == Формулировка задачи: ==
| |
| − | Коммивояжер должен посетить <tex> N </tex> городов, побывав в каждом из них ровно по одному разу и завершив путешествие в том городе, с которого он начал. В какой последовательности ему нужно обходить города, чтобы общая длина его пути была наименьшей?
| |
| − | | |
| − | == Представление: ==
| |
| − | | |
| − | Чтобы использовать математические процессы для решения, реальная ситуация должна отображаться сначала простой моделью. Задачу коммивояжера можно смоделировать с помощью графа. При этом вершины можно считать городами, в то время как каждая дуга <tex>(i, j) </tex> описывает связь между этими 2 вершинами <tex>i</tex> и <tex>j</tex>. Каждая дуга имеет свой вес с(i, j). Поездка (также цикл Гамильтона) - это цикл в этом графе, который проходит через каждую вершину ровно один раз. Целью является найти более короткую поездку.
| |
| − | | |
| − | == Варианты решения: ==
| |
| − | | |
| − | Можно предположить, что для решения задачи необходимо просто сгенерировать все <tex> N! </tex> всевозможных перестановок вершин полного графа,подсчитать для перестановки длину маршрута и выбрать минимальный. Но тогда задача оказывается неосуществимой для достаточно небольших <tex>N</tex>.
| |
| − | | |
| − | Так же известно, что задача о коммивояжере относится к NP-полным задачам.
| |
| − | | |
| − | == Динамическое программирование по подмножествам ==
| |
| − | | |
| − | Задача о коммивояжере сводится к поиску кратчайшего гамильтонова пути в графе.
| |
| − | | |
| − | Смоделируем данную задачу при помощи графа. При этом вершины можно считать городами, а ребра - дорогами. Пусть в графе <tex> P = (V, E)</tex> <tex> N </tex>
| |
| − | вершин и каждое ребро <tex>(i, j) \in E </tex> имеет некоторый вес <tex> d(i, j)</tex>. Необходимо найти гамильтонов путь, сумма весов по ребрам которого минимальна.
| |
| − | | |
| − | Пусть dp[pos][i] обозначает длину кратчайшего гамильтонова пути подмножества вершин pos, заканчивающегося в вершине i.
| |
| − | | |
| − | Динамика считается по следующим соотношениям:
| |
| − | dp[pos][i] = 0, если count(pos) = 1 и bit(i, pos) = 1;
| |
| − | , если count(pos) > 1 и bit(i, pos) = 1;
| |
| − | dp[pos][i] = ∞ во всех остальных случаях.
| |
| − | | |
| − | Теперь искомая минимальная длина пути. Если pmin = ∞, то гамильтонова пути в графе, нет. Восстановить сам путь несложно. Пусть минимальный путь заканчивается в вершине i. Тогда j ≠ i, для которого , является предыдущей вершиной пути. Теперь удалим i из множества и только что описанным способом найдем вершину предыдущую к j. Продолжая процесс пока не останется одна вершина, мы найдем весь гамильтонов путь.
| |
| − | | |
| − | Данное решение требует O(2nn) памяти и O(2nn2) времени.
| |
