分支限界算法详解及经典例题 c++

分支限界算法是一种用于解决组合优化问题的常用算法。它通过不断搜索问题空间，并实时地剪枝，从而达到提高搜索效率的目的。该算法在解决旅行商问题、装箱问题、背包问题等方面具有广泛的应用。

分支限界算法的核心思想是将问题空间划分为多个子空间，并在每个子空间中寻找问题的最优解。在搜索的过程中，通过设定界限条件，及时地淘汰一些不可能出现最优解的分支，从而避免无效的搜索。这样，可以大大减少搜索的时间复杂度，提高算法的效率。

经典的例题之一是旅行商问题。该问题要求在给定的一组城市之间找到最短的路径，使得每个城市被访问且仅访问一次，最后回到出发城市。分支限界算法通过不断搜索城市的排列组合，并及时地剪枝，最终找到最优解。

在实际应用中，分支限界算法需要根据具体问题进行深入的优化和改进。例如，在处理大规模问题时，可以利用启发式算法来优化搜索的过程；在处理特定类型的问题时，可以针对性地设计剪枝条件等。

总之，分支限界算法是一种高效的组合优化问题求解方法，通过合理的搜索和剪枝策略，能够在较短的时间内找到问题的最优解。

相关问题

01背包分支限界算法C++

以下是01背包分支限界算法的C++代码实现：

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1010;

struct Node
{
    int v, w;
    double u; // u表示单位价值
    bool operator< (const Node &t) const
    {
        return u < t.u;
    }
}node[N];

int n, m;
double ans;
priority_queue<double> q;

void dfs(int u, int v, double w)
{
    if (v > m) return;
    if (u == n)
    {
        ans = max(ans, w);
        return;
    }
    if (w + q.top() * (m - v + 1) <= ans) return; // 剪枝
    q.push(node[u + 1].u);
    dfs(u + 1, v + node[u + 1].v, w + node[u + 1].w);
    q.pop();
    dfs(u + 1, v, w);
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> node[i].v >> node[i].w;
        node[i].u = (double)node[i].w / node[i].v;
    }
    sort(node + 1, node + n + 1);
    dfs(0, 0, 0);
    printf("%.2lf\n", ans);
    return 0;
}

C++ 实现分支限界算法

分支限界算法是一种解决最优化问题的算法，主要应用于组合优化和离散优化问题。下面是一个简单的实现分支限界算法的示例代码：

1. 定义问题：假设我们有一组物品，每个物品有一个重量和一个价值，我们需要从中选择一些物品，使得它们的总重量不超过最大重量限制，同时总价值最大化。

2. 定义结点：每个结点表示一个状态，其中包含以下信息：

- 已选择的物品
- 已选择的物品总重量
- 已选择的物品总价值
- 未选择的物品

3. 定义优先级函数：我们需要定义一个优先级函数，根据结点的优先级来排序结点的扩展顺序。在本例中，我们可以使用价值密度（价值/重量）来作为优先级函数。

4. 实现算法：

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

#define MAX_N 10

typedef struct {
    int weight;
    int value;
} Item;

typedef struct {
    int level;
    int weight;
    int value;
    int bound;
    int *selected;
} Node;

int max(int a, int b) {
    return a > b ? a : b;
}

int compare(const void *a, const void *b) {
    Item *ia = (Item *) a;
    Item *ib = (Item *) b;
    return (int) ((ib->value / ib->weight) - (ia->value / ia->weight));
}

void print_selected_items(Item *items, int *selected, int n) {
    printf("Selected items:\n");
    for (int i = 0; i < n; i++) {
        if (selected[i]) {
            printf("  - Item %d (weight: %d, value: %d)\n", i, items[i].weight, items[i].value);
        }
    }
}

int get_bound(Item *items, int n, int level, int weight, int value) {
    int bound = value;
    int remain_weight = MAX_N - weight;
    while (level < n && remain_weight >= items[level].weight) {
        remain_weight -= items[level].weight;
        bound += items[level].value;
        level++;
    }
    if (level < n) {
        bound += remain_weight * items[level].value / items[level].weight;
    }
    return bound;
}

void branch_and_bound(Item *items, int n, int max_weight) {
    qsort(items, n, sizeof(Item), compare);

    Node *nodes = (Node *) malloc(sizeof(Node) * (n + 1));
    for (int i = 0; i <= n; i++) {
        nodes[i].selected = (int *) malloc(sizeof(int) * n);
    }

    int best_value = 0;
    int index = 0;
    nodes[index].level = 0;
    nodes[index].weight = 0;
    nodes[index].value = 0;
    nodes[index].bound = get_bound(items, n, 0, 0, 0);
    for (int i = 0; i < n; i++) {
        nodes[index].selected[i] = 0;
    }

    while (index >= 0) {
        Node node = nodes[index];
        if (node.bound <= best_value) {
            index--;
            continue;
        }

        if (node.level == n) {
            if (node.value > best_value) {
                best_value = node.value;
                print_selected_items(items, node.selected, n);
            }
            index--;
            continue;
        }

        int level = node.level;
        int weight = node.weight;
        int value = node.value;

        // not select current item
        nodes[index + 1].level = level + 1;
        nodes[index + 1].weight = weight;
        nodes[index + 1].value = value;
        nodes[index + 1].bound = get_bound(items, n, level + 1, weight, value);
        for (int i = 0; i < n; i++) {
            nodes[index + 1].selected[i] = node.selected[i];
        }
        index++;

        // select current item
        if (weight + items[level].weight <= max_weight) {
            nodes[index + 1].level = level + 1;
            nodes[index + 1].weight = weight + items[level].weight;
            nodes[index + 1].value = value + items[level].value;
            nodes[index + 1].bound = get_bound(items, n, level + 1, weight + items[level].weight, value + items[level].value);
            for (int i = 0; i < n; i++) {
                nodes[index + 1].selected[i] = node.selected[i];
            }
            nodes[index + 1].selected[level] = 1;
            index++;
        } else {
            index--;
        }
    }

    for (int i = 0; i <= n; i++) {
        free(nodes[i].selected);
    }
    free(nodes);
}

int main() {
    Item items[] = {
            {2, 10},
            {3, 15},
            {5, 30},
            {7, 25},
            {4, 20},
            {1, 5},
            {6, 35},
            {1, 10},
            {2, 15},
            {3, 25},
    };
    int n = sizeof(items) / sizeof(Item);
    int max_weight = 10;
    branch_and_bound(items, n, max_weight);
    return 0;
}

在上面的代码中，我们首先对物品按照价值密度排序，然后创建一个结点数组，每个结点包含已选择的物品、已选择的物品总重量、已选择的物品总价值、未选择的物品和结点的优先级（即上界）等信息。我们使用一个栈来保存待扩展的结点。在每次循环中，我们从栈中弹出一个结点，如果该结点的优先级小于当前最优解，则直接抛弃。如果该结点已经选择了所有物品，则更新最优解。否则，我们可以选择不选择当前物品或选择当前物品。对于不选择当前物品的情况，我们只需要将当前结点的下一个层级设置为当前层级加一，其它信息不变。对于选择当前物品的情况，我们需要先判断是否超过了最大重量限制，如果没有超过，则需要将当前结点的下一个层级设置为当前层级加一，已选择的物品、已选择的物品总重量和已选择的物品总价值分别加上当前物品的信息，其它信息不变。否则，我们直接抛弃该结点。

最后，我们需要释放结点数组和每个结点的已选择的物品数组。