🏆 作者简介，愚公搬代码 🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，阿里云专家博主，腾讯云优秀博主，掘金优秀博主，51CTO博客专家等。 🏆《近期荣誉》：2022年CSDN博客之星TOP2，2022年华为云十佳博主等。 🏆《博客内容》：.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。 🏆🎉欢迎 👍点赞✍评论⭐收藏

🚀前言

五大常用算法的特点如下：

分治：将一个大问题拆分成若干个小问题，分别解决，然后将解决结果合并起来得到整个问题的解。分治算法的特点是递归，效率高，但对数据的规律要求比较高，需要较高的算法设计技巧。常见应用领域为排序、查找和统计等。
动态规划：将一个大问题分解成若干个小问题，通过寻找子问题之间的递推关系，求解小问题的最优解，然后将小问题的最优解组合起来解决整个大问题。动态规划的特点是可以解决具有重叠子问题的问题，但需要较高的时间和空间复杂度。常见应用领域为求解最大子序列、背包问题等。
贪心：在处理问题的过程中，每次做出局部最优的选择，希望通过局部最优的选择达到全局最优。贪心算法的特点是快速、简单，但是无法保证每个局部最优解会导致全局最优解。常见应用领域为最小生成树、活动安排等。
回溯：通过不断尝试局部的解，如果不满足要求就回溯返回，直到找到解为止。回溯算法的特点是可以解决多种类型的问题，但需要搜索所有可能的解，时间复杂度较高。常见应用领域为八皇后问题、排列组合问题等。
分支限界：与回溯算法相似，但是在搜索的过程中，通过剪枝操作来减少搜索的空间，提高算法效率。常见应用领域为旅行商问题、图着色问题等。

🚀一、分支限界算法

🔎1.基本思想

分支限界算法是一种解决最优化问题的常用算法，其基本思想是将问题的解空间划分为一棵树，每个节点代表一个可能的解，从根节点开始搜索，搜索过程中根据约束条件和限界条件，逐步减小搜索空间，只保留可能成为最优解的子树。具体来说，分支限界算法有以下几个基本步骤：

确定问题的解空间，并构造解空间树。解空间树的每个节点表示一个可能的解，根节点表示问题的初始状态，叶节点表示所有约束条件都满足且可行的解。
确定搜索策略。搜索策略包括选择节点的顺序、扩展节点的方式、剪枝方式等。合理的搜索策略可以提高搜索效率和找到最优解的概率。
判断节点是否可行，并进行剪枝。在搜索过程中，根据约束条件和限界条件，判断一个节点是否可行，如果不可行，则进行剪枝。
计算节点的上下界。上界是指当前节点子树中可能的最优解，下界是指当前节点子树中可行解的最优值。计算上下界是为了确定搜索的方向和提高搜索效率。
按照搜索策略扩展节点。根据搜索策略，选择一个可行的未扩展的节点进行扩展，即生成该节点的子节点。
判断是否到达叶节点。如果扩展的节点是叶节点，则更新最优解。
重复执行步骤3至6，直到找到最优解或搜索完整棵树。

🔎2.分支限界法与回溯法的不同

分支限界法和回溯法都是解决搜索问题的算法，但它们有以下不同点：

策略不同：回溯法是一种深度优先搜索策略，即从根节点出发，一直往深处搜索，直到找到解或无解，然后回溯到上一个节点，继续搜索。而分支限界法是一种广度优先搜索策略，它将搜索空间分为多个分支，逐个分支扩展搜索空间，直到找到解或无解。
搜索方式不同：回溯法通常采用递归的方式实现搜索，每递归一层，就会存储当前节点的状态，在回溯时再把状态恢复。分支限界法一般采用优先队列或堆等数据结构来存储当前搜索状态，并根据优先级依次扩展搜索空间。
剪枝策略不同：分支限界法在扩展搜索空间时，会根据一些剪枝策略来减少搜索量，比如可行性剪枝、最优性剪枝等。而回溯法则会根据约束条件来判断当前节点是否可行，不可行则回溯到上一个节点。
解的有效性不同：分支限界法能够保证找到最优解或近似最优解，而回溯法只能找到其中的一种解，且不保证最优。

综上，分支限界法和回溯法各有优缺点，需要根据具体问题的特点和需求来选择使用哪种算法。

🔎3.常见的两种分支限界法

