Рубрики

Задача коммивояжера | Набор 1 (Наивное и Динамическое Программирование)

Задача коммивояжера (TSP): учитывая набор городов и расстояние между каждой парой городов, проблема состоит в том, чтобы найти кратчайшее Возможный маршрут, который посещает каждый город ровно один раз и возвращается в исходную точку.
Обратите внимание на разницу между гамильтоновым циклом и TSP. Задача цикла Гамильтонина — найти тур, который посещает каждый город ровно один раз. Здесь мы знаем, что гамильтонов тур существует (так как граф полон), и на самом деле существует много таких туров, проблема состоит в том, чтобы найти гамильтонов цикл с минимальным весом.

Например, рассмотрим график, показанный на рисунке справа. Тур TSP на графике 1-2-4-3-1. Стоимость тура 10 + 25 + 30 + 15, что составляет 80.

Проблема известная NP трудная проблема. Не существует полиномиального времени для решения этой проблемы.

Ниже приведены различные решения проблемы коммивояжера.

Наивное решение:
1) Рассмотрите город 1 как начальную и конечную точку.
2) Генерировать все (n-1)! Перестановки городов.
3) Рассчитать стоимость каждой перестановки и отслеживать минимальную перестановку затрат.
4) Вернуть перестановку с минимальными затратами.

Сложность времени: Θ (n!)

Динамическое программирование:
Пусть заданным набором вершин будет {1, 2, 3, 4,… .n}. Давайте рассмотрим 1 как начальную и конечную точку вывода. Для каждой другой вершины i (кроме 1) мы находим путь минимальной стоимости с 1 в качестве начальной точки, i в качестве конечной точки и всех вершин, которые появляются ровно один раз. Пусть стоимость этого пути будет стоить (i), стоимость соответствующего цикла будет стоить (i) + dist (i, 1), где dist (i, 1) — это расстояние от i до 1. Наконец, мы возвращаем минимум всех значений [cost (i) + dist (i, 1)]. Это выглядит просто пока. Теперь вопрос, как получить стоимость (я)?
Чтобы рассчитать стоимость (i) с использованием динамического программирования, нам нужно иметь рекурсивное отношение с точки зрения подзадач. Определим термин C (S, i) как стоимость пути минимальной стоимости, посещающего каждую вершину в множестве S ровно один раз, начиная с 1 и заканчивая на i .
Мы начнем со всех подмножеств размера 2 и вычислим C (S, i) для всех подмножеств, где S — это подмножество, затем вычислим C (S, i) для всех подмножеств S размера 3 и так далее. Обратите внимание, что 1 должен присутствовать в каждом подмножестве.

If size of S is 2, then S must be {1, i},
 C(S, i) = dist(1, i) 
Else if size of S is greater than 2.
 C(S, i) = min { C(S-{i}, j) + dis(j, i)} where j belongs to S, j != i and j != 1.

Для набора размера n мы рассматриваем n-2 подмножества каждого размера n-1, так что все подмножества не имеют nth в них.
Используя вышеупомянутое рекуррентное отношение, мы можем написать решение на основе динамического программирования. Существует не более O (n * 2 n ) подзадач, и для решения каждой из них требуется линейное время. Таким образом, общее время работы составляет O (n 2 * 2 n ). Временная сложность намного меньше, чем O (n!), Но все же экспоненциальная. Требуемое пространство также экспоненциально. Так что этот подход также невозможен даже для немного большего числа вершин.

Вскоре мы обсудим приближенные алгоритмы задачи коммивояжера.

Следующая статья: Задача коммивояжера | Набор 2

Ссылки:
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf
http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Задача коммивояжера | Набор 1 (Наивное и Динамическое Программирование)

0.00 (0%) 0 votes