数据结构和算法

DSA - 主页 DSA - 概述 DSA - 环境设置 DSA - 算法基础 DSA - 渐近分析

数据结构

DSA - 数据结构基础 DSA - 数据结构和类型 DSA - 数组数据结构

链接列表

DSA - 链接列表数据结构 DSA - 双向链接列表数据结构 DSA - 循环链表数据结构

堆栈 &队列

DSA - 堆栈数据结构 DSA - 表达式解析 DSA - 队列数据结构

搜索算法

DSA - 搜索算法 DSA - 线性搜索算法 DSA - 二分搜索算法 DSA - 插值搜索 DSA - 跳跃搜索算法 DSA - 指数搜索 DSA - 斐波那契搜索 DSA - 子列表搜索 DSA - 哈希表

排序算法

DSA - 排序算法 DSA - 冒泡排序算法 DSA - 插入排序算法 DSA - 选择排序算法 DSA - 归并排序算法 DSA - 希尔排序算法 DSA - 堆排序 DSA - 桶排序算法 DSA - 计数排序算法 DSA - 基数排序算法 DSA - 快速排序算法

图形数据结构

DSA - 图形数据结构 DSA - 深度优先遍历 DSA - 广度优先遍历 DSA - 生成树

树数据结构

DSA - 树数据结构 DSA - 树遍历 DSA - 二叉搜索树 DSA - AVL 树 DSA - 红黑树 DSA - B树 DSA - B+ 树 DSA - 伸展树 DSA - 尝试 DSA - 堆数据结构

递归

DSA - 递归算法 DSA - 使用递归的汉诺塔 DSA - 使用递归的斐波那契数列

分而治之

DSA - 分而治之 DSA - 最大最小问题 DSA - 施特拉森矩阵乘法 DSA - Karatsuba 算法

贪婪算法

DSA - 贪婪算法 DSA - 旅行商问题(贪婪方法) DSA - Prim 最小生成树 DSA - Kruskal 最小生成树 DSA - Dijkstra 最短路径算法 DSA - 地图着色算法 DSA - 分数背包问题 DSA - 作业排序截止日期 DSA - 最佳合并模式算法

动态规划

DSA - 动态规划 DSA - 矩阵链乘法 DSA - Floyd Warshall 算法 DSA - 0-1 背包问题 DSA - 最长公共子序列算法 DSA - 旅行商问题(动态方法)

近似算法

DSA - 近似算法 DSA - 顶点覆盖算法 DSA - 集合覆盖问题 DSA - 旅行商问题(近似方法)

随机算法

DSA - 随机算法 DSA - 随机快速排序算法 DSA - Karger 最小割算法 DSA - Fisher-Yates 洗牌算法

DSA 有用资源

DSA - 问答 DSA - 快速指南 DSA - 有用资源 DSA - 讨论


DSA - Branch and Bound Algorithm

The branch and bound algorithm is a technique used for solving combinatorial optimization problems. First, this algorithm breaks the given problem into multiple sub-problems and then using a bounding function, it eliminates only those solutions that cannot provide optimal solution.

Combinatorial optimization problems refer to those problems that involve finding the best solution from a finite set of possible solutions, such as the 0/1 knapsack problem, the travelling salesman problem and many more.

When Branch and Bound Algorithm is used?

The branch and bound algorithm can be used in the following scenario −

  • Whenever we encounter an optimization problem whose variables belong to a discrete set. These types of problems are known as discrete optimization problems.

  • As discussed earlier, this algorithm is also used to solve combinatorial optimization problem.

  • If the given problem is a mathematical optimization problem, then the branch and bound algorithm can also be applied.

How does Branch and Bound Algorithm work?

The branch and bound algorithm works by exploring the search space of the problem in a systematic way. It uses a tree structure (state space tree) to represent the solutions and their extensions. Each node in the tree is part of the partial solution, and each edge corresponds to an extension of this solution by adding or removing an element. The root node represents the empty solution.

The algorithm starts with the root node and moves towards its children nodes. At each level, it evaluates whether a child node satisfies the constraints of the problem to achieve a feasible solution. This process is repeated until a leaf node is reached, which represents a complete solution.

Branch and Bound

Searching techniques in Branch and Bound

There are different approaches to implementing the branch and bound algorithm. The implementation depends on how to generate the children nodes and how to search the next node to expand. Some of the common searching techniques are −

  • Breadth-first search − It maintains a queue of nodes to expand, which means this searching technique uses First in First out order to search next node.

  • Least cost search − This searching technique works by computing bound value of each node. The algorithm selects the node with the lowest bound value to expand next.

  • Depth-first search − It maintains a stack of nodes to expand, which means this searching technique uses Last in First out order to search the next node.

Types of Branch and Bound Solutions

The branch and bound algorithm can produce two types of solutions. They are as follows −

  • Variable size solution − This type of solution is represented by a subset which is the optimal solution to the given problem.

  • Fixed-size solution − This type of solution is represented by 0s and 1s.

Advantages of Branch and Bound Algorithm

The advantages of the branch and bound algorithm are as follows −

  • It can reduce the time complexity by avoiding unnecessary exploration of the state space tree.

  • It has different search techniques that can be used for different types of problems and preferences.

Disadvantages of Branch and Bound Algorithm

Some of the disadvantages of the branch and bound algorithm are as follows −

  • In the worst case scenario, it may search for all the combinations to produce solutions.

  • It can time consuming if the state space tree is too large.