分支限界算法是一种解决最优化问题的方法。其中，队列式（FIFO）分支限界法和优先队列式分支限界法是两种常见的策略。

队列式（FIFO）分支限界法将扩展节点存储在一个队列中，并按照先进先出的顺序进行扩展。也就是说，每次选择队列中的第一个节点进行扩展，直到找到最优解或队列为空。这种方法简单、直观，但会导致生成的节点数较多，效率较低。

而优先队列式分支限界法则是根据优先级将扩展节点存储在一个优先队列中。每次选择优先级最高的节点进行扩展，直到找到最优解或优先队列为空。这种方法能够有效降低生成的节点数和搜索的时间复杂度，因为它会优先扩展那些看起来更有希望达到最优解的节点。但需要注意的是，该方法的实现需要选择合适的优先级函数，并且可能需要开销较大的空间来存储优先队列。

🔎4.0/1背包问题

分支限界算法可以用来解决0/1背包问题。其基本思想是将问题划分为许多子问题，并对每个子问题进行求解。在求解子问题的过程中，利用最优性条件，对某些子问题进行剪枝，从而减少计算量，提高算法效率。

具体实现方法是将问题转化为一棵决策树，每个节点代表一个子问题。从根节点开始，依次考虑每个物品是否加入背包，分别扩展出两个子节点，一个是加入该物品，一个是不加入该物品。计算每个子节点的上界，选择上界最大的节点进行扩展，直到达到叶子节点，或者扩展出的节点的上界小于当前已知的最优解。最后，返回搜索到的最优解即可。

就拿0/1背包问题做例子，回溯法求解0/1背包问题实际上是盲目地搜索解空间树，回溯法只会不断地往下走，虽然通过剪枝函数能减少一定的计算，但是当经过一个结点时，并不知晓其子结点会是怎样的情况，从而盲目继续搜索。而分支限界法则不一样，在经过某一结点时，会根据限界条件判断其结点之下的情况是否能够导出最优解，如若不能，直接不走这条路。这样虽然在空间上不占优势，但是搜索并不盲目，速度上快了很多。

下面是使用C#实现的分支限界算法解决0/1背包问题的示例代码：

using System;
using System.Collections.Generic;

namespace BranchAndBound
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] weights = { 10, 20, 30 };
            int[] values = { 60, 100, 120 };
            int capacity = 50;

            Knapsack knapsack = new Knapsack(weights, values, capacity);
            int maxValue = knapsack.Solve();

            Console.WriteLine("Max value: " + maxValue);
        }
    }

    class Knapsack
    {
        private readonly int[] weights;
        private readonly int[] values;
        private readonly int capacity;

        public Knapsack(int[] weights, int[] values, int capacity)
        {
            this.weights = weights;
            this.values = values;
            this.capacity = capacity;
        }

        public int Solve()
        {
            int n = weights.Length;
            var queue = new Queue<Node>();
            queue.Enqueue(new Node(0, 0, 0));

            int maxValue = 0;

            while(queue.Count > 0)
            {
                Node node = queue.Dequeue();

                if(node.Level == n)
                {
                    if(node.Value > maxValue)
                    {
                        maxValue = node.Value;
                    }

                    continue;
                }

                // Explore left child (include current item)
                if(node.Weight + weights[node.Level] <= capacity)
                {
                    queue.Enqueue(new Node(node.Level + 1, node.Weight + weights[node.Level], node.Value + values[node.Level]));
                }

                // Explore right child (exclude current item)
                queue.Enqueue(new Node(node.Level + 1, node.Weight, node.Value));
            }

            return maxValue;
        }

        class Node
        {
            public int Level { get; }
            public int Weight { get; }
            public int Value { get; }

            public Node(int level, int weight, int value)
            {
                Level = level;
                Weight = weight;
                Value = value;
            }
        }
    }
}

在上面的代码中，我们定义了一个Knapsack类来表示0/1背包问题，并使用weights、values和capacity数组来初始化它。然后，我们实现了Solve方法来解决问题。在这个方法中，我们使用一个队列来保存待处理的节点，初始化时将根节点（即将第一个物品放入背包）加入队列中。

然后，在队列不为空时，我们从队列中取出下一个节点并进行处理。如果这个节点的层级等于物品数量n（即已经考虑完了最后一个物品），我们就检查这个节点的价值是否超过当前最大值，并继续处理下一个节点。

