효과적인 역 추적 알고리즘

Question

이 코드가 Basicaly이 작업은의 가장자리에 N 슬롯에 배치 N 디바이스의 저렴한 조합을 찾을 수 있습니다 동그라미에서 입력에 각 장치가 각 슬롯에 설치하는 데 드는 비용을 알려주는 비용 매트릭스가 있으며, 장치는 교차해서는 안되는 와이어로 서로 연결되어 있습니다. 항상 N-1 연결이 있습니다. 세부 정보 및 예는 위 링크에 있습니다.

내 문제는 내 솔루션이 너무 느리다는 것입니다. 일반적으로 크기가 13 인 드릴 헤드를 2 초 이내에 풀어야합니다. 너무 정확하게 : 이하 2S에서

12 
27 25 21 27 25 30 27 26 22 28 27 26 
21 22 26 30 25 28 21 21 22 23 22 30 
20 21 22 20 30 30 30 22 30 26 23 26 
27 30 24 21 20 24 26 24 22 22 24 22 
29 26 20 29 22 23 27 28 23 28 30 27 
21 21 20 30 20 22 25 29 22 29 27 24 
26 21 30 24 23 23 29 29 29 28 23 22 
25 27 21 24 20 24 27 23 27 28 25 26 
26 27 23 27 23 27 29 30 25 24 20 23 
20 22 25 20 23 26 20 29 21 24 25 20 
27 28 25 20 25 22 26 23 24 21 26 23 
23 21 28 23 26 30 22 30 25 26 26 20 
0 1 
1 2 
2 3 
3 4 
4 5 
5 6 
6 7 
7 8 
8 9 
9 10 
10 11 

(용액 262) 이 : I이보다 1S에 용해 입력해야한다.

13 
52 9 42 65 54 47 16 62 35 47 63 2 48 
25 4 12 25 58 12 45 62 70 60 40 17 33 
28 64 64 62 1 28 3 26 56 15 59 64 17 
    7 23 70 20 57 70 46 5 6 1 21 12 40 
62 53 5 15 22 43 57 15 26 42 51 16 38 
20 13 64 3 51 22 28 1 18 27 4 36 9 
11 20 41 65 29 63 54 28 31 63 27 59 41 
44 21 42 16 59 10 60 11 3 53 52 53 37 
41 51 18 4 38 6 22 49 15 51 54 61 7 
54 6 5 24 47 35 46 11 26 17 53 37 25 
34 42 6 54 40 47 59 25 53 53 37 9 64 
69 63 68 5 37 16 17 61 33 51 19 39 44 
    6 47 4 6 21 17 23 24 13 29 34 54 33 
0 1 
0 2 
0 3 
1 4 
1 5 
1 6 
2 7 
2 8 
2 9 
3 10 
3 11 
3 12 

을 따라서 (용액 165이다) 아무도이 일을하는 법을 알고 싶다면 완전히 잃어버린거야?

Answer 1

프로그램은 가능한 모든 순열을 생성 한 다음 순열이 유효한지 테스트합니다. 테스트 자체에는 중첩 루프가 포함됩니다. Photon이 제안한 것처럼 검사가보다 효율적이거나 검색 공간에서 막 다른 곳을 찾을 수 있도록 데이터 구조를 최적화 할 수 있습니다.

보다 효율적인 방법은 올바른 순열 만 만들어 지도록 프로그램을 설계하는 것입니다. 이렇게하면 검색 공간이 줄어들고 테스트가 제거됩니다.

      5   
          |   
         1 6 
         | | 
        0---2---7 
         | | 
         3 8    
         | 
         4 

당신이 도구 0에서 시작하여 슬롯 0에 넣어 경우, 다음 단계는을 배치하는 것입니다 :

당신이 문제를 설명의 예를 보면은 wrie 네트워크는 비순환 그래프이다 툴 1과 툴 3, 그리고 각각의 연결된 도구 들인 툴 2와 그 "자손들"의 순열. 도구 0의 관점에서이를 다음과 같이 트리로 바꿀 수 있습니다.

    [1237] 
       // | \ 
       1 2 [34] [678] 
       /| | \ \ 
        3 4 [56] 7 8 
          | \ 
          5 6 

