최대 가중치 그래프에 꼭짓점 세트 연결

Question

이것은 기본적으로 가능한 최소 도로로 n 개의 대상을 연결하는 문제입니다.

입력 쉽게 계산 정점들의 세트 (A, B, ..., N)

두 꼭지점 사이의 에지의 가중치 (예를 들어 두 꼭지점 사이의 직교 거리)이다

나는 euclidian 공간에서 꼭지점 집합을 주어진 알고리즘으로 연결 그래프를 구성하고 가장자리의 총 무게가 될 수있는 한 작은 가장자리 집합을 반환하고자합니다.

그래프 언어에서이 그래프는 연결된 그래프의 최소 스패닝 트리입니다. 무력으로

내가 가진 것 :

이

1. 모든 정점 사이의 모든 가능한 가장자리를 정의 - 다음 n을 가지고, n을 정점을 가지고 있다고 (N-1) 전체 그래프
에서/2 가장자리
2. 가능한 에지는 켜짐 또는 꺼짐 일 수 있습니다 (2 개 상태)
3. 모든 가능한 에지 켜짐/꺼짐 조합을 통해 이동하십시오 : 2^(n (n-1)/2)!
4. 나머지 조합부터 그래프
5. 을 연결하지 것이라고 모든 사람들, 그 합 에지 가중치의 나는 이것을 이해하는 모든

의 가장 작은 것을 찾기를 NP-하드 문제가되는 무시 . 그러나, 현실적으로는 제 신청을 위해 은 최대 11 개의 정점을 가지고 있습니다. 나는 이것을 전형적인 현대의 스마트 폰이나 작은 서버 크기로 해결할 수 있기를 바라고있다.

두 번째 변형으로 각 꼭지점이 최대 하나의 다른 꼭지점에 연결된다는 제한과 동일한 목표를 얻고 싶습니다. 그래프가 연결되어있는 한 기본적으로 하나의 트레이스를 얻고, 임의의 지점에서 시작하고 다른 지점에서 마무리합니다. 시작한 곳으로 돌아갈 필요가 없습니다. 그래프 언어에서 이것은 오픈 유클리드 여행 세일즈맨 문제입니다.

일부 의사 코드 알고리즘이 많은 도움이 될 것입니다.

Answer 1

첫 번째 문제의 경우 확인을 위해 Minimum Spanning Tree을 작성해야합니다. 이를 수행하는 알고리즘은 Prim 및 Kruskal입니다. 그러나 완전한 그래프를위한 치료법에 대한 첫 번째 링크를 살펴보십시오.

두 번째 문제는 좀 더 복잡해집니다. 문제는 Open Traveling Salesman Problem (oTSP)이됩니다. 이전 링크를 읽는 것은 아마 유클리드와 비대칭에 초점을 맞 춥니 다.모든 노드가 다른 하나에 연결되어까지

당신은 한 노드를 추가 :

1. Create a list sortedList that stores each pair of nodes i and j and is sorted by the 
    weight w(i,j). 
2. Create a HashSet connectedNodes that is empty at the beginning 
3. while (connectedNodes.size() < n) 
    element := first element of sortedList 
    if (connectedNodes.isEmpty()) 
     connectedNodes.put(element.nodeI); 
     connectedNodes.put(element.nodeJ); 
     delete element from sortedList 
    else 
     for(element in sortedList) //start again with the first 
     if(connectedNodes.get(element.nodeI) || connectedNodes.get(element.nodeJ)) 
      if(!(connectedNodes.get(element.nodeI) && connectedNodes.get(element.nodeJ))) 
       //so it does not include already both nodes 
       connectedNodes.put(element.nodeI); 
       connectedNodes.put(element.nodeJ); 
       delete element from sortedList 
       break; 
      else 
       continue; 

그래서 내가 3 단계가 조금 설명 :

감사

Answer 2

메이비 당신은 greedy 알고리즘을 시도 할 수 . 노드가 이미 connectedNodes 목록에있는 다른 노드에 연결되어있는 경우 노드를 추가하기 때문에 그래프가 연결되어 있는지 확인해야합니다.

이 알고리즘은 욕심이 많습니다. 즉, 해결책이 최적이라는 것을 의미하지는 않습니다. 그러나 가장 좋은 근사값입니다 (항상 sortedList이 모서리의 무게로 정렬되기 때문에).

은 HashSet이기 때문에 connectedNodes이 아니기 때문에 런타임이 더 빠릅니다.

최악의 경우 크기가있는 전체 목록을 통해 모든 단계를 실행하기 때문에 런타임은 O (n^3)의 시작과 그 아래 정렬을 위해 O (n^2)이어야합니다. 왜냐하면 당신은 각 단계에서 하나의 요소를 추가하기 때문에 n^2를 사용하고 그것을 n 번 할 수 있습니다.

하지만 O (n^2)보다 훨씬 빨리 요소를 찾으면 대부분 O (n)이라고 생각합니다.

Answer 3

optimap tsp solver fron gebweb 또는 선형 프로그램 해석기로 travelsalesman 문제와 해밀턴 경로 문제를 해결할 수 있습니다. 하지만 첫 번째 질문은 질문 태그가 틀렸을 수도있는 최소 스패닝 트리를 요구하는 것 같습니다.

Answer 4

첫 번째 문제의 경우 O(n^2 * 2^n) 시간 알고리즘이 있습니다. 기본적으로 dynamic programming을 사용하여 검색 공간을 줄일 수 있습니다. 모든 버텍스 집합이 V이라고 가정하면 상태 공간은 V의 모든 하위 집합으로 구성되며 목표 함수 f(S)은 버텍스를 연결하는 모서리의 최소 가중치 합이 S입니다. 각 상태가 S 인 경우 모든 가장자리에 대해 (u, v)을 열거 할 수 있습니다. u은 S이고 v은 V - S이고 업데이트는 f(S + {v})입니다. 가능한 모든 상태를 확인한 후 최적의 대답은 f(V)입니다.

아래는 아이디어를 설명하기위한 샘플 코드이지만 역방향으로 구현됩니다.

const int n = 11; 
int weight[n][n]; 
int f[1 << n]; 
for (int state = 0; state < (1 << n); ++state) 
{ 
    int res = INF; 
    for (int i = 0; i < n; ++i) 
    { 
     if ((state & (1 << i)) == 0) continue; 
     for (int j = 0; j < n; ++j) 
     { 
      if (j == i || (state & (1 << j)) == 0) continue; 
      if (res > f[state - (1 << j)] + weight[i][j]) 
      { 
       res = f[state - (1 << j)] + weight[i][j]; 
      } 
     } 
    } 
    f[state] = res; 
} 
printf("%d\n", f[(1 << n) - 1]); 

두 번째 문제에 대해서는 미안하지만 잘 이해하지 못합니다. 어쩌면 몇 가지 예를 제시해야할까요?