Обобщённая задача коммивояжёра | это... Что такое Обобщённая задача коммивояжёра? (original) (raw)

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

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

Как и задача коммивояжёра, обобщённая задача коммивояжёра относится к классу NP-трудных задач. Для доказательства достаточно рассмотреть частный случай задачи, когда каждый кластер содержит ровно одну вершину, и задача сводится к простой задаче коммивояжёра, которая является NP-трудной.

Содержание

1 Методы решения
- 1.1 Точные методы
- 1.2 Эвристические методы
  * 1.2.1 Простые эвристические методы
  * 1.2.2 Метаэвристики
2 Ссылки

Методы решения

Точные методы

Известно два эффективных метода точного решения обобщённой задачи коммивояжёра: Brunch-and-Cut метод описан в статье Fishetti, Salazar-Gonzalez и Toth[1], а также метод приведения обобщённой задачи к обычной задаче коммивояжёра, способы решения которой хорошо изучены[2].

Эвристические методы

Простые эвристические методы

К простейшим эвристическим методам решения обобщённой задачи коммивояжёра следует отнести жадный алгоритм, на каждом шаге выбирающий ребро наименьшей стоимости из множества рёбер, не нарушающих корректности решения, а также более эффективный метод ближайшего соседа (Nearest Neighbour), начинающий с произвольной вершины и на каждом шаге добавляющий к решению вершину, наиболее близкую к последней добавленной. Существуют также и другие эвристики, являющиеся модификациями известных эвристик для обычной задачи коммивояжёра.

В частности, часто используются следующие виды локального поиска:

2-opt, широко применяемый во многих задачах комбинаторной оптимизации, сводится к удалению двух рёбер из тура и вставке двух новых рёбер, не нарушающих корректности решения (в случае 2-opt вставляемые рёбра определены однозначно). Тур считается локальным минимумом, если в нём не существует ни одной пары рёбер, замена которых привела бы к улучшению решения. Таким образом, и размер окрестности, и сложность эвристики составляют , где — это число кластеров.
3-opt подобен 2-opt, однако на каждом удаляется не два, а три ребра. В случае 3-opt, для восстановления корректности тура существует восемь нетривиальных способов вставки новых рёбер. Один из этих способов сохраняет направление каждого из фрагментов тура, что является важным свойством для асимметричных задач. Размер окрестности, и сложность эвристики составляют .
Существуют естественные модификации 2-opt и 3-opt алгоритмов, дополнительно включающие поиск оптимальных вершин внутри изменяемых кластеров.
Insertion является частным случаем 3-opt. На каждой итерации алгоритм удаляет вершину и пытается найти более выгодную для неё позицию. Сложность алгоритма составляет . Широко применяется модификация, рассматривающая вставку не только удалённой вершины, но и любой другой вершины соответствующего кластера.
Cluster Optimization является локальным поиском, специфичным для обобщённой задачи коммивояжёра. Суть алгоритма заключается в нахождении кратчайшего пути через заданную последовательность кластеров. Иными словами, окрестность алгоритма включает в себя все туры, отличающиеся от исходного не более чем выбором вершин внутри каждого из кластеров. Размер исследуемой окрестности составляет:

$\prod_{i=1}^m |C_i|\,,$ где C_i — это кластер под номером . Применяя поиск кратчайшего пути в специально построенном графе, алгоритм находит локальный минимум за O(m s^3) , где $s = \max_i |C_i|$ . Таким образом, Cluster Optimization относится к классу локальных поисков с очень большой окрестностью, то есть исследует экспоненциальную окрестность за полиномиальное время.

Метаэвристики

Хорошо исследована область генетических алгоритмов, показавших свою эффективность для данной задачи. Первая работа в этой области принадлежит Snyder и Daskin[3], следующие наиболее значимые работы — это Silberholz и Golden[4] и Gutin и Karapetyan[5].

Ссылки

↑ M. Fischetti, J.J. Salazar-Gonzalez, and P. Toth. A Branch-and-Cut algorithm for the symmetric generalized traveling salesman problem. Operations Research 45 (3) (1997), 378-394.
↑ D. Ben-Arieh, G. Gutin, M. Penn, A. Yeo, and A. Zverovitch. Transformations of generalized ATSP into ATSP, Operations Research Letters 31 (2003), 357-365.
↑ L.V. Snyder and M.S. Daskin. A random-key genetic algorithm for the generalized traveling salesman problem. European Journal of Operational Research 174 (2006), 38−53.
↑ J. Silberholz and B. Golden. The Generalized Traveling Salesman Problem: a new Genetic Algorithm approach. Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, 2007, 165−181.
↑ G. Gutin and D. Karapetyan. Gregory Gutin and Daniel Karapetyan. A Memetic Algorithm for the Generalized Traveling Salesman Problem. Natural Computing 9(1), pages 47-60, Springer 2010.

NP-полные задачи
Математика
Исследование операций:Оптимизация:Комбинаторная оптимизация
Максимизационная задача укладки (упаковки)	Упаковка в контейнеры (двумерная упаковка • линейная упаковка • упаковка по весу • упаковка по стоимости) • Задача о ранце (рюкзаке)
Теория графов теория множеств	Задача о вершинном покрытии • Задача о клике • Задача о независимом множестве (наборе) • Задача о покрытии множества • Задача Штейнера • Задача коммивояжёра • Обобщённая задача коммивояжёра
Алгоритмические задачи	Задача выполнимости булевых формул (в конъюнктивной нормальной форме)
Логические игры и головоломки	Обобщённые пятнашки с костяшками >15) (задача поиска кратчайшего решения) • Задачи, решения которых применяются в Тетрис • Задача обобщённого судоку • Задача о заполнении латинского квадрата • Задача какуро
См. также	Прикладная математика • Теория алгоритмов • Динамическое программирование • 21 NP-полная задача Карпа
Классы сложности