算法设计与分析-汇总

  算法还是要学的，不学算法感觉心里空落落的，好像自己不是计算机专业的一样。

1. 递归法

求解n皇后问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int Place(int k, int j)
// 测试位置(k, j)能否摆放皇后
{
    int i;
    for (i = 1; i < k; i++)
        if ((q[i] == j) || (abs(q[i] - j) == abs(k - i)))  // (同一列 || 同一对角线)
            return 0;
    return 1;
}

void Queen(int k, int n)
{
    int j;
    if (k > n)
        dispasolution(n);
    else
        for (j = 1; j <= n; j++)
            if (Place(k, j))
            {
                q[k] = j;
                Queen(k + 1, n);
            }
}

2. 分治法

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int Partition(int a[], int s, int t)
{
    int i = s, j = t;
    int tmp = a[s];
    while (i != j)
    {
        while (j > i && a[j] >= tmp)
            j--;
        a[i] = a[j];
        while (i < j && a[i] <= tmp)
            i++;
        a[j] = a[i];
    }
    a[i] = tmp;
    return i;
}

void QuickSort(int a[], int s, int t)
{
    int i;
    if (s < t)
    {
        i = Partition(a, s, t);
        QuickSort(a, s, i - 1);
        QuickSort(a, i + 1, t);
    }
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
void Merge(int a[], int low, int mid, int high)
// a[low ... mid], a[mid + 1 ... high] -> a[low ... high]
{
    int* tmpa;
    int i = low, j = mid + 1, k = 0;
    tmpa = (int*)malloc((high - low + 1) * sizeof(int));
    while (i <= mid && j <= high)
        if (a[i] <= a[j])
        {
            tmpa[k] = a[i];
            i++;
            k++;
        }
        else
        {
            tmpa[k] = a[j];
            j++;
            k++;
        }
    while (i <= mid)
    {
        tmpa[k] = a[i];
        i++;
        k++;
    }
    while (j <= high)
    {
        tmpa[k] = a[j];
        j++;
        k++;
    }
    for (k = 0, i = low; i <= high; k++, i++)
        a[i] = tmpa[k];
    free(tmpa);
}

void MergePass(int a[], int length, int n)
{
    int i;
    for (i = 0; i + 2 * length - 1 < n; i += 2 * length)
        Merge(a, i, i + length - 1, i + 2 * length - 1);  // 归并长为length的两相邻子表
    if (i + length - 1 < n)
        Merge(a, i, i + length - 1, n - 1);  // 归并余下的两个子表
}

void MergeSort(int a[], int n)
{
    int length;
    for (length = 1; length < n; length = 2 * length)
        MergePass(a, length, n);
}

自顶向下的二路归并算法

1
2
3
4
5
6
7
8
9
10
11
void MergeSort(int a[], int low, int high)
{
    int mid;
    if (low < high)
    {
        mid = (low + high) / 2;
        MergeSort(a, low, mid);
        MergeSort(a, mid + 1, high);
        Merge(a, low, mid, high);
    }
}

折半查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int BinSerch(int a[], int low, int high, int k)
{
    int mid;
    if (low <= high)
    {
        mid = (low + high) / 2;
        if (a[mid] == k)
            return mid;
        if (a[mid] > k)
            return BinSerch(a, low, mid - 1);
        else
            return BinSerch(a, mid + 1, high);
    }
    else
        return -1;
}

寻找一个序列中第k小的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int QuickSelect(int a[], int s, int t, int k)
{
    int i = s, j = t;
    int tmp;
    if (s < t)
    {
        tmp = a[s];
        while (i != j)
        {
            while (j > i && a[j] >= tmp)
                j--;
            a[i] = a[j];
            while (i < j && a[i] <= tmp)
                i++;
            a[j] = a[i];
        }
        a[i] = tmp;
        if (i == k - 1)
            return a[i];
        else if (i > k - 1)
            return QuickSelect(a, s, i - 1, k);
        else
            return QuickSelect(a, i + 1, t, k);
    }
    else if (s == t && s = k - 1)  // 区间内只有一个元素
        return a[k - 1];
}

寻找两个等长有序序列的中位数

  问题求解：

  分别求出$a$、$b$的中位数$a[m_1]$和$b[m_2]$：

  若$a[m_1] = b[m_2]$，则$a[m_1]$或$b[m_2]$即为所求中位数。

  若$a[m_1] < b[m_2]$，则舍弃序列$a$中前半部分（较小的一半），同时舍弃序列$b$中后半部分（较大的一半）要求舍弃的长度相等。

  若$a[m_1] > b[m_2]$，则舍弃序列$a$中后半部分（较大的一半），同时舍弃序列$b$中前半部分（较小的一半），要求舍弃的长度相等。

  在保留的两个升序序列中，重复过程上述过程直到两个序列中只含一个元素时为止，较小者即为所求的中位数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int MidNum(int a[], int s1, int t1, int b[], int s2, int t2)
// 求两个有序序列a[s1 ... t1]和b[s2 ... t2]的中位数
{
    int m1, m2;
    if (s1 == t1 && s2 == t2)  // 两个序列只有一个元素
        return a[s1] < b[s2] ? a[s1] : b[s2];  // 返回较小者
    else
    {
        m1 = (s1 + t1) / 2;
        m2 = (s2 + t2) / 2;
        if (a[m1] == b[m2])
            return a[m1];
        if (a[m1] < b[m2])
        {
            postpart(s1, t1);
            prepart(s2, t2);
            return MidNum(a, s1, t1, b, s2, t2);
        }
        else
        {
            prepart(s1, t1);
            postpart(s2, t2);
            return MidNum(a, s1, t1, b, s2, t2);
        }
    }
}

求解最大连续子序列和问题

  使用分治法。

  问题求解：

  对于含有$n$个整数的序列$a[0 \dots n - 1]$：

  若$n = 1$，表示该序列仅含一个元素，如果该元素大于$0$，则返回该元素；否则返回$0$（一个序列最大连续子序列和至少是$0$，如果该序列的所有元素均为负整数，则最大连续子序列含$0$个元素，其和为$0$）。

  若$n > 1$，采用分治法求解最大连续子序列时，取其中间位置$mid = \lfloor (n - 1) / 2 \rfloor$，该子序列只可能出现三个地方，各种情况及求解方法如下：

  (1) 该子序列完全落在左半部即$a[0 \dots mid]$中。采用递归求出其最大连续子序列和$maxLeftSum$。

  (2) 该子序列完全落在右半部即$a[mid + 1 \dots n - 1]$中。采用递归求出其最大连续子序列和$maxRightSum$。

  (3) 该子序列跨越序列$a$的中部而占据左右两部分。也就是说，这种情况下最大和的连续子序列含有$a[mid]$，则从左半部（含$a[mid]$元素）求出$maxLeftBorderSum = max \sum\limits_{k = i}^{mid}a_k (0 \leqslant i \leqslant mid)$，则从右半部（不含$a[mid]$元素）求出$maxRightBorderSum = max \sum\limits_{k = mid + 1}^{j}a_k (mid + 1 \leqslant j \leqslant n - 1)$，这种情况下的最大连续子序列和$maxMidSum = maxLeftBorderSum + maxRightBorderSum$。

  最后整个序列$a$的最大连续子序列和为$maxLeftSum$，$maxRightSum$和$maxMidSum$三者中的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
long MaxSubSum4(int a[], int left, int right)
{
    int i, j;
    long maxLeftSum, maxRightSum;
    long maxLeftBorderSum, leftBorderSum;
    long maxRightBorderSum, rightBorderSum;
    if (left == right)  // 子序列只有一个元素
    {
        if a[left] > 0
            return a[left];
        else
            return 0;
    }
    int mid = (left + right) / 2;
    maxLeftSum = maxSubSum4(a, left, mid);
    maxRightSum = maxSubSum4(a, mid + 1, right);
    maxLeftBorderSum = 0, leftBorderSum = 0;
    for (i = mid; i >= left; i--)
    {
        leftBorderSum += a[i];
        if (leftBorderSum > maxLeftBorderSum)
            maxLeftBorderSum = leftBorderSum;
    }
    maxRightBorderSum = 0, rightBorderSum = 0;
    for (j = mid + 1; j <= right; j++)
    {
        rightBorderSum += a[i];
        if (rightBorderSum > maxRightBorderSum)
            maxRightBorderSum = rightBorderSum;
    }
    return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
}

求解查找假币问题

  有$n$（$n > 3$）个硬币，其中一个是假币，且假币较轻，采用天平称重方式找到这个假币，并给出操作步骤。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int Solve(int low, int high)
{
    if (low == high)  // 只有一个硬币
        return low;
    if (low == high - 1)  // 只有两个硬币
    {
        if (a[low] < a[high])
            return low;
        else
            return high;
    }
    int mid = (low + high) / 2;
    int sum1, sum2;
    if ((high - low + 1) % 2 == 0)  // 区间内硬币为偶数
    {
        sum1 = Sum(low, mid);
        sum2 = Sum(mid + 1, high);
        printf("...");
    }
    else  // 区间内硬币为奇数
    {
        sum1 = Sum(low, mid - 1);
        sum2 = Sum(mid + 1, high);
        printf("...");
    }
    if (sum1 == sum2)
    {
        printf("...");
        return mid;
    }
    else if (sum1 < sum2)
    {
        printf("...");
        if ((high - low + 1) % 2 == 0)
            return Solve(low, mid);
        else
            return Solve(low, mid - 1);
    }
    else
    {
        printf("...");
        return Solve(mid + 1, high);
    }
}

  如果采用三分法，则不需要考虑区间内硬币为奇数还是偶数。

求解众数问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int num;
int maxcnt = 0;

void Split(int a[], int low, int high, int &mid, int &left, int &right)
// 以a[low ... high]中间的元素为界限，确定为等于a[mid]元素的左、右位置left和right
{
    mid = (low + high) / 2;
    for (left = low; left <= high; left++)
        if (a[left] == a[mid])
            break;
    for (right = left + 1; right <= high; right++)
        if (a[right] != a[mid])
            break;
    right--;
}

void GetMaxCnt(int a[], int low, int high)
{
    if (low <= high)
    {
        int mid, left, right;
        Split(a, low, high. mid, left, right);
        int cnt = right - left + 1;
        if (cnt > maxcnt)
        {
            num = a[mid];
            maxcnt = cnt;
        }
        GetMaxCnt(a, low, left - 1);
        GetMaxCnt(a, right + 1, high);
    }
}

求解逆序数问题

  问题求解：在二路归并排序的合并过程中计算逆序数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int ans;

void Merge(int a[], int low, int mid, int high)
{
    int i = low;
    int j = mid + 1;
    int k = 0;
    int* tmp = (int*)malloc((high - low + 1) * sizeof(int));
    while (i <= mid && j <= high)
    {
        if (a[i] > a[j])
        {
            tmp[k++] = a[j++];
            ans += mid - i + 1;
        }
        else
            tmp[k++] = a[i++];
    }
    while(i <= mid)
        tmp[k++] = a[i++];
    while(j <= high)
        tmp[k++] = a[j++];
    for (int k1 = 0; k1 < k; k1++)
        a[low + k1] = tmp[k1];
    free(tmp);
}

求解半数集问题

  给定一个自然数$n$，由$n$开始可以一次产生半数集$set(n)$中的数如下：

  (1) $n \in set(n)$。

  (2) 在$n$的左边加上一个自然数，但该自然数不能超过最近添加的自然数的一半。

  (3) 按此规则进行处理，直到不能再添加为止。

  例如，$set(6) = \{6, 16, 26, 126, 35, 136\}$，半数集$set(6)$中有$6$个元素。

  问题求解：$f(1) = 1, f(n) = 1 + \sum\limits_{i = 1}^{n / 2}f(i)$。

1
2
3
4
5
6
7
8
int Fset(int n)
{
    int i, ans = 1;
    if (n > 1)
        for (i = 1; i <= n / 2; i++)
            ans += Fset(i);
    return ans;
}

求解一个整数数组划分为两个子数组问题

  已知由$n$（$n \geqslant 2$）个正整数构成的集合$A = \{a_k\}$（$0 \leqslant k < n$），将其划分为两个不相交的子集$A_1$和$A_2$，元素个数分别时$n_1$和$n_2$，$A_1$和$A_2$中的元素之和分别为$S_1$和$S_2$。设计一个尽可能高效的划分算法，满足$|n_1 - n_2|$最小且$|S_1 - S_2|$最大，算法返回$|S_1 - S_2|$的结果。

  问题求解：将$A$中最小的$\lfloor n / 2 \rfloor$个元素放在$A_1$中，其他元素放在$A_2$中。采用递归快速排序思路，查找第$n / 2$小的元素，进行划分，不用将$A$中元素全部排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int Partition(int a[], int low, int high)
{
    int i = low, j = high;
    int povit = a[low];
    while (i < j)
    {
        while (i < j && a[j] >= povit)
            j--;
        a[i] = a[j];
        while (i < j && a[i] <= povit)
            i++;
        a[j] = a[i];
    }
    a[i] = povit;
    return i;
}

int Solve(int a[], int n)
{
    int low = 0, high = n - 1;
    bool flag = true;
    while (flag)
    {
        int i = Partition(a, low, high);
        if (i == n / 2 - 1)
            flag = false;
        else if (i < n / 2 - 1)
            low = i + 1;
        else
            high = i - 1;
    }
    int s1 = 0; s2 = 0;
    for (int i = 0; i < n / 2; i++)
        s1 += a[i];
    for (int i = n / 2; i < n; i++)
        s2 += a[i];
    return s2 - s1;
}

求解满足条件的元素对个数问题

  给定$N$个整数$A_i$以及一个正整数$C$，问其中有多少对$i$、$j$满足$A_i - A_j = C$。

  问题求解：采用二分查找数量。先对数组$a$进行递增排序，用$j$扫描数组$a$，对于元素$a[j]$，在$a[j + 1 \dots n - 1]$中采用二分法求元素$a[j] + c$出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int BinSearch(int low, int high, int x)
{
    int cnt = 0;
    for (int i = low; i <= high; i++)
    {
        if (a[i] == x)
        {
            cnt++;
        }
    }
    return cnt;
}

int main()
{
    scanf_s("%d %d", &n, &c);
    for (int i = 0; i < n; i++)
    {
        scanf_s("%d", &a[i]);
    }
    sort(a, a + n);
    int ans = 0;
    for (int i = 0; i < n - 1; i++)
    {
        ans += BinSearch(i + 1, n - 1, a[i] + c);
    }
    printf("%d\n", ans);
    return 0;
}

3. 蛮力法

4. 回溯法

求解填字游戏问题

  在一个$3 \times 3$个方格的方阵中要填入数字$1 \sim 10$的某$9$个数字，每个方格填一个整数，使所有相邻两个方格内的两个整数之和为素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
bool used[N + 1];  // used[i] = true表示数字i可以使用
int a[9];  // 存放3 x 3方格
int count = 0;
int checkmatrix[][3] = {{-1}, {0, -1}, {1, -1}, {0, -1}, {1, 3, -1}, {2, 4, -1}, {3, -1}, {4, 6, -1}, {5, 7, -1}};

bool Check(int pos)
// 检查a中pos位置的相邻两个方格内的数字之和是否为素数
{
    int i, j;
    if (pos < 0)
        return false;
    for (i = 0; (j = checkmatrix[pos][i]) >= 0; i++)
        if (!isPrime(a[pos] + a[j]))
            return false;
    return true;
}

int Extend(int pos)
// 扩展：为pos位置选择一个没有使用的数字，pos++
{
    a[++pos] = selectnum(1);  // 扩展过程都是从1开始选择数字的
    used[a[pos]] = 0;
    return pos;
}

int Change(int pos)
// 调整：从pos开始回溯
{
    int j;
    // 为pos位置选择另外一个数字，为了避免重复，是从原数字的下一个数字开始选取的
    // 若不能为pos选择一个数字，则回溯，即恢复a[pos]为可以使用的数字，再执行poss--
    while (pos >= 0 && (j = selectnum(a[pos] + 1)) == 0)
        used[a[pos--]] = true;
    if (pos < 0)  // 全部回溯完毕，返回-1结束
        return -1;
    used[a[pos]] = true;  // 为pos位置找到一个没有使用的数字
    a[pos] = j;  // pos位置放置数字j
    used[j] = false;  // 标识数字j已经使用过
    return pos;  // 返回该回溯的新位置
}

int Solve()
{
    bool ok = true;
    int pos = 0;
    a[pos] = 1;
    used[a[pos]] = 0;
    do
    {
        if (ok)
        {
            if (pos == 8)
            {
                dispasolution(a);
                pos = Change(pos);
            }
            else
                pos = Extend(pos);
        }
        else
            pos = Change(pos);
        ok = Check(pos);
    } while (pos >= 0);
}

求解密码问题

  给定一个整数$n$和一个由不同大写字母组成的字符串$str$（长度大于$5$、小于$12$），每一个字母在字母表中对应有一个序数（$A = 1, B = 2, \dots , Z = 26$），从$str$中选择$5$个字母构成密码，例如选取的$5$个字母为$v, w, x, y$和$z$，它们要满足$v的序数 - (w的序数)^2 + (x的序数)^3 - (y的序数)^4 + (z的序数)^5 = n$。这样的解可以有多个，最终结果是按字典序最大的那个。

  问题求解：求$str$的所有排列，找出前5个字母满足指定要求的排列，需要先对$str$进行递减排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int fn(char a, int n)
// 求大写字母的n次方
{
    if (n == 1)
        return a - 'A' + 1;
    return (a - 'A' + 1) * Fn(a, n - 1);
}

void dfs(int i)
{
    if (i == 5)
    {
        if (fn(x[0], 1) - fn(x[1], 2) + fn(x[2], 3) - fn(x[3], 4) + fn(x[4], 5) == n)
        {
            flag = true;
            printf("...");
        }
        return;
    }
    if (flag)
        return;
    for (int j = i; j < m; j++)
    {
        swap(str[i], str[j]);
        x[i] = str[i];
        dfs(i + 1);
        swap(str[i], str[j]);
    }
}

int main()
{
    while (true)
    {
        ...;
        sort(str, str + m, greater<char>());  // 按字典序递减排序
        ...;
    }
    return 0;
}

求解幸运袋子问题

  一个袋子里面有$n$个球，每个球上都有一个号码（拥有相同号码的球是无区别的）。对于一个袋子，当且仅当所有球的号码的和大于所有球的号码的积时是幸运的。可以适当从袋子里移除一些球（可以移除$0$个，但是不要移除完），要使移除后的袋子是幸运的。现编程计算可以获得多少种不同的幸运袋子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void init()
{
    int t;
    m = 0;  // 不同号码球的个数
    memset(times, 0, sizeof(times));  // times[i]表示元素i出现的次数
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &t);
        if (times[t] == 0)
            a[++m] = t;
        times[t]++;
    }
}