否则，我们分别考虑将下一个物品放入背包或不放入背包两种可能，得到左右两个子节点，并将它们加入队列中。

最后，我们返回找到的最大价值。

🔎5.单源最短路径问题

分支限界算法是一种用于解决优化问题的算法，其中单源最短路径问题是其中一个重要的应用。

单源最短路径问题是指，在一个有向加权图中，给定一个起点，需要找到从起点到其他所有节点的最短路径。这个问题可以用分支限界算法来解决。

分支限界算法通过初始状态开始搜索，每次找到当前状态的下一步可能的状态集合，并计算每个状态的代价值。然后按照代价值从小到大的顺序对状态进行排序，并按顺序逐个扩展生成子节点。如果子节点中有目标状态，则记录目标状态的代价值并更新最小代价值。如果子节点中没有目标状态，将代价值小于当前最小代价值的节点加入搜索树中，继续搜索。如果搜索树中没有找到目标状态，则返回最小代价值作为解。

对于单源最短路径问题，可以用分支限界算法来搜索最短路径。可以将起点看作初始状态，目标状态为所有节点，代价值为路径长度。每次搜索时，找到起点能够到达的下一步可能的状态（即与起点相邻的节点），计算它们到起点的路径长度，并按照路径长度从小到大排序。依次扩展每个节点，生成它们到目标状态的路径，并计算代价值。如果代价值小于当前最小代价值，则更新最小代价值，否则将该节点加入搜索树中。继续搜索直到搜索树为空或找到目标状态。

通过分支限界算法，可以在有向加权图中找到从起点到其他所有节点的最短路径，对于很大的图，这是一个非常高效的解法。

以下是使用C#实现分支限界算法解决单源最短路径问题的基本步骤和示例代码：

定义图的结构和边的类：

public class Edge
{
    public int source, dest, weight;

    public Edge(int s, int d, int w)
    {
        source = s;
        dest = d;
        weight = w;
    }
}

public class Graph
{
    public int V;
    public List<Edge>[] adj;

    public Graph(int v)
    {
        V = v;
        adj = new List<Edge>[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new List<Edge>();
    }

    public void AddEdge(int s, int d, int w)
    {
        Edge e = new Edge(s, d, w);
        adj[s].Add(e);
    }
}

定义状态类，并实现比较方法：

public class State : IComparable<State>
{
    public int city;
    public int cost;
    public int[] path;
    public bool[] visited;

    public State(int c, int cst, int[] p, bool[] v)
    {
        city = c;
        cost = cst;
        path = p;
        visited = v;
    }

