여러 세트의 최단 경로

나는 모든 세트에서 한 번만 노드를 사용할 수있는 다양한 세트의 노드 사이에 최단 경로를 찾아야합니다. 모든 노드는 다른 모든 노드와 거리를두고 연결됩니다. 세트 내의 노드가 그들 사이에 연결되지 않은 예외가 있습니다. 경로에는 모든 세트에서 하나의 노드가 있어야합니다.여러 세트의 최단 경로

예 :

Set A - [a1, a2, a3] 
    Set B - [b1, b2] 
    Set C - [c1] 
    Set D - [d1, d2, d3] 
    Set Z - [z1, z2, z3]

노드는, A1있다 A2, A3, B1, B2 ...

예. A1가

B1, B2, C1, D1, D2, D3, Z2, Z1과 관련이있는 노드 Z3

또는 노드 C1가

와 연결되어
A1, A2, A3, B1, B2, D1, D2, D3, Z2, Z1, Z3

T 그 posibble 경로가 될 수있다 :

A1 -> B1 -> C1 -> D1 -> Z1, 또는 C1 -> Z2를 -> A3 -> B1 - 모든 사이> D2

거리는 노드 (집합 내의 노드를 제외하고는 연결이 없음)는 0에서 1 사이 일 수 있습니다.

출처

2013-04-22 Matej

Dijkstra로 태그를 지정 했으므로 이미 아이디어가 있습니까? 지금까지 무엇을 코딩 했습니까? –

여행 판매원 문제와 같은 소리가납니다. – nhahtdh

은 노드 수가 n 인 노드에서 최대 로그 함수의 집합으로 제한되지 않는 한 tsp와 같지 않아야합니다. 어떤 오라클이 각 노드에서 선택할 노드를 미리 알려 주겠다고 상상해보십시오. 각 집합에 대해 다른 모든 노드를 놓습니다. 귀하의 문제는 TSP 인스턴스가되었습니다. nb : 원래 문제로 동일한 세트를 여러 번 방문 할 수있는 경우 해당 tsp 문제에 반영되지 않지만 검색이 더 어려워집니다. – collapsar

이것은 일반화 된 여행 판매원 문제로 알려져 있습니다. C. Noon & J.Bean, An Efficient Transformation of the Generalized Traveling Salesman Problem 가입일

일반화 외판원 문제 (GTSP)의 선택과 순서의 결정과 관련된 문제에 대한 유용한 모델이다. 문제의 비대칭 버전은 노드 N, 연결 원호 A 및 해당 원호 비용 벡터를 가진 유향 그래프에서 정의됩니다. c. 노드는 상호 배타적이며 철저한 노드 세트로 사전 그룹화됩니다. 연결 호는 다른 세트에 속한 노드 사이에서만 정의됩니다. 즉, 인트라셋 호가 없습니다. 정의 된 각 호에는 해당하는 음수가 아닙니다. GTSP는 각 노드 집합에서 정확하게 하나의 노드를 포함하는 최소 비용 m 아크 사이클을 찾는 문제로 설명 될 수 있습니다.

이 백서에서는 문제를 표준 여행용 세일즈맨 (Traveling Salesman) 문제로 변환하는 방법에 대해 설명합니다.

출처

2013-04-22 18:24:49

답변

관련 문제