void dfs(int i, int sum, int mult)
{
    if (i > m)
        return;
    dfs(i + 1, sum, mult);
    for (int j = 1; j <= times[a[i]]; j++)
    {
        sum += a[i];
        mult *= a[i];
        if (i != 1 && mult >= sum)
            break;
        if (sum > mult)
            ans++;
        dfs(i + 1, sum, mult);
    }
}

5. 分支限界法

求解0/1背包问题

  问题求解：

  采用队列式分枝界限法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
struct NodeType
{
    int no;  // 节点编号
    int i;  // 当前节点在搜索空间中的层次
    int w;
    int v;
    int x[MAXN];  // 当前节点包含的解向量
    double ub;  // 上界
};

void bound(NodeType &e)
// 计算分枝节点e的上界
{
    int i = e.i + 1;
    int sumw = e.w;
    double sumv = e.v;
    while ((sumw + w[i] <= W) && i <= n)
    {
        sumw += w[i];
        sumv += v[i];
        i++;
    }
    if (i <= n)
        e.ub = sumv + (W - sumw) * v[i] / w[i];
    else
        e.ub = sumv;
}

void EnQueue(NodeType e, queue<NodeType> &qu)
{
    if (e.i == n)  // 到达叶子节点
    {
        if (e.v > maxv)
        {
            maxv = e.v;
            for (int j = 1; j <= n; j++)
                bestx[j] = e.x[j];
        }
    }
    else
        qu.push(e);
}

