Обобщённая задача коммивояжёра

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

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

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

Источник: Википедия