    public int CompareTo(State other)
    {
        return cost.CompareTo(other.cost);
    }
}

定义分支限界算法的主方法：

public static int[] ShortestPath(Graph g, int src)
{
    int[] parent = new int[g.V];
    int[] path = new int[g.V];
    bool[] visited = new bool[g.V];
    for (int i = 0; i < g.V; ++i)
    {
        parent[i] = -1;
        path[i] = -1;
        visited[i] = false;
    }

    PriorityQueue<State> pq = new PriorityQueue<State>();
    pq.Enqueue(new State(src, 0, new int[g.V], visited));

    while (pq.Count > 0)
    {
        State s = pq.Dequeue();
        visited = s.visited;
        if (visited[s.city])
            continue;

        visited[s.city] = true;
        parent[s.city] = s.path[s.city];
        path[s.city] = s.cost;

        foreach (Edge e in g.adj[s.city])
        {
            if (!visited[e.dest])
            {
                int[] tempPath = new int[g.V];
                Array.Copy(s.path, tempPath, g.V);
                tempPath[e.dest] = s.city;
                pq.Enqueue(new State(e.dest, s.cost + e.weight, tempPath, visited));
            }
        }
    }

    return path;
}

测试：

static void Main(string[] args)
{
    Graph g = new Graph(5);
    g.AddEdge(0, 1, 10);
    g.AddEdge(0, 4, 5);
    g.AddEdge(1, 2, 1);
    g.AddEdge(1, 4, 2);
    g.AddEdge(2, 3, 4);
    g.AddEdge(3, 2, 6);
    g.AddEdge(3, 0, 7);
    g.AddEdge(4, 1, 3);
    g.AddEdge(4, 2, 9);
    g.AddEdge(4, 3, 2);

    int[] path = ShortestPath(g, 0);
    for (int i = 0; i < g.V; ++i)
    {
        Console.WriteLine("Shortest path from 0 to " + i + " is " + path[i]);
    }
}

输出结果为：

Shortest path from 0 to 0 is 0
Shortest path from 0 to 1 is 8
Shortest path from 0 to 2 is 9
Shortest path from 0 to 3 is 7
Shortest path from 0 to 4 is 5

说明从0出发到其他所有点的最短路径分别为0, 8, 9, 7, 5。

🔎6.最优装载问题

装载问题是指有一些货物需要全部装到一些已知容量的集装箱中，要求尽可能地充分利用集装箱容量，使所需集装箱数量最少。分支限界算法可以用来解决这个问题。

具体地，采用分支限界算法的流程如下：

定义问题的状态空间，用一个状态描述集装箱的装载情况和还未装载的货物情况。
对状态空间进行扩展。
对扩展后的状态进行评价，得到一个估价函数。
选择当前状态的最有希望的扩展状态，放入活结点表中。
从活结点表中选取一个结点，进行扩展。
重复4-5步骤，直到找到最优解或者所有结点均被扩展。

在解决装载问题时，状态空间可以定义为一个二元组$(x,y)$，其中$x$表示已经装载的货物的总重量，$y$表示还未装载的货物。对于一个状态$(x,y)$，我们可以选择装载剩下所有货物或不装载，从而得到两个新的状态，然后利用估价函数计算它们的估计值，将它们加入活结点表中。具体而言，估价函数可以定义为已装载的货物总重量与容量比值的补数，即$f(x,y) = -(x/V)$，其中$V$表示集装箱的总容量。这个估价函数的值越小，表示当前状态越接近最优解。在扩展状态时，我们首先选择估价函数最小的状态进行扩展。

通过这样的分支限界算法，可以找到一种最优的货物装载方案，使所需集装箱数量最少。

最优装载问题是一种经典的组合优化问题，它的目标是在给定的一组物品中，选择尽可能多的物品放入一个容器中，使得容器的总重量不超过给定的重量限制，同时选择的物品总重量要最大化。这个问题可以使用分支限界算法来求解。

using System;
using System.Collections.Generic;

// 定义货物结构体，存储货物的重量
public struct Goods
{
    public int weight;
}

class Program
{
    static void Main(string[] args)
    {
        // 设置货物重量数组和容器容量
        Goods[] goodsArray = new Goods[] { new Goods { weight = 1 }, new Goods { weight = 2 }, new Goods { weight = 3 }, new Goods { weight = 4 }, new Goods { weight = 5 } };
        int containerCapacity = 10;

        // 调用分支限界算法求解最优装载问题
        int maxWeight = FindMaxWeight(goodsArray, containerCapacity);

        // 输出最大的载重量
        Console.WriteLine("最大载重量为：" + maxWeight);
    }

    static int FindMaxWeight(Goods[] goodsArray, int containerCapacity)
    {
        int maxWeight = 0; // 最大载重量
        int currentIndex = 0; // 当前搜索到的货物下标
        int currentWeight = 0; // 当前装载的货物总重量
        int remainingCapacity = containerCapacity; // 剩余容量

        // 使用优先级队列保存分支节点
        PriorityQueue<Node> queue = new PriorityQueue<Node>();
        queue.Enqueue(new Node(currentIndex, currentWeight, remainingCapacity));

        while (queue.Count > 0)
        {
            // 取出优先级最高的节点
            Node node = queue.Dequeue();

            if (node.currentWeight > maxWeight)
            {
                // 更新最大载重量
                maxWeight = node.currentWeight;
            }

            if (node.remainingCapacity == 0)
            {
                // 如果容器已经被装满，则不需要再搜索下去
                continue;
            }

            if (node.currentIndex >= goodsArray.Length)
            {
                // 如果货物已经全部搜索完毕，则不需要再搜索下去
                continue;
            }

            // 分支1：不选择当前货物
            queue.Enqueue(new Node(node.currentIndex + 1, node.currentWeight, node.remainingCapacity));

            int nextWeight = node.currentWeight + goodsArray[node.currentIndex].weight;
            if (nextWeight > maxWeight && nextWeight <= containerCapacity)
            {
                // 分支2：选择当前货物，并且可以继续添加货物
                queue.Enqueue(new Node(node.currentIndex + 1, nextWeight, node.remainingCapacity - goodsArray[node.currentIndex].weight));
            }
        }

        return maxWeight;
    }
}

// 定义分支节点结构体
public struct Node : IComparable<Node>
{
    public int currentIndex;
    public int currentWeight;
    public int remainingCapacity;