void bfs()
{
    int j;
    NodeType e, e1, e2;
    queue<NodeType> qu;
    
    // 根节点初始化
    e.i = 0;
    e.w = 0;
    e.v = 0;
    e.no = total++;
    for (j = 1; j <= n; j++)
        e.x[j] = 0;
    bound(e);
    qu.push(e);
    
    while (!qu.empty())
    {
        e = qu.front();
        qu.pop();
        if (e.w + w[e.i + 1] <= W)
        {
            e1.no = total++;
            e1.i = e.i++;
            e1.w = e.w + w[e1.i];
            e1.v = e.v + v[e1.i];
            for (j = 1; j <= n; j++)
                e1.x[j] = e.x[j];
            e1.x[e1.i] = 1;
            bound(e1);
            EnQueue(e1, qu);
        }
        e2.no = total++;
        e2.i = e.i++;
        e2.w = e.w;
        e2.v = e.v;
        for (j = 1; j <= n; j++)
            e2.x[j] = e.x[j];
        e2.x[e2.i] = 0;
        bound(e2);
        if (e2.ub > maxv)
            EnQueue(e2, qu);
    }
}

  采用优先队列式分枝界限法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
struct NodeType
{
    int no;  // 节点编号
    int i;  // 当前节点在搜索空间中的层次
    int w;
    int v;
    int x[MAXN];  // 当前节点包含的解向量
    double ub;  // 上界
    bool operator < (const NodeType &s) const
    {
        return row < s.row;
    }
};