여기에서 잎은 하나의 도구에 해당합니다. 가지에는 여러 가지 도구가 있습니다. 가지의 모든 prumutations 유효한 배열을 형성합니다. 물론

0 (1 2 (3 4) ((5 6) 7 8)) 

는 [56]의 모든 순열은 다른 지점의 모든 순열과 조합해야합니다.각 공간에서 0에서 9까지의 숫자를 거치지 않고 지점의 가능한 순열을 통해 일종의 주행 거리계를 구현하면됩니다.

모든 생성 된 순열이 유효하지만,이 기술은 모든 가능한 순열을 아직 생성하지 않습니다. 슬롯 0에 공구 0을 고정 시켰지만 그럴 필요는 없다는 것을 기억하십시오. 그러나 유효한 레이아웃의 지형은 그것을 회전시키고 슬롯 0에 도구 0을 넣는 등 8 개의 다른 레이아웃을 생성하는 데 사용할 수 있습니다.

이 기술을 사용하면 검색 공간이 9에서 줄어 듭니다. ~ 9 & middot; 4! & middot; 2! & middot; 삼! & middot; 2! 또는 70의 인자로 나타낼 수 있습니다. 테스트는 없지만보다 복잡한 데이터 구조를 사용합니다.

#include <stdio.h> 
#include <stdlib.h> 
#include <limits.h> 



enum { 
    N = 16       // hardcoded max. size 
}; 

struct tool { 
    int conn[N - 1];    // wire connections 
    int nconn; 

    int desc[N];     // "descendants" of the tree node 
    int ndesc; 

    int cost[N];     // row of the cost matrix 
    int used;      // flag for recursive descent 
}; 

struct drill { 
    int n; 
    struct tool tool[N]; 

    int root;      // root node  
    int branch[N];     // indices of branch nodes 
    int nbranch;     // permutating branches 

    int opt;      // current optimum 
}; 

void swap(int a[], int i, int j) 
{ 
    int s = a[i]; a[i] = a[j]; a[j] = s; 
} 

void reverse(int a[], int i, int n) 
{ 
    while (i < --n) swap(a, i++, n); 
} 

/* 
*  Turn an array to the next higher permutation. When the 
*  permutation is already the highest, return 0 and reset the 
*  array to the smalles permutation. Otherwise, return 1. 
*/ 
int next_perm(int a[], int n) 
{ 
    int i = n - 1; 
    int k = n - 1; 

    if (n < 2) return 0; 

    while (k && a[k] < a[k - 1]) k--; 
    if (k == 0) { 
     reverse(a, 0, n); 
     return 0; 
    } 
    k--; 

    while (i > k && a[i] < a[k]) i--; 
    swap(a, i, k); 
    reverse(a, k + 1, n); 

    return 1; 
} 

/* 
*  Insertion sort for sorting the branches at the beginning. 
*/ 
void sort(int a[], int len) 
{ 
    for (int i = 1; i < len; i++) { 
     int k = i; 

     while (k > 0 && a[k] < a[k - 1]) { 
      swap(a, k, k - 1); 
      k--; 
     } 
    } 
} 

/* 
*  Determine the list of descendants for each node. 
*/ 
void descend(struct drill *dr, int n) 
{ 
    struct tool *t = dr->tool + n; 

    t->ndesc = 1; 
    t->desc[0] = n; 

    t->used = 1; 

    for (int i = 0; i < t->nconn; i++) { 
     int m = t->conn[i]; 

     if (dr->tool[m].used == 0) { 
      t->desc[t->ndesc++] = m; 
      descend(dr, m); 
     } 
    } 

    if (t->ndesc > 1) { 
     sort(t->desc, t->ndesc); 
     dr->branch[dr->nbranch++] = n; 
    } 

    t->used = 0; 
} 