    public Node(int currentIndex, int currentWeight, int remainingCapacity)
    {
        this.currentIndex = currentIndex;
        this.currentWeight = currentWeight;
        this.remainingCapacity = remainingCapacity;
    }

    public int CompareTo(Node other)
    {
        // 比较当前节点和其他节点的优先级
        return other.currentWeight - this.currentWeight;
    }
}

// 定义优先级队列
public class PriorityQueue<T> where T : IComparable<T>
{
    private List<T> data = new List<T>();

    public void Enqueue(T item)
    {
        data.Add(item);
        int childIndex = data.Count - 1;
        while (childIndex > 0)
        {
            int parentIndex = (childIndex - 1) / 2;
            if (data[childIndex].CompareTo(data[parentIndex]) >= 0)
            {
                break;
            }
            T tmp = data[childIndex];
            data[childIndex] = data[parentIndex];
            data[parentIndex] = tmp;
            childIndex = parentIndex;
        }
    }

    public T Dequeue()
    {
        int lastIndex = data.Count - 1;
        T frontItem = data[0];
        data[0] = data[lastIndex];
        data.RemoveAt(lastIndex);

        --lastIndex;
        int parentIndex = 0;
        while (true)
        {
            int childIndex = parentIndex * 2 + 1;
            if (childIndex > lastIndex)
            {
                break;
            }
            int rightChild = childIndex + 1;
            if (rightChild <= lastIndex && data[rightChild].CompareTo(data[childIndex]) < 0)
            {
                childIndex = rightChild;
            }
            if (data[parentIndex].CompareTo(data[childIndex]) <= 0)
            {
                break;
            }
            T tmp = data[parentIndex];
            data[parentIndex] = data[childIndex];
            data[childIndex] = tmp;
            parentIndex = childIndex;
        }

        return frontItem;
    }

    public int Count
    {
        get { return data.Count; }
    }
}

在这个示例代码中，我们使用了一个优先级队列来保存分支节点，每次从队列中取出优先级最高的节点进行扩展搜索。在搜索过程中，我们使用变量maxWeight来记录当前搜索到的最大载重量，当搜索到更大的载重量时，更新这个变量。另外，我们使用了一个结构体Node来保存分支节点的信息，并重载了它的比较运算符，以便优先级队列可以按照节点的权值排序。

在主函数中，我们设置了一个货物重量数组和一个容器容量，然后调用FindMaxWeight函数进行搜索。函数中，我们首先初始化搜索过程的参数，然后将初始状态的节点加入优先级队列中。接着，每次从队列中取出优先级最高的节点进行扩展搜索，直到队列为空。在每次取出一个节点进行扩展搜索时，我们将其分为两种情况进行处理：

不选择当前货物。在这种情况下，货物下标和当前载重量不变，容器剩余容量也不变，因此可以直接将这个状态加入优先级队列中。
选择当前货物。在这种情况下，我们将货物下标加一，将当前载重量加上当前货物的重量，将容器剩余容量减去当前货物的重量，然后将这个状态加入优先级队列中。

使用分支限界算法求解最优装载问题的时间复杂度为$O(2^n)$，其中$n$是货物的数量。在实际求解中，如果使用合适的分支操作，可以避免搜索所有可能的状态，从而提高算法的效率。

我正在参与2023腾讯技术创作特训营第四期有奖征文，快来和我瓜分大奖！

(完)c#数据结构与算法

【愚公系列】2023年12月五大常用算法(五)-分支限界算法

🚀前言

🚀一、分支限界算法

🔎1.基本思想

🔎2.分支限界法与回溯法的不同

🔎3.常见的两种分支限界法

🔎4.0/1背包问题

🔎5.单源最短路径问题

🔎6.最优装载问题

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

(完)c#数据结构与算法

【愚公系列】2023年12月 五大常用算法(五)-分支限界算法

🚀前言

🚀一、分支限界算法

🔎1.基本思想

🔎2.分支限界法与回溯法的不同

🔎3.常见的两种分支限界法

🔎4.0/1背包问题

🔎5.单源最短路径问题

🔎6.最优装载问题

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

【愚公系列】2023年12月五大常用算法(五)-分支限界算法