void bound(NodeType &e)
// 计算分枝节点e的上界
{
    int i = e.i + 1;
    int sumw = e.w;
    double sumv = e.v;
    while ((sumw + w[i] <= W) && i <= n)
    {
        sumw += w[i];
        sumv += v[i];
        i++;
    }
    if (i <= n)
        e.ub = sumv + (W - sumw) * v[i] / w[i];
    else
        e.ub = sumv;
}

void EnQueue(NodeType e, queue<NodeType> &qu)
{
    if (e.i == n)  // 到达叶子节点
    {
        if (e.v > maxv)
        {
            maxv = e.v;
            for (int j = 1; j <= n; j++)
                bestx[j] = e.x[j];
        }
    }
    else
        qu.push(e);
}

void bfs()
{
    int j;
    NodeType e, e1, e2;
    priority_queue<NodeType> qu;
    
    e.i = 0;  // 根节点初始化
    e.w = 0;
    e.v = 0;
    e.no = total++;
    for (j = 1; j <= n; j++)
        e.x[j] = 0;
    bound(e);
    qu.push(e);
    
    while (!qu.empty())
    {
        e = qu.top();
        qu.pop();
        if (e.w + w[e.i + 1] <= W)
        {
            e1.no = total++;
            e1.i = e.i++;
            e1.w = e.w + w[e1.i];
            e1.v = e.v + v[e1.i];
            for (j = 1; j <= n; j++)
                e1.x[j] = e.x[j];
            e1.x[e1.i] = 1;
            bound(e1);
            EnQueue(e1, qu);
        }
        e2.no = total++;
        e2.i = e.i++;
        e2.w = e.w;
        e2.v = e.v;
        for (j = 1; j <= n; j++)
            e2.x[j] = e.x[j];
        e2.x[e2.i] = 0;
        bound(e2);
        if (e2.ub > maxv)
            EnQueue(e2, qu);
    }
}

