c - 有效的回溯算法

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

它应该做 this

编辑:基本上，任务是找到放置在圆圈边缘的 N 个插槽中的 N 台设备的最便宜组合，在输入端有一个成本矩阵，告诉您在每个插槽中安装每个设备的成本，设备也通过不得交叉的电线相互连接。总有 N-1 个连接。详细信息和示例位于上面的链接中。

我的问题是我的解决方案太慢了。我需要它在不到两秒的时间内解决 13 号钻头的问题。太精确了:我需要在不到 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

(解为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 所建议的那样。

一种更有效的方法可能是设计程序，以便只创建有效的排列。这减少了搜索空间，也摆脱了测试。

如果看问题描述中的例子，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

在这里，叶子只对应一个工具。分支机构有多种工具。分支机构的所有分支均形成有效安排。

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 工具示例中，减少是极端的，其中电线网络实际上只是一条没有 fork 的直线。)

此代码实现了所描述的技术:

#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;
}