| dbo:abstract
|
- In combinatorial optimization, the set TSP, also known as the generalized TSP, group TSP, One-of-a-Set TSP, Multiple Choice TSP or Covering Salesman Problem, is a generalization of the traveling salesman problem (TSP), whereby it is required to find a shortest tour in a graph which visits all specified subsets of the vertices of a graph. The subsets of vertices must be disjoint, since the case of overlapping subsets can be reduced to the case of disjoint ones. The ordinary TSP is a special case of the set TSP when all subsets to be visited are singletons. Therefore, the set TSP is also NP-hard. There is a transformation for an instance of the set TSP to an instance of the standard asymmetric TSP. The idea is to connect each subset into a directed cycle with edges of zero weight, and inherit the outgoing edges from the original graph shifting by one vertex backwards along this cycle. The salesman, when visiting a vertex v in some subset, walks around the cycle for free and exits it from the vertex preceding v by an outgoing edge corresponding to an outgoing edge of v in the original graph. The Set TSP has a lot of interesting applications in several path planning problems. For example, a two vehicle cooperative routing problem could be transformed into a set TSP, tight lower bounds to the Dubins TSP and generalized Dubins path problem could be computed by solving a Set TSP. (en)
- Обобщённая задача коммивояжёра — задача комбинаторной оптимизации, являющаяся обобщением хорошо известной задачи коммивояжёра. Исходными данными для задачи является множество вершин, разбиение этого множества на так называемые кластеры, а также матрица стоимостей перехода из одной вершины в другую. Задача заключается в нахождении кратчайшего замкнутого пути, который бы посетил по одной вершине в каждом кластере (существует также модификация, когда путь должен посетить хотя бы по одной вершине в каждом кластере). В зависимости от свойств матрицы стоимостей, задача может быть симметричной, если матрица симметричная, или асимметричной в противном случае. Одним из наиболее часто рассматриваемых частных случаев симметричной задачи является евклидова или планарная задача, когда каждая вершина имеет свои координаты в пространстве, и стоимость перехода между вершинами соответствует евклидову расстоянию между соответствующими точками в пространстве. Как и задача коммивояжёра, обобщённая задача коммивояжёра относится к классу NP-трудных задач. Для доказательства достаточно рассмотреть частный случай задачи, когда каждый кластер содержит ровно одну вершину, и задача сводится к простой задаче коммивояжёра, которая является NP-трудной. (ru)
- Узагальнена задача комівояжера - задача комбінаторної оптимізації, що є узагальненням добре відомої задачі комівояжера. Вихідними даними для задачі є множина вершин, розбиття цієї множини на так звані кластери, а також матриця вартостей переходу з однієї вершини в іншу. Завдання полягає в знаходженні найкоротшого замкнутого шляху, який би проходив через одну вершину в кожному кластері (існує також модифікація, коли шлях повинен пройти хоча б через одну вершину в кожному кластері). Залежно від властивостей матриці вартостей, задача може бути симетричною, якщо матриця симетрична, або асиметричною в іншому випадку. Одним з найчастіше описуваних часткових випадків симетричної задачі є евклідова або планарна задача, коли кожна вершина має свої координати у просторі, і вартість переходу між вершинами відповідає евклідовій відстані між відповідними точками у просторі. Як і задача комівояжера, узагальнена задача комівояжера відноситься до класу NP-складних задач. Для доведення досить розглянути частковий випадок задачі, коли кожен кластер містить рівно одну вершину, і задача зводиться до простої задачі комівояжера, яка є NP-складною. (uk)
|
| rdfs:comment
|
- In combinatorial optimization, the set TSP, also known as the generalized TSP, group TSP, One-of-a-Set TSP, Multiple Choice TSP or Covering Salesman Problem, is a generalization of the traveling salesman problem (TSP), whereby it is required to find a shortest tour in a graph which visits all specified subsets of the vertices of a graph. The subsets of vertices must be disjoint, since the case of overlapping subsets can be reduced to the case of disjoint ones. The ordinary TSP is a special case of the set TSP when all subsets to be visited are singletons. Therefore, the set TSP is also NP-hard. (en)
- Обобщённая задача коммивояжёра — задача комбинаторной оптимизации, являющаяся обобщением хорошо известной задачи коммивояжёра. Исходными данными для задачи является множество вершин, разбиение этого множества на так называемые кластеры, а также матрица стоимостей перехода из одной вершины в другую. Задача заключается в нахождении кратчайшего замкнутого пути, который бы посетил по одной вершине в каждом кластере (существует также модификация, когда путь должен посетить хотя бы по одной вершине в каждом кластере). (ru)
- Узагальнена задача комівояжера - задача комбінаторної оптимізації, що є узагальненням добре відомої задачі комівояжера. Вихідними даними для задачі є множина вершин, розбиття цієї множини на так звані кластери, а також матриця вартостей переходу з однієї вершини в іншу. Завдання полягає в знаходженні найкоротшого замкнутого шляху, який би проходив через одну вершину в кожному кластері (існує також модифікація, коли шлях повинен пройти хоча б через одну вершину в кожному кластері). (uk)
|