求解图的单源最短路径

  给定一个带权有向图$G = (V, E)$，其中每条边的权是一个正整数。另外，还给定$V$中的一个顶点$v$，称为源点。计算从源点到其他所有顶点的最短路径长度。这里的长度是指路上各边权之和。

  问题求解：

  采用队列式分枝界限法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int n;  // 图顶点个数
int a[MAXN][MAXN];  // 图的邻接矩阵
int v;  // 源点

int dist[MAXN];  // dist[i]表示源点到顶点i的最短路径长度
int prev[MAXN];  // prev[i]表示源点到顶点j的最短路径中顶点j的前驱节点

struct NodeType
{
    int vno;  // 顶点编号
    int length;  // 路径长度
};

void bfs(int v)
{
    NodeType e, e1;
    queue<NodeType> pqu;
    e.vno = v;
    e.length = 0;
    pqu.push(e);
    dist[v] = 0;
    while (!pqu.empty())
    {
        e = pqu.front();
        pqu.pop();
        for (int j = 0; j < n; j++)
        {
            if (a[e.vno][j] < INF && e.length + a[e.vno][j] < dist[j])
            {
                dist[j] = e.length + a[e.vno][j];
                prev[j] = e.vno;
                e1.vno = j;
                e1.length = dist[j];
                pqu.push(e1);
            }
        }
    }
}

  采用优先队列式分枝界限法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct NodeType
{
    int vno;  // 顶点编号
    int length;  // 路径长度
    bool operator < (const NodeType &node) const
    {
        return length > node.length;  // length越小越优先出队
    }
};

