Решение TSP с использованием динамического программирования
Ага, потому что решений не хватает…
Пока я проводил исследование для другого поста из моей серии статей о транспорте (I, II, следите за обновлениями для III), я искал решение динамического программирования для Задачи коммивояжера (TSP).
Я нашел много ресурсов, но ни один из них мне не понравился. Либо они были слишком абстрактными, слишком теоретическими, представлены в длинном видео, которое я не хотел смотреть, либо просто, знаете ли, не в моем стиле. Как будто я не понял логики.
Так что, честно говоря, я даже не собирался писать этот пост, потому что думал, что он был бы написан уже тысячу раз. Но разве жизнь не удивительна?
Полный код этого сообщения можно найти здесь.
Настройки
Более приятный и веселый вариант настройки вы можете прочитать в этом посте, но суть в следующем. У нас есть n точка на плоскости, и мы хотим найти кратчайший путь, который посещает каждую точку ровно один раз.
Ускоренный курс DP
На самом деле я действительно хочу сказать, что это не ускоренный курс DP 😇
Если вы не знакомы с концепциями динамического программирования, я рекомендую более хорошее введение, чем мое, в этот прекрасный метод. К счастью, забавный и интуитивно понятный вариант уже существует! Посмотрите это отличное видео Сираджа Равала и присоединяйтесь к нам в продолжении 🤓
Построение дерева DP
В динамическом программировании (DP) мы создаем решение по мере продвижения. В нашем случае это означает, что нашим начальным состоянием будет любой первый узел, который нужно посетить, а затем мы расширяем каждое состояние, добавляя все возможные узлы, чтобы создать путь размером 2, и так далее. Каждый раз, когда мы обращаемся к частичному решению, к которому мы обращались ранее, мы сохраняем только лучший результат.
Ага!
Но что такое «уже посещенное частичное решение», спросите вы?
И вы правильно спросите!
Выяснение того, что следует «хранить в памяти», - один из ключевых элементов успешное решение DP. После некоторых проб и ошибок я решил сохранить в памяти как последний, так и предпоследний узлы, которые посещались для каждого частичного решения.
Как только вы определились с тем, что хотите сохранить в памяти, код становится довольно простым и практически не меняется в разных реализациях DP для решения различных задач:
Повторение кратчайшего пути
Как только мы достигли конца дерева, то есть пути, которые мы держим в нашей памятке, завершены, «все, что нам осталось» - это повторить наши шаги, чтобы найти оптимальный путь.
К счастью, мы запомнили последний и предпоследний узлы в каждом частичном пути!
Итак, первым шагом будет просмотр последнего слоя со всеми полными путями и выбор последнего узла с наименьшей общей стоимостью.
Оттуда мы можем повторить наши шаги, используя наши предпоследние узлы.
Сравнение с эвристическим решением
Хорошо, теперь, когда у нас есть оптимальное решение нашей проблемы TSP, что мы можем с ним сделать?
Что ж, дело в том, что это не так уж и много ...
TSP - это проблема NP-Complete, и ее решение до оптимальности практически невозможно масштабировать. К счастью, в предыдущем посте мы решили TSP с помощью быстрого эвристического метода. Многие из вас спрашивали меня после этого поста - как это решение сравнивается с оптимальным? И я наконец могу ответить!
Вот это да!! Вот так выглядит экспоненциальный рост !! 😨
Помимо сложности, эвристическое решение всегда приближает его к оптимальному 😅
Для самого большого ввода в этом эксперименте, даже когда мы смотрим на окончательный результат, он выглядит примерно одинаково 🎯
Ааааааааааааааааааааааааааааааааааётся всё, ребята Следите за нашим следующим приключением!
Полный код этого сообщения можно найти здесь.
