Обобщённая задача коммивояжёра — задача комбинаторной оптимизации, являющаяся обобщением хорошо известной задачи коммивояжёра. Исходными данными для задачи является множество вершин, разбиение этого множества на так называемые кластеры, а также матрица стоимостей перехода из одной вершины в другую. Задача заключается в нахождении кратчайшего замкнутого пути, который бы посетил по одной вершине в каждом кластере (существует также модификация, когда путь должен посетить хотя бы по одной вершине в каждом кластере).
В зависимости от свойств матрицы стоимостей, задача может быть симметричной, если матрица симметричная, или асимметричной в противном случае. Одним из наиболее часто рассматриваемых частных случаев симметричной задачи является евклидова или планарная задача, когда каждая вершина имеет свои координаты в пространстве, и стоимость перехода между вершинами соответствует евклидову расстоянию между соответствующими точками в пространстве.
Как и задача коммивояжёра, обобщённая задача коммивояжёра относится к классу NP-трудных задач. Для доказательства достаточно рассмотреть частный случай задачи, когда каждый кластер содержит ровно одну вершину, и задача сводится к простой задаче коммивояжёра, которая является NP-трудной.
Известно два эффективных метода точного решения обобщённой задачи коммивояжёра: Brunch-and-Cut[1], а также метод приведения обобщённой задачи к обычной задаче коммивояжёра, способы решения которой хорошо изучены[2].
В 2002 году показано[3], что обобщённая задача коммивояжера может быть сведена к обыкновенной задаче коммивояжера той же размерности заменой матрицы весов[источник не указан 1441 день].
К простейшим эвристическим методам решения обобщённой задачи коммивояжёра следует отнести жадный алгоритм, на каждом шаге выбирающий ребро наименьшей стоимости из множества рёбер, не нарушающих корректности решения, а также более эффективный метод ближайшего соседа (Nearest Neighbour), начинающий с произвольной вершины и на каждом шаге добавляющий к решению вершину, наиболее близкую к последней добавленной. Существуют также и другие эвристики, являющиеся модификациями известных эвристик для обычной задачи коммивояжёра.
В частности, часто используются следующие виды локального поиска:
где — это кластер под номером . Применяя поиск кратчайшего пути в специально построенном графе, алгоритм находит локальный минимум за , где . Таким образом, Cluster Optimization относится к классу локальных поисков с очень большой окрестностью, то есть исследует экспоненциальную окрестность за полиномиальное время.
Хорошо исследована область генетических алгоритмов, показавших свою эффективность для данной задачи. Первая работа в этой области принадлежит Снайдеру и Даскину[4], в дальнейшем важные результаты получены Зильбергольцем и Голденом[5], Гютеном и Карапетяном[6].
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .