# 干货 | 11分钟带你全面掌握branch and bound（分支定界）算法-概念篇（下）

03 算法框架

1. Using a heuristic, find a solution xh to the optimization problem. Store its value, B = f(x_h). (If no heuristic is available, set B to infinity.) B will denote the best solution found so far, and will be used as an upper bound on candidate solutions.
2. Initialize a queue to hold a partial solution with none of the variables of the problem assigned.
3. Loop until the queue is empty:
3.1. Take a node N off the queue.
3.2. If N represents a single candidate solution x and f(x) < B, then x is the best solution so far. Record it and set B ← f(x).
3.3. Else, branch on N to produce new nodes Ni. For each of these:
3.3.1. If bound(N_i) > B, do nothing; since the lower bound on this node is greater than the upper bound of the problem, it will never lead to the optimal solution, and can be discarded.
3.3.2. Else, store Ni on the queue.

Depth-first search (DFS)：深度优先搜索，就是纵向搜索，先一个分支走到底，再跳到另一个分支走到底。这种搜索可以用LIFO queue也就是栈实现。

Best-First Search：最佳优先搜索，最佳优先搜索算法是一种启发式搜索算法（Heuristic Algorithm），其基于广度优先搜索算法，不同点是其依赖于估价函数对将要遍历的节点进行估价，选择代价小的节点进行遍历，直到找到目标点为止。这种搜索可以用优先队列priority queue来实现。

04 伪代码描述[1]

// C++-like implementation of branch and bound,
// assuming the objective function f is to be minimized
CombinatorialSolution branch_and_bound_solve(
CombinatorialProblem problem,
ObjectiveFunction objective_function /*f*/,
BoundingFunction lower_bound_function /*g*/)
{
// Step 1 above
double problem_upper_bound = std::numeric_limits<double>::infinity; // = B
CombinatorialSolution heuristic_solution = heuristic_solve(problem); // x_h
problem_upper_bound = objective_function(heuristic_solution); // B = f(x_h)
CombinatorialSolution current_optimum = heuristic_solution;
// Step 2 above
queue<CandidateSolutionTree> candidate_queue;
// problem-specific queue initialization
candidate_queue = populate_candidates(problem);
while (!candidate_queue.empty()) { // Step 3 above
// Step 3.1
CandidateSolutionTree node = candidate_queue.pop();
// "node" represents N above
if (node.represents_single_candidate()) { // Step 3.2
if (objective_function(node.candidate()) < problem_upper_bound) {
current_optimum = node.candidate();
problem_upper_bound = objective_function(current_optimum);
}
// else, node is a single candidate which is not optimum
}
else { // Step 3.3: node represents a branch of candidate solutions
// "child_branch" represents N_i above
for (auto&& child_branch : node.candidate_nodes) {
if (lower_bound_function(child_branch) <= problem_upper_bound) {
candidate_queue.enqueue(child_branch); // Step 3.3.2
}
// otherwise, g(N_i) > B so we prune the branch; step 3.3.1
}
}
}
return current_optimum;
}

|
2月前
|

【数据结构和算法】---二叉树（1）--树概念及结构
【数据结构和算法】---二叉树（1）--树概念及结构
22 0
|
1天前
|

【8月更文挑战第2天】决策树算法以其直观性和解释性在机器学习领域中独具魅力，尤其擅长处理非线性关系。相较于复杂模型，决策树通过简单的分支逻辑实现数据分类，易于理解和应用。本示例通过Python的scikit-learn库演示了使用决策树对鸢尾花数据集进行分类的过程，并计算了预测准确性。虽然决策树优势明显，但也存在过拟合等问题。即便如此，无论是初学者还是专家都能借助决策树的力量提升数据分析能力。
11 4
|
29天前
|

52 3
|
2月前
|

28 3
|
2月前
|

【6月更文挑战第15天】递归算法在C语言中是强大力量的体现，通过函数调用自身解决复杂问题。递归涉及基本概念如自调用、终止条件及栈空间管理。在C中实现递归需定义递归函数，分解问题并设定停止条件。阶乘和斐波那契数列是经典应用示例，展示了递归的优雅与效率。然而，递归可能导致栈溢出，需注意优化。学习递归深化了对“分而治之”策略的理解。**
41 7
|
2月前
|

【排序】数据结构——排序算法概念及代码详解（插入、冒泡、快速、希尔）
【排序】数据结构——排序算法概念及代码详解（插入、冒泡、快速、希尔）
24 1
|
2月前
|

【二叉树】数据结构——BST二叉树基本概念及算法设计（插入、删除、遍历操作）
【二叉树】数据结构——BST二叉树基本概念及算法设计（插入、删除、遍历操作）
21 0
|
2月前
|

22 0
|
2月前
|

18 0
|
2月前
|

14 0