跳转至

分支限界算法

概述

分支限界法（Branch and Bound）是一种在问题的解空间树上搜索问题解的方法，通过限界函数剪枝，减少搜索空间，提高求解效率。

核心思想

分支限界法与回溯法类似，但采用广度优先或最佳优先的搜索策略，使用限界函数估计剩余代价，优先扩展最有希望的节点。

分支限界法特点

  • 搜索策略：广度优先或最佳优先
  • 剪枝依据：限界函数
  • 适用问题：组合优化问题
  • 空间需求：需要存储活跃节点

分支限界与回溯对比

特性 回溯法 分支限界法
搜索方式 深度优先 广度/最佳优先
存储方式 递归栈 队列/优先队列
剪枝方式 约束函数 限界函数
适用目标 所有解/任一解 最优解
空间复杂度 较低 较高

0-1背包问题

问题定义

给定n个物品，每个物品有重量w[i]和价值v[i]，背包容量为W，求装入背包的物品最大价值。

分支限界实现

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
 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
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
#define MAX_N 100

typedef struct {
    int level;
    int profit;
    int weight;
    float bound;
} Node;

typedef struct {
    int weight[MAX_N];
    int value[MAX_N];
    int n;
    int capacity;
    float ratio[MAX_N];
} Knapsack;

void sortByRatio(Knapsack *kp) {
    for (int i = 0; i < kp->n; i++) {
        kp->ratio[i] = (float)kp->value[i] / kp->weight[i];
    }
    
    for (int i = 0; i < kp->n - 1; i++) {
        for (int j = 0; j < kp->n - i - 1; j++) {
            if (kp->ratio[j] < kp->ratio[j + 1]) {
                float tempR = kp->ratio[j];
                kp->ratio[j] = kp->ratio[j + 1];
                kp->ratio[j + 1] = tempR;
                
                int tempW = kp->weight[j];
                kp->weight[j] = kp->weight[j + 1];
                kp->weight[j + 1] = tempW;
                
                int tempV = kp->value[j];
                kp->value[j] = kp->value[j + 1];
                kp->value[j + 1] = tempV;
            }
        }
    }
}

float bound(Knapsack *kp, Node u) {
    if (u.weight >= kp->capacity) {
        return 0;
    }
    
    float profitBound = u.profit;
    int j = u.level + 1;
    int totalWeight = u.weight;
    
    while (j < kp->n && totalWeight + kp->weight[j] <= kp->capacity) {
        totalWeight += kp->weight[j];
        profitBound += kp->value[j];
        j++;
    }
    
    if (j < kp->n) {
        profitBound += (kp->capacity - totalWeight) * kp->ratio[j];
    }
    
    return profitBound;
}

int knapsackBranchBound(Knapsack *kp) {
    sortByRatio(kp);
    
    Node queue[MAX_N * MAX_N];
    int front = 0, rear = 0;
    
    Node u, v;
    u.level = -1;
    u.profit = 0;
    u.weight = 0;
    u.bound = bound(kp, u);
    
    queue[rear++] = u;
    int maxProfit = 0;
    
    while (front < rear) {
        u = queue[front++];
        
        if (u.bound > maxProfit) {
            v.level = u.level + 1;
            
            v.weight = u.weight + kp->weight[v.level];
            v.profit = u.profit + kp->value[v.level];
            
            if (v.weight <= kp->capacity && v.profit > maxProfit) {
                maxProfit = v.profit;
            }
            
            v.bound = bound(kp, v);
            
            if (v.bound > maxProfit) {
                queue[rear++] = v;
            }
            
            v.weight = u.weight;
            v.profit = u.profit;
            v.bound = bound(kp, v);
            
            if (v.bound > maxProfit) {
                queue[rear++] = v;
            }
        }
    }
    
    return maxProfit;
}

优先队列实现

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
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
91
92
93
94
95
96
97
#define MAX_QUEUE 10000

typedef struct {
    Node data[MAX_QUEUE];
    int size;
} PriorityQueue;

void initPQ(PriorityQueue *pq) {
    pq->size = 0;
}

void swapNode(Node *a, Node *b) {
    Node temp = *a;
    *a = *b;
    *b = temp;
}