void bfs(int v)
{
    NodeType e, e1;
    priority_queue<NodeType> pqu;
    e.vno = v;
    e.length = 0;
    pqu.push(e);
    dist[v] = 0;
    while (!pqu.empty())
    {
        e = pqu.top();
        pqu.pop();
        for (int j = 0; j < n; j++)
        {
            if (a[e.vno][j] < INF && e.length + a[e.vno][j] < dist[j])
            {
                dist[j] = e.length + a[e.vno][j];
                prev[j] = e.vno;
                e1.vno = j;
                e1.length = dist[j];
                pqu.push(e1);
            }
        }
    }
}

求解任务分配问题

  有$n$（$n \geqslant 1$）个任务需要分配给$n$个人执行，每个任务只能分配给一个人，每个人只能执行一个任务。第$i$个人执行第$j$个任务的成本是$c[i][j]$（$1 \leqslant i, j \leqslant n$），求出总成本最小的分配方案。

  问题求解：这里采用优先队列式分枝限界法求解。

  任务和人员的编号均为$1 \sim n$，解空间每一层对应一个人员的分配。

  根结点对应人员$0$（虚结点），依次为人员$1, 2, \dots , n$分配任务，叶子结点对应人员$n$。

  解向量为$x : x[i]$表示人员$i$分配任务编号，初始时所有元素值为$0$，表示没有分配。

  临时标识数组$worker : worker[i] = true$表示任务$i$已经分配，初始时所有元素值为$false$，表示没有分配。

  用$bestx[MAXN]$存放最优分配方案，$mincost$（初始值为$\infin$）存放最优成本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