/* 
*  Fill the array a with the current arrangement in the tree. 
*/ 
int evaluate(struct drill *dr, int a[], int n) 
{ 
    struct tool *t = dr->tool + n; 
    int m = 0; 

    if (n == dr->root) { 
     a[0] = dr->root; 
     return 1 + evaluate(dr, a + 1, dr->tool[n].conn[0]); 
    } 

    for (int i = 0; i < t->ndesc; i++) { 
     int d = t->desc[i]; 

     if (d == n) { 
      a[m++] = d; 
     } else { 
      m += evaluate(dr, a + m, d); 
     } 
    } 

    return m; 
} 

/* 
*  Evaluate all possible permutations and find the optimum. 
*/ 
void optimize(struct drill *dr) 
{ 
    dr->opt = (1u << 31) - 1; 

    for (;;) { 
     int i = 0; 
     struct tool *t = dr->tool + dr->branch[0]; 

     for (int j = 0; j < dr->n; j++) { 
      int a[2 * N]; 
      int cost = 0; 

      evaluate(dr, a, dr->root); 

      for (int i = 0; i < dr->n; i++) { 
       int k = (i + j) % dr->n; 

       cost += dr->tool[i].cost[a[k]]; 
      } 

      if (cost < dr->opt) dr->opt = cost; 
     } 

     while (next_perm(t->desc, t->ndesc) == 0) { 
      i++; 

      if (i == dr->nbranch) return; 
      t = dr->tool + dr->branch[i];    
     } 
    } 
} 

/* 
*  Read and prepare drill data, then optimize. 
*/ 
int main(void) 
{ 
    struct drill dr = {0}; 

    fscanf(stdin, "%d", &dr.n); 

    for (int j = 0; j < dr.n; j++) { 
     for (int i = 0; i < dr.n; i++) { 
      scanf("%d", &dr.tool[j].cost[i]); 
     } 
    } 

    for (int i = 1; i < dr.n; i++) { 
     int a, b; 

     scanf("%d", &a); 
     scanf("%d", &b); 

     dr.tool[a].conn[dr.tool[a].nconn++] = b; 
     dr.tool[b].conn[dr.tool[b].nconn++] = a; 
    } 

    while (dr.tool[dr.root].nconn > 1) dr.root++; 
    dr.tool[dr.root].used = 1; 

    descend(&dr, dr.tool[dr.root].conn[0]); 
    optimize(&dr); 

    printf("%d\n", dr.opt); 

    return 0; 
} 

Answer 2

글쎄 당신은 아이디어를 물었습니다 : 모든 n 대신에! 순열, 당신은 확실하게 전선을 교차하게 할 순열을 무시하기 위해 역 추적을 사용해야합니다.

u는 전치 1 2 3 4 .... 11 1 2 3 부를 이미 와이어 너무 U 4 모든 순열을 무시할 수 .... 11 부, 수 크로스가 즉

Here`s 일부 구현 세부 정보의 의사 코드 :

int n;    // devices 
int cost[n][n];  // cost for putting device i into slot j 
bool used[n]={0}; // we need to keep track of used devices 
int slots[n];  // tracks which device is in which slot 
int edges[n-1];  //edges of a tree 
int ats = INF; 

bool cross(); //function that checks if any devices cross 
       //it seems you already wrote something similar, so i skipped this 

solve(int x, int total)  //function that tries putting remaining blocks into slot x 
{ 
if(x==n) //all slots are filled means we`re done 
{ 
ats = min(ats,total); 
return; 
} 

if(total > ats)  // some pruning optimization for some speedup 
return;    // cause no matter what we do we won`t be able to beat this cost 


for(int i=0; i<n; i++) 
if(!used[i])     //if device is not used and 
           //we can try putting it into our slot 
{ 
    slot[x] = i; 
    used[i] = true; 
    if(!cross())    //if putting device i into slot x makes some lines cross, skip it 
    solve(x+1,total + cost[i][x]); 
    used[i] = false; 
} 
} 

main() 
{ 

for (int i=0; i<n; i++) //try all devices into slot 0 
{ 
used[i] = true; 
slot[i]=0; 
solve(1,cost[i][0]); 
used[i] = false; 
} 

print(ats); 

}