効果的なバックトラッキングアルゴリズム

Question

私はこのコードを持ってBasicalyタスクはの端にNスロットに配置されたN個のデバイスの最も安い組み合わせを見つけることです入力には、各デバイスが各スロットにインストールするためにどのような費用がかかりますかを示すコストマトリックスがあり、デバイスはまた、交差してはならないワイヤによって互いに接続されています。常にN-1接続があります。 詳細と例は上のリンクにあります。

私の問題は、私の解決策が遅すぎるということです。 サイズ13のドリルヘッドを一般に2秒未満で解決する必要があります。 はあまりに正確：私は1秒未満で解かこの入力を必要とする：

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 

2S未満で この（溶液は262である）：

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である） だから。もし誰かがこれをどうやって考えているのであれば、私は完全に迷っていますか？代わりに、すべてのN ：

Answer 1

プログラムはすべての可能な順列を生成し、その順列が有効かどうかをテストします。テスト自体にネストされたループが含まれます。 Photonが示唆しているように、データ構造を最適化してチェックが効率的になるようにするか、早い段階で検索スペース内の行き詰まりを見つけることができます。

、より効率的なアプローチは、唯一の有効な順列がcreated.Thisになるようにプログラムを設計することであるかもしれない探索空間を減少させ、テストを取り除きます。

あなたは問題記述の例を見ると、wrieネットワークは非循環グラフである：

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

あなたはツール0から始まり、スロット0に入れた場合は、次のステップを配置することですツール2およびその「子孫」、すなわちツール1,7および3とそのそれぞれに接続されたツールとの順列が含まれる。ツール0の観点から、これをツリーにすることができます：

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

ここで、葉はただ1つのツールに対応しています。支店にはいくつかのツールがあります。支店のすべての切取りは、有効な手配を形成する。もちろん

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

、[56]のすべての順列は、他のブランチの全ての順列と組み合わせなければなりません。あなたは、各宇宙で0から9までの数字を通らない種類のオドメーターを実装することによって達成することができますが、枝の可能な順列を通して。

生成されたすべての順列は有効ですが、この手法ではすべての順列がまだ作成されていません。スロット0には工具0が固定されていますが、そうである必要はありません。しかし、有効なレイアウトのトポグラフィを使用して、それを回転させてツール0をスロット1,2に配置するなどして、8つのレイアウトを生成することができます。

この手法では、検索スペースを9から減らすことができます。 〜9＆middot; 4！ ＆middot; 2！ ＆middot; 3！ ＆middot; 2！または70倍になります。テストはありませんが、より複雑なデータ構造を犠牲にしています。

（還元が分岐せずに、ワイヤのネットワークはIR本当にただ一直線あなたの12のツールの例に極端である。）

このコードが記載された技術を実装：

#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

さてあなただけのアイデアを求めました！順列、あなたは確かにワイヤーを交差させる順列を無視するバックトラックを使用する必要があります。

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); 

}