struct NodeType
{
    int no;  // 节点编号
    int i;  // 人员编号
    int x[MAXN];  // x[i]为人员i分配的任务编号
    bool worker[MAXN];  // worker[i] = true表示任务i已经分配
    int cost;  // 已经分配任务所需要的成本
    int lb;  // 下界
    bool operator < (const NodeType &s) const
    {
        return lb > s.lb;
    }
}

void bound(NodeType &e)
{
    int minsum = 0;
    for (int i1 = e.i + 1; i1 <= n; i1++)
    {
        int minc = INF;
        for (int j1 = 1; j1 <= n; j1++)
            if (e.worker[j1] == false && c[i1][j1] < minc)
                minc = c[i1][j1];
            minsum += minc;
    }
    e.lb = e.cost + minsum;
}

void bfs()
{
    int j;
    NodeType e, e1;
    priority_queue<NodeType> qu;
    memset(e.x, 0, sizeof(e.x));
    memset(e.worker, 0, sizeof(e.worker));
    
    e.i = 0;
    e.cost = 0;
    bound(e);
    e.no = total++;
    qu.push(e);
    
    while (!qu.empty())
    {
        e = qu.top();
        qu.pop();
        if (e.i == n)
        {
            if (e.cost < mincost)
            {
                mincost = e.cost;
                for (j = 1; j <= n; j++)
                    bestx[j] = e.x[j];
            }
        }
        e1.i = e.i + 1;
        for (j = 1; j <= n; j++)
        {
            if (e.worker[j])
                continue;
            for (int i1 = 1; i1 <= n; i1++)
                e1.x[i1] = e.x[i1];
            e1.x[e1.i] = j;
            for (int i2 = 1; i2 <= n; i2++)
                e1.worker[i2] = e.worker[i2];
            e1.worker[j] = true;
            e1.cost = e.cost + c[e1.i][j];
            bound(e1);
            e1.no = total++;
            if (e1.lb <= mincost)
                qu.push(e1);
        }
    }
}

求解流水作业调度问题

  有$n$个作业（编号为$1 \sim n$）要在由两台机器$M_1$和$M_2$组成的流水线上完成加工。每个作业加工的顺序都是先在$M_1$上加工，然后在$M_2$上加工。$M_1$和$M_2$加工作业$i$所需的时间分别为$a_i$和$b_i$（$1 \leqslant i \leqslant n$）。流水作业调度问题要求确定这$n$个作业的最优加工顺序，使得从第一个作业在机器$M_1$上开始加工，到最后一个作业在机器$M_2$上加工完成所需的时间最少。可以假定任何作业一旦开始加工，就不允许被中断，直到该作业被完成，即非优先调度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