void push(PriorityQueue *pq, Node node) {
    int i = pq->size++;
    pq->data[i] = node;
    
    while (i > 0 && pq->data[(i - 1) / 2].bound < pq->data[i].bound) {
        swapNode(&pq->data[i], &pq->data[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

Node pop(PriorityQueue *pq) {
    Node result = pq->data[0];
    pq->data[0] = pq->data[--pq->size];
    
    int i = 0;
    while (2 * i + 1 < pq->size) {
        int larger = 2 * i + 1;
        if (larger + 1 < pq->size && 
            pq->data[larger + 1].bound > pq->data[larger].bound) {
            larger++;
        }
        
        if (pq->data[i].bound >= pq->data[larger].bound) break;
        
        swapNode(&pq->data[i], &pq->data[larger]);
        i = larger;
    }
    
    return result;
}

int isEmpty(PriorityQueue *pq) {
    return pq->size == 0;
}

int knapsackPQ(Knapsack *kp) {
    sortByRatio(kp);
    
    PriorityQueue pq;
    initPQ(&pq);
    
    Node u, v;
    u.level = -1;
    u.profit = 0;
    u.weight = 0;
    u.bound = bound(kp, u);
    
    push(&pq, u);
    int maxProfit = 0;
    
    while (!isEmpty(&pq)) {
        u = pop(&pq);
        
        if (u.bound > maxProfit) {
            v.level = u.level + 1;
            
            v.weight = u.weight + kp->weight[v.level];
            v.profit = u.profit + kp->value[v.level];
            
            if (v.weight <= kp->capacity && v.profit > maxProfit) {
                maxProfit = v.profit;
            }
            
            v.bound = bound(kp, v);
            if (v.bound > maxProfit) {
                push(&pq, v);
            }
            
            v.weight = u.weight;
            v.profit = u.profit;
            v.bound = bound(kp, v);
            
            if (v.bound > maxProfit) {
                push(&pq, v);
            }
        }
    }
    
    return maxProfit;
}

旅行商问题（TSP）

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
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
91
92
93
94
95
#define MAX_CITIES 20
#define INF 1000000

typedef struct {
    int city;
    int cost;
    int path[MAX_CITIES];
    int pathLen;
    int visited[MAX_CITIES];
} TSPNode;

int dist[MAX_CITIES][MAX_CITIES];
int n;

int tspBound(TSPNode *node) {
    int bound = node->cost;
    
    for (int i = 0; i < n; i++) {
        if (!node->visited[i]) {
            int minDist = INF;
            for (int j = 0; j < n; j++) {
                if (i != j && dist[i][j] < minDist) {
                    minDist = dist[i][j];
                }
            }
            bound += minDist;
        }
    }
    
    return bound;
}

int tspBranchBound() {
    PriorityQueue pq;
    initPQ(&pq);
    
    TSPNode start;
    start.city = 0;
    start.cost = 0;
    start.pathLen = 1;
    start.path[0] = 0;
    for (int i = 0; i < n; i++) {
        start.visited[i] = 0;
    }
    start.visited[0] = 1;
    
    push(&pq, *(Node*)&start);
    
    int minCost = INF;
    int bestPath[MAX_CITIES];
    
    while (!isEmpty(&pq)) {
        Node nodeData = pop(&pq);
        TSPNode *curr = (TSPNode*)&nodeData;
        
        if (curr->cost >= minCost) continue;
        
        if (curr->pathLen == n) {
            int totalCost = curr->cost + dist[curr->city][0];
            if (totalCost < minCost) {
                minCost = totalCost;
                for (int i = 0; i < n; i++) {
                    bestPath[i] = curr->path[i];
                }
            }
            continue;
        }
        
        for (int next = 0; next < n; next++) {
            if (!curr->visited[next]) {
                TSPNode child;
                child.city = next;
                child.cost = curr->cost + dist[curr->city][next];
                child.pathLen = curr->pathLen + 1;
                
                for (int i = 0; i < curr->pathLen; i++) {
                    child.path[i] = curr->path[i];
                }
                child.path[curr->pathLen] = next;
                
                for (int i = 0; i < n; i++) {
                    child.visited[i] = curr->visited[i];
                }
                child.visited[next] = 1;
                
                int bound = tspBound(&child);
                if (bound < minCost) {
                    push(&pq, *(Node*)&child);
                }
            }
        }
    }
    
    return minCost;
}

最大团问题

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
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
typedef struct {
    int adj[MAX_N][MAX_N];
    int n;
} CliqueGraph;

typedef struct {
    int level;
    int size;
    int candidate[MAX_N];
} CliqueNode;

int cliqueBound(CliqueGraph *g, CliqueNode *node, int *bestSize) {
    int remaining = g->n - node->level;
    return node->size + remaining;
}

int isClique(CliqueGraph *g, int *clique, int size, int v) {
    for (int i = 0; i < size; i++) {
        if (!g->adj[clique[i]][v]) {
            return 0;
        }
    }
    return 1;
}

int maxClique(CliqueGraph *g) {
    int bestSize = 0;
    int bestClique[MAX_N];
    
    CliqueNode queue[MAX_N * MAX_N];
    int front = 0, rear = 0;
    
    CliqueNode start;
    start.level = 0;
    start.size = 0;
    queue[rear++] = start;
    
    while (front < rear) {
        CliqueNode curr = queue[front++];
        
        if (curr.level == g->n) {
            if (curr.size > bestSize) {
                bestSize = curr.size;
                for (int i = 0; i < curr.size; i++) {
                    bestClique[i] = curr.candidate[i];
                }
            }
            continue;
        }
        
        CliqueNode child = curr;
        child.level++;
        
        if (isClique(g, curr.candidate, curr.size, curr.level)) {
            child.candidate[child.size] = curr.level;
            child.size++;
            
            if (cliqueBound(g, &child, &bestSize) > bestSize) {
                queue[rear++] = child;
            }
        }
        
        child.size = curr.size;
        if (cliqueBound(g, &child, &bestSize) > bestSize) {
            queue[rear++] = child;
        }
    }
    
    return bestSize;
}

C++ 实现（0-1背包）

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
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
91
92
93
94
95
class Knapsack {
private:
    struct Node {
        int level;
        int profit;
        int weight;
        double bound;
        
        bool operator<(const Node& other) const {
            return bound < other.bound;
        }
    };
    
    vector<int> weight, value;
    int capacity, n;
    
    double bound(const Node& u) const {
        if (u.weight >= capacity) return 0;
        
        double profitBound = u.profit;
        int j = u.level + 1;
        int totalWeight = u.weight;
        
        while (j < n && totalWeight + weight[j] <= capacity) {
            totalWeight += weight[j];
            profitBound += value[j];
            j++;
        }
        
        if (j < n) {
            profitBound += (capacity - totalWeight) * 
                          (double)value[j] / weight[j];
        }
        
        return profitBound;
    }
    
public:
    Knapsack(const vector<int>& w, const vector<int>& v, int c)
        : weight(w), value(v), capacity(c), n(w.size()) {}
    
    int solve() {
        vector<pair<double, int>> order(n);
        for (int i = 0; i < n; i++) {
            order[i] = {(double)value[i] / weight[i], i};
        }
        sort(order.rbegin(), order.rend());
        
        vector<int> sortedW(n), sortedV(n);
        for (int i = 0; i < n; i++) {
            sortedW[i] = weight[order[i].second];
            sortedV[i] = value[order[i].second];
        }
        weight = sortedW;
        value = sortedV;
        
        priority_queue<Node> pq;
        Node u = {-1, 0, 0, 0};
        u.bound = bound(u);
        pq.push(u);
        
        int maxProfit = 0;
        
        while (!pq.empty()) {
            u = pq.top();
            pq.pop();
            
            if (u.bound > maxProfit) {
                Node v = {u.level + 1, 0, 0, 0};
                
                v.weight = u.weight + weight[v.level];
                v.profit = u.profit + value[v.level];
                
                if (v.weight <= capacity && v.profit > maxProfit) {
                    maxProfit = v.profit;
                }
                
                v.bound = bound(v);
                if (v.bound > maxProfit) {
                    pq.push(v);
                }
                
                v.weight = u.weight;
                v.profit = u.profit;
                v.bound = bound(v);
                
                if (v.bound > maxProfit) {
                    pq.push(v);
                }
            }
        }
        
        return maxProfit;
    }
};

时间复杂度分析

问题 最坏复杂度 平均复杂度 空间复杂度
0-1背包 O(2ⁿ) 远小于最坏 O(2ⁿ)
TSP O(n!) 远小于最坏 O(n!)
最大团 O(2ⁿ) 远小于最坏 O(2ⁿ)

效率说明

  • 分支限界法最坏复杂度与穷举相同
  • 但通过剪枝，实际效率通常远优于最坏情况
  • 限界函数的质量决定剪枝效率

限界函数设计原则

  1. 有效性：下界 ≤ 最优解 ≤ 上界
  2. 紧致性：界越紧，剪枝越多
  3. 可计算性：计算代价不能太高
  4. 单调性：子节点的界不优于父节点

应用场景

  1. 组合优化：背包、指派、选址
  2. 路径规划：旅行商、最短路径
  3. 图论问题：最大团、图着色
  4. 调度问题：作业调度、资源分配

优缺点

优点

  1. 可求最优解：保证找到全局最优
  2. 剪枝效率高：大幅减少搜索空间
  3. 可中断求解：可获得当前最优解

缺点

  1. 最坏复杂度高：指数级
  2. 空间消耗大：存储活跃节点
  3. 限界函数难设计：需要问题特定知识

参考资料