Постановка задачи
Путешественнику необходимо посетить все города из списка, где известны расстояния между всеми городами, и каждый город нужно посетить только один раз. Каков самый короткий маршрут, по которому он посетит каждый город ровно один раз и вернется в исходный город?
Решение:
Задача коммивояжера - самая известная вычислительная задача. Мы можем использовать метод грубой силы, чтобы оценить каждый возможный тур и выбрать лучший. Для n числа вершин в графе существует (n -1)! количество возможностей. Вместо перебора с использованием подхода динамического программирования решение может быть получено за меньшее время, хотя нет алгоритма с полиномиальным временем.
На рисунке 1.0 четыре города представлены в виде ориентированного графа, а стоимость каждого ребра показана в матрице смежности. Предположим, что продавец, начиная с индекса города 1, объезжает каждый узел и возвращается к первому узлу. Ниже показан каждый возможный маршрут с его минимальной стоимостью.
Здесь все возможные пути могут быть найдены путем перехода от корневого узла к любому из листовых узлов. Минимальная стоимость достижения при выходе из любого узла указана на каждой ветви дерева. поэтому, если какой-либо узел имеет два или более поддерева, чем минимальная стоимость для всех ветвей, принимается в качестве окончательной стоимости.
Таким образом, продавец деревьев должен пройти путь 1–2–3–4–1 или 1–2–4–3–1 для минимального расстояния, которое составляет 35.
Эту проблему также можно решить с помощью динамического программирования, которое требует меньше времени.
Решение с использованием динамического программирования:
Пусть данный набор вершин равен {1, 2, 3, 4,… n}. Давайте рассмотрим 1 как начальную и конечную точку вывода. Для каждой второй вершины i (кроме 1) мы находим путь с минимальной стоимостью с 1 в качестве начальной точки, i в качестве конечной точки и всех вершин, появляющихся ровно один раз. Пусть стоимость этого пути будет cost (i), стоимость соответствующего цикла будет cost (i) + dist (i, 1), где dist (i, 1) - расстояние от i до 1. Наконец, мы возвращаем минимум из всех значений [cost (i) + dist (i, 1)]. Пока это выглядит просто. Теперь вопрос в том, как получить стоимость (i)?
Чтобы рассчитать стоимость (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, так что все подмножества не содержат n-го числа.
Используя указанное выше соотношение повторяемости, мы можем написать решение на основе динамического программирования. Существует не более O (n * 2n) подзадач, и каждая из них требует линейного времени для решения. Таким образом, общее время работы составляет O (n2 * 2n). Временная сложность намного меньше, чем O (n!), Но все же экспоненциальна. Требуемое пространство также экспоненциально. Таким образом, этот подход также неосуществим даже для немного большего количества вершин.
Эту проблему также можно решить с помощью приближенного алгоритма, который требует меньше времени.
Для получения дополнительной информации посетите geeksforgeeks.org.
Спасибо.