struct NodeType
{
    int no;  // 节点编号
    int x[MAX];  // x[i]表示第i步分配的作业编号
    int y[MAX];  // y[i] = 1表示编号为i的作业已经分配
    int i;  // 步骤编号
    int f1;  // 已经分配作业M1的执行时间
    int f2;  // 已经分配作业M2的执行时间
    int lb;  // 下界
    bool operator < (const NodeType &s) const
    {
        return lb > s.lb;  // lb越小越优先出队
    }
};

void bound(NodeType &e)
{
    int sum = 0;
    for (int i = 1; i <= n; i++)
        if (e.y[i] == 0)
            sum += b[i];
    e.lb = e.f2 + sum;
}

void bfs()
{
    NodeType e, e1;
    priority_queue<NodeType> qu;
    memset(e.x, 0, sizeof(e.x));
    memset(e.y, 0, sizeof(e.y));
    e.i = 0;
    e.f1 = 0;
    e.f2 = 0;
    bound(e);
    e.no = total++;
    qu.push(e);
    
    while (!qu.empty())
    {
        e = qu.top();
        qu.pop();
        if (e.i == n)
        {
            if (e.f2 < bestf)
            {
                bestf = e.f2;
                for (int j1 = 1; j1 <= n; j1++)
                    bestx[j1] = e.x[j1];
            }
        }
        e1.i = e.i + 1;
        
        for (int j = 1; j <= n; j++)
        {
            if (e.y[j] == 1)
                continue;
            for (int i1 = 1; i1 <= n; i1++)
                e1.x[i1] = e.x[i1];
            for (int i2 = 1; i2 <= n; i2++)
                e1.y[i2] = e.y[i2];
            e1.x[e1.i] = j;
            e1.y[j] = 1;
            e1.f1 = e.f1 + a[j];
            e1.f2 = max(e.f2, e1.f1) + b[j];
            bound(e1);
            if (e1.lb < bestf)
            {
                e1.no = total++;
                qu.push(e1);
            }
        }
    }
}

求解4皇后问题

  问题求解：

  采用队列式分枝界限法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int n = 4;
int count = 1; // 累计队列中节点个数，全局变量

struct NodeType
{
    int no;
    int row;
    vector<int> cols;
};

void Solve()
{
    int i, j;
    NodeType e, e1;
    queue<NodeType> qu;
    e.no = count++;  // 建立根节点
    e.row = -1;  // 行号初始化为-1
    qu.push(e);
    printf("进队：");
    dispnode(e);
    while (!qu.empty())
    {
        e = qu.front();
        qu.pop();
        printf("出队：");
        dispnode(e);
        if (e.row == n - 1)
        {
            printf("产生一个解：");
            for (i = 0; i < n; i++)
                printf("...");
            return;
        }
        else
        {
            for (j = 0; j < n; j++)
            {
                i = e.row + 1;
                if (Valid(e.cols, i, j))
                {
                    e1.no = count++;
                    e1.row = i;
                    e1.cols = e.cols;
                    e1.cols.push_back(j);
                    qu.push(e1);
                    printf("进队子节点：");
                    dispnode(e1);
                }
            }
        }
    }
}

  采用优先队列式分枝界限法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
int n = 4;
int count = 1; // 累计队列中节点个数，全局变量

struct NodeType
{
    int no;
    int row;
    vector<int> cols;
    bool operator < (const NodeType &s) const
    {
        return row < s.row;
    }
};

void Solve()
{
    int i, j;
    NodeType e, e1;
    queue<NodeType> qu;
    e.no = count++;  // 建立根节点
    e.row = -1;  // 行号初始化为-1
    qu.push(e);
    printf("进队：");
    dispnode(e);
    while (!qu.empty())
    {
        e = qu.top();
        qu.pop();
        printf("出队：");
        dispnode(e);
        if (e.row == n - 1)
        {
            printf("产生一个解：");
            for (i = 0; i < n; i++)
                printf("...");
            return;
        }
        else
        {
            for (j = 0; j < n; j++)
            {
                i = e.row + 1;
                if (Valid(e.cols, i, j))
                {
                    e1.no = count++;
                    e1.row = i;
                    e1.cols = e.cols;
                    e1.cols.push_back(j);
                    qu.push(e1);
                    printf("进队子节点：");
                    dispnode(e1);
                }
            }
        }
    }
}

6. 贪心法