有效回溯算法

Question

我有这样的代码：

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

long result = LONG_MAX;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int hasConnection(int *array, int arrayIndex, int maxBound, int *rules, int size) {
    int connection;
    for (int i = 0; i < (size - 1)*2; i++) {
        if (rules[i] == array[arrayIndex]) {
            if (i % 2) {
                connection = rules[i - 1];
            } else {
                connection = rules[i + 1];
            }
            for (int j = maxBound - 1; j >= 0; j--) {
                if (array[j] == connection) {
                    return 1;
                }
            }
        }
    }
    return 0;
}

int isCrossed(int *array, int outConnectionIndex, int inConnectionIndex, int *rules, int size) {
    for (int i = inConnectionIndex + 1; i < outConnectionIndex; i++) {//sweep trough indexes in between
        if (hasConnection(array, i, inConnectionIndex, rules, size)) {//array[i] has connection with index lower than inConnectionIndex
            return 1;
        }
    }
    return 0;
}

int isWiredInsideAndCrossed(int *array, int arrayIndex, int *rules, int size) {
    int connection;
    for (int i = 0; i < 2 * (size - 1); i++) {
        if (rules[i] == array[arrayIndex]) {
            if (i % 2) {
                connection = rules[i - 1];
            } else {
                connection = rules[i + 1];
            }
            for (int j = 1; j < arrayIndex - 1; j++) {
                if (array[j] == connection) {
                    if (isCrossed(array, arrayIndex, j, rules, size)) {
                        return 1;
                    }
                }
            }
        }
    }
    return 0;
}

void trySequence(int * array, int size, int *priceMap, int *rules) {
    int ret = 0;
    for (int i = 0; i < size; i++) {
        ret = ret + priceMap[i * size + array[i]];
        if (ret >= result || isWiredInsideAndCrossed(array, i, rules, size)) {
            return;
        }
    }
    result = ret;
}

void permute(int *array, int i, int size, int *priceMap, int *rules) {
    if (size == i) {
        trySequence(array, size, priceMap, rules);
        return;
    }
    int j = i;
    for (j = i; j < size; j++) {
        swap(array + i, array + j);
        permute(array, i + 1, size, priceMap, rules);
        swap(array + i, array + j);
    }
    return;
}

int main(int argc, char** argv) {    
    int size;
    fscanf(stdin, "%d", &size);
    int *priceMap = malloc(sizeof (int)*size * size);
    int *rules = malloc(sizeof (int)*(size - 1)*2);
    int i = 0;
    int squaredSize = size*size;
    while (i < squaredSize) {
        scanf("%d", priceMap + i);
        i++;
    }
    i = 0;
    int rulesSize = (size - 1)*2;
    while (i < rulesSize) {
        scanf("%d", rules + i);
        i++;
    }
    int arrayToPermute [size];
    for (int j = 0; j < size; j++) {
        arrayToPermute[j] = j;
    }
    permute(arrayToPermute, 0, size, priceMap, rules);
    printf("%ld\n", result);
    return (EXIT_SUCCESS);
}

它应该做这

编辑:基本任务是找出放置在圆周边缘N个槽中的N个设备的最便宜的组合，在输入上有一个成本矩阵，它告诉每个设备在每个插槽中安装所需的费用，设备之间也通过不能交叉的电线连接。总是有N-1连接。详细信息和例子都在上面的链接上。

我的问题是我的解决方案太慢了。我需要它来解决一个13大小的钻头，一般在两秒钟之内。太精确了:我需要在不到1s内解决这个输入：

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)，在少于2秒的时间内：

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建议的那样。

一个更有效的方法可能是设计程序，使只有有效的排列是created.This，减少了搜索空间，也摆脱了测试。

如果您查看问题描述中的示例，wrie网络是一个无循环图：

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

如果从tool 0开始，并将其放入槽0中，下一步是放置tool 2及其“后代”的排列，即工具1、7和3及其各自连接的工具。从tool 0的角度来看，您可以将其转换为树：

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

在这里，叶子只对应一个工具。这些分支有几个工具。所有的分支机构都形成了有效的安排。

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

当然，[56]的每一个置换都必须与其他分支的每一个置换结合起来。您可以通过实现一种不通过每个空间中从0到9的数字，而是通过分支的可能排列来实现这一点。

每个生成的置换都是有效的，但是这种技术还没有创建所有可能的排列。请记住，我们已经将工具0固定在槽0中，但不必是这样。但是，有效布局的地形可以通过旋转它和将工具0放置在插槽1、2等方式来生成8种其他布局。

这种技术减少了你的搜索空间，从9！到9·4·2·3·2！或者是70倍。没有测试，但代价是更复杂的数据结构。

(在你的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

好吧，你只是问了一个主意:而不是所有的n！排列，你必须使用回溯来忽略那些肯定会使导线交叉的排列。

也就是说你有置换1，2，3，4.11，和12 3部分已经使导线交叉，所以你可以忽略所有的排列为4.第11部分

下面是一些用于实现细节的伪代码：

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

}