当前位置：首页 > news >正文

分支限界法实战：从TSP到工业优化的可调试最优解实现

news 2026/6/12 5:17:11

1. 这不是教科书里的抽象概念，而是你手头那个卡住的优化问题的解药

“Branch and Bound — Introduction Prior to Coding the Algorithm From Scratch”——光看这个标题，很多人第一反应是：又一个算法课上的PPT名词，离实际写代码还隔着三座山。但我在制造业排产系统里调优调度引擎时，在物流路径规划项目中压测千万级节点图时，在金融风控模型里做特征子集搜索时，反复验证过一件事：分支限界法（Branch and Bound）不是理论装饰，而是当穷举太慢、贪心不准、启发式抖动时，你唯一能亲手攥在手里、逐行调试、精准控制的确定性最优解工具。它不依赖黑箱训练数据，不靠概率蒙特卡洛采样，而是用数学逻辑把搜索空间切成可管理的块，再用目标函数的上下界像筛子一样一层层滤掉无效分支。我见过太多团队在“用现成库”和“自己硬写DP”之间摇摆，结果要么被scikit-learn的OptimizeResult对象绕晕，要么在递归栈溢出后放弃。而分支限界，恰恰站在中间：它要求你理解问题结构，但不强求你推导出闭式解；它需要你写代码，但每一步剪枝逻辑都清晰可见、可审计、可针对业务规则定制。比如在电商仓储拣货路径优化中，客户要求“必须在20分钟内返回最短路径”，你不能只扔给networkx.shortest_path——它返回的是单点最短，而你需要的是覆盖全部137个SKU位点的TSP最优解。这时，分支限界就是你的手术刀：你可以把“已访问点集”作为分支状态，把“当前路径长度 + 最小生成树下界”作为限界函数，一行行写出可控、可打断、可记录中间最优解的代码。本文不讲定义复述，不列伪代码充数，而是带你从零开始，把“分支限界”从标题变成你IDE里可运行、可调试、可部署的.py文件。适合正在啃运筹学作业的研究生、被NP-hard问题卡住的算法工程师、以及所有想亲手造一把“确定性最优解钥匙”的实践者。

2. 为什么非得是分支限界？——在暴力、贪心与黑箱之间的第三条路

2.1 暴力穷举的幻灭：当n=15就耗尽内存时

我们先直面现实：假设你要解决一个含15个决策变量的0-1整数规划问题，每个变量取0或1，总搜索空间是2¹⁵ = 32,768种组合。这看起来很友好，对吧？但真实场景远比这残酷。我在为某新能源电池厂设计电芯配组算法时，面对的是200+电芯单元，需从中选出60个组成一组，满足电压差≤5mV、容量差≤1.2Ah等硬约束。组合数是C(200,60) ≈ 10¹⁰⁰量级——远超宇宙原子总数。暴力枚举连“开始”都做不到。更隐蔽的陷阱是隐式穷举：比如用DFS遍历所有可能的调度序列，看似只存当前路径，但递归深度达100层时，Python默认递归限制（1000）会直接报RecursionError，而手动改高限制又导致栈内存爆炸。分支限界的第一重价值，就是用“分支”把指数爆炸的空间显式切分成树状结构，再用“限界”让这棵树不会无限生长——它不消灭复杂度，但把它关进可控的笼子里。

2.2 贪心算法的局限：局部最优如何拖垮全局收益

贪心策略常被当作快速解法首选。比如在任务调度中，按截止时间最早优先（EDF）安排；在装箱问题中，按物品体积降序放入首个能容纳的箱子。但它的致命伤在于“不可逆性”。我曾参与一个港口集装箱堆叠优化项目：目标是最小化翻箱次数。贪心策略每次将新到集装箱放在“当前顶层最空闲的堆位”，结果运行一周后发现，第3天堆叠的集装箱，到第7天要被翻动12次——因为早期贪心选择堵死了后期更优的堆叠路径。数学上，这叫缺乏“最优子结构性质”：局部最优解无法保证构成全局最优。分支限界则完全不同：它允许你回溯。当你在某个节点发现“当前已选任务集合的完成时间 + 剩余任务最小可能耗时 > 当前已知最优解”，就立刻剪掉整棵子树。这个“当前已知最优解”就是你在搜索过程中不断更新的标杆，它让算法始终带着全局视野做局部决策。贪心是近视眼医生，分支限界是拿着CT片做手术的外科医生——前者快，后者准。

2.3 黑箱优化器的盲区：当“最优”结果无法解释时

现代工具链里，scipy.optimize.minimize、ortools、gurobi等求解器确实强大。但它们像高级餐厅的主厨：你给出菜单（目标函数+约束），他端出菜品（最优解），但你不知道火候怎么控、调料何时加。当结果不符合业务直觉时，你无从下手。比如在广告投放预算分配中，gurobi返回的解显示“将70%预算投给渠道A”，但业务方质疑：“历史数据显示渠道A转化率在下午4点后暴跌，这个解没考虑时段衰减！”——此时，你无法修改求解器内部逻辑。而分支限界是你亲手搭建的厨房：分支策略可以定义为“先固定时段维度，再分渠道”，限界函数可以嵌入“时段衰减系数×预估转化率”的业务公式。它把优化过程从“黑箱输出”变成“白盒演算”，每一个剪枝动作都对应一条可验证的业务规则。这正是它在金融风控、医疗排程等强监管领域不可替代的原因：结果不仅要对，还要能说清“为什么对”。

2.4 分支限界的核心思想拆解：三要素闭环

分支限界不是魔法，它由三个严丝合缝的齿轮咬合驱动：

分支（Branching）：空间切割的刀
将原始问题分解为互斥且完备的子问题。关键在“如何切”？常见策略有：
- 二分分支：对连续变量，取中点切为[x≤mid]和[x>mid]；
- 枚举分支：对离散变量，如TSP中“下一个访问城市”枚举所有未访问节点；
- 优先分支：基于启发式选择“最可能产生改进”的变量分支（如选择当前松弛解中分数部分最接近0.5的变量）。
提示：分支策略直接影响搜索树宽度。我在物流路径项目中测试过：对“是否经过枢纽站”先行分支，比随机选城市分支，平均减少47%的节点探索量——因为枢纽站连接性决定了整个网络连通性。
限界（Bounding）：剪枝的尺子
为每个子问题计算一个“不可能优于当前最优解”的数值界限。这是算法效率的灵魂。常用方法：
- 松弛解限界：去掉整数约束，解LP松弛问题，其最优值即为下界（最小化问题）；
- 启发式限界：用贪心算法快速获得一个可行解，其目标值即为上界；
- 组合限界：如TSP中，用最小生成树（MST）权重作为下界——因为任何哈密顿回路必包含一棵生成树。
注意：限界越紧，剪枝越狠。但计算紧界本身有开销。实测表明，对中小规模问题（n<50），MST下界计算耗时仅占总运行时间3%，却能剪掉82%的无效分支；而对n>200的问题，改用更粗但更快的“最近邻启发式”上界，整体性能反而提升。
搜索策略（Search Strategy）：遍历的路线图
决定先探索哪棵子树。主流有：
- 深度优先（DFS）：内存占用小，能快速找到第一个可行解，适合“找一个好解”场景；
- 广度优先（BFS）：易并行，但内存爆炸；
- 最佳优先（Best-First）：按节点下界值排序，优先探索“最有希望”的节点，易获最优解但内存压力大；
- 混合策略：如“先DFS找初始上界，再Best-First精搜”。我在电商推荐系统特征选择中采用此法：前10秒用DFS获取一个f1-score=0.82的解，之后切换为按“信息增益下界”排序的Best-First，最终在62秒内将f1提升至0.873。

这三个要素构成闭环：分支产生新节点 → 限界评估节点价值 → 搜索策略决定处理顺序 → 新节点的限界更新可能触发剪枝 → 剪枝后剩余节点继续分支……直到搜索树被完全探索或满足停止条件。

3. 从零编码：以旅行商问题（TSP）为蓝本的手把手实现

3.1 问题建模：把现实约束翻译成数学语言

我们以经典TSP为例：给定n个城市坐标，求访问每个城市恰好一次并返回起点的最短回路。这不是玩具问题——它直接对应电路板钻孔路径优化、外卖骑手多单配送、基因测序片段拼接。首先明确输入输出：

输入：distances[i][j]表示城市i到j的欧氏距离（对称矩阵，distances[i][i]=0）
输出：best_path: List[int]最优路径（如[0,2,1,3,0]），best_cost: float对应总长度

关键建模决策：

状态表示：用元组(current_city, visited_mask, path_length)表示当前节点。其中visited_mask是整数，其二进制位表示城市是否已访问（如3个城市，mask=5即101₂，表示城市0和2已访问）。这比用set或list节省90%内存，且位运算极快。
分支方式：从current_city出发，枚举所有mask中未访问的城市next_city，生成新状态(next_city, mask | (1<<next_city), path_length + distances[current_city][next_city])。
限界函数：采用MST下界。对未访问城市集合S，计算其最小生成树权重，加上“从当前城市到S中任一城市的最短距离”和“S中任一城市返回起点的最短距离”。这个下界虽非最紧，但计算稳定，且可增量更新。

3.2 核心数据结构：用堆与位掩码驯服指数增长

分支限界最怕两件事：内存爆满、重复计算。我们用两个关键技术应对：

1. 优先队列（最小堆）管理待探索节点
Python的heapq是理想选择。我们将节点表示为元组(lower_bound, node_state, path_so_far)，堆按lower_bound排序，确保每次heappop()拿到的都是当前最有希望的节点。注意：node_state需包含足够信息重建路径，但避免存储冗余数据。实测中，若在node_state中存完整路径列表，n=20时内存占用达1.2GB；改为只存(current, mask)，路径通过回溯重建，内存降至45MB。

2. 位掩码（Bitmask）压缩状态空间
对n个城市，visited_mask范围是0到2ⁿ-1。n=20时，mask有1048576种可能，可全部预计算并缓存。我们构建mst_lower_bound[mask]数组：对每个mask，预计算其对应城市集合的MST权重。预计算用Prim算法，时间复杂度O(n²·2ⁿ)，但只需执行一次。后续查表O(1)。代码片段如下：

def precompute_mst_bounds(distances, n): # mst_lower_bound[mask] = MST权重 of cities in mask mst_lower_bound = [float('inf')] * (1 << n) mst_lower_bound[0] = 0 mst_lower_bound[1] = 0 # single city has no edge # iterate over all masks for mask in range(1, 1 << n): cities = [i for i in range(n) if mask & (1 << i)] if len(cities) <= 1: continue # Prim's algorithm on subgraph induced by 'cities' # ... (standard Prim implementation) mst_lower_bound[mask] = mst_weight return mst_lower_bound

实操心得：预计算阶段是性能瓶颈。我在n=18时发现Prim对每个mask单独运行太慢。优化方案是：用动态规划思想，mst_lower_bound[mask] = min_{i in mask} { mst_lower_bound[mask without i] + min_edge_from_i_to_rest }。这将时间复杂度从O(n²·2ⁿ)降至O(n·2ⁿ)，n=20时预计算从42秒降至1.8秒。

3.3 限界函数实现：MST下界的工程化落地

MST下界是TSP分支限界的黄金标准。但教科书只讲概念，工程实现有三大坑：

坑1：MST计算需支持任意子集
标准Prim算法输入是完整图，而我们需要对任意城市子集S计算MST。解决方案：在Prim中，只考虑S内城市间的边。代码中用cities_in_mask列表过滤邻接关系。

坑2：下界需包含“进出”代价
单纯MST权重只是S内部连接成本，还需加上：

min_out_cost: 从当前城市curr到S中任一城市的最短距离
min_in_cost: 从S中任一城市回到起点（城市0）的最短距离
因此完整下界 =mst_lower_bound[mask] + min_out_cost + min_in_cost

坑3：增量更新避免重复计算
每次分支时，mask增加一位（新城市加入），若每次都重算MST，开销巨大。我们采用增量式：当mask_new = mask_old | (1<<new_city)，新MST权重 ≤ 旧MST权重 +min_edge_from_new_city_to_old_set。但为精确，我们仍采用预计算查表法，因n≤20时内存可接受。

完整限界函数代码：

def calculate_lower_bound(curr, mask, distances, n, mst_lower_bound): if mask == (1 << n) - 1: # all visited return distances[curr][0] # return to start # cities not visited unvisited = [i for i in range(n) if not (mask & (1 << i))] if len(unvisited) == 0: return distances[curr][0] # MST cost for unvisited set unvisited_mask = 0 for i in unvisited: unvisited_mask |= (1 << i) mst_cost = mst_lower_bound[unvisited_mask] # min cost from curr to any unvisited min_out = min(distances[curr][i] for i in unvisited) # min cost from any unvisited to start (city 0) min_in = min(distances[i][0] for i in unvisited) return mst_cost + min_out + min_in

注意：min_out和min_in必须实时计算，因curr和起点固定，而unvisited随mask变化。这里用min()而非预存，因unvisited列表通常很小（≤10），计算开销可忽略。

3.4 主搜索循环：剪枝逻辑的生死时速

主循环是分支限界的“心脏”，每一行都关乎性能生死。以下是经过23个真实项目锤炼的鲁棒实现：

import heapq from typing import List, Tuple, Optional def tsp_branch_and_bound(distances: List[List[float]], n: int) -> Tuple[List[int], float]: # Precompute MST lower bounds for all masks mst_lower_bound = precompute_mst_bounds(distances, n) # Priority queue: (lower_bound, current_city, mask, path_length, path_tuple) # Use tuple for path to make it hashable; convert to list at end pq = [] # Start from city 0, mask=1 (only city 0 visited), path=[0] heapq.heappush(pq, (0.0, 0, 1, 0.0, (0,))) best_cost = float('inf') best_path = [] # To avoid re-expanding same (curr, mask) with worse path_length # We store best path_length for each (curr, mask) best_path_length = {} while pq: lb, curr, mask, path_len, path_tuple = heapq.heappop(pq) # Prune 1: if lower bound already >= best known solution if lb >= best_cost - 1e-9: # account for float error continue # Prune 2: if we have a better path to this (curr, mask) state state_key = (curr, mask) if state_key in best_path_length and best_path_length[state_key] <= path_len: continue best_path_length[state_key] = path_len # If all cities visited, complete the tour if mask == (1 << n) - 1: total_cost = path_len + distances[curr][0] if total_cost < best_cost: best_cost = total_cost best_path = list(path_tuple) + [0] continue # Branch: try all unvisited cities for next_city in range(n): if mask & (1 << next_city): # already visited continue new_mask = mask | (1 << next_city) new_path_len = path_len + distances[curr][next_city] new_path_tuple = path_tuple + (next_city,) # Calculate lower bound for new state new_lb = calculate_lower_bound(next_city, new_mask, distances, n, mst_lower_bound) # Prune 3: if new_lb already >= best_cost, skip pushing if new_lb >= best_cost - 1e-9: continue heapq.heappush(pq, (new_lb, next_city, new_mask, new_path_len, new_path_tuple)) return best_path, best_cost

关键设计解析：

双重剪枝：lb >= best_cost（全局剪枝） +state_key记忆化（局部剪枝）。后者防止同一状态被多次探索，n=15时减少35%节点。
浮点容错：-1e-9避免因精度误差漏剪。我在金融计算中吃过亏：两个理论上相等的浮点数，因计算路径不同差1e-15，导致该剪的没剪，运行超时。
路径存储策略：用tuple而非list，因heapq要求元素可比较且不可变；path_tuple在最后转为list，避免中间频繁拷贝。
内存安全：best_path_length字典键为(curr, mask)，而非完整路径，将内存从O(2ⁿ·n)降至O(2ⁿ·n)，n=20时从GB级降至百MB级。

4. 实战避坑指南：那些只有踩过才懂的“幽灵bug”

4.1 浮点精度地狱：当0.1+0.2≠0.3毁掉整个剪枝

分支限界对数值稳定性极度敏感。最经典的坑是：if lb >= best_cost:看似简单，但在浮点世界里，lb可能因计算路径不同，比best_cost小一个ULP（最小精度单位），导致本该剪掉的分支被保留。我在一个卫星轨道优化项目中遇到：理论下界应为124.00000000000001，但计算得124.00000000000000，>=判断失败，算法多探索了2.7亿个节点，运行从8分钟飙升至17小时。

解决方案：

统一使用math.isclose(lb, best_cost, abs_tol=1e-9)替代>=
或更激进：所有距离、成本统一乘以1000转为整数（如毫米代替米），彻底消灭浮点误差。我在电路板钻孔项目中强制要求输入坐标为整数微米，限界计算全用int，剪枝100%可靠。

提示：在calculate_lower_bound中，min()函数返回的浮点数可能有精度漂移。实测发现，对同一unvisited列表，min([d1,d2,d3])和sorted([d1,d2,d3])[0]结果可能不同。统一用min()并加abs_tol容错。

4.2 内存泄漏：当Python的引用计数让你的堆爆掉

heapq存储大量(lb, curr, mask, path_len, path_tuple)元组，其中path_tuple随路径增长而变长。n=20时，平均路径长度10，path_tuple含10个整数，但Python元组对象本身有额外开销。更致命的是，heapq不自动清理已弹出节点的引用，若pq中堆积大量旧节点，GC可能来不及回收。

诊断方法：

用sys.getsizeof(pq)监控堆大小
用tracemalloc追踪内存分配源头

根治方案：

惰性路径重建：不在队列中存path_tuple，只存(curr, mask, parent_ref)，路径在找到解时通过parent_ref链表回溯。这使每个队列项内存从~200字节降至~40字节。
定期清理：在while pq:循环中，每处理10000个节点，执行pq = [(lb,c,m,pl) for (lb,c,m,pl) in pq if lb < best_cost]，然后heapq.heapify(pq)。虽有开销，但防内存雪崩。

4.3 搜索策略误判：当“最佳优先”变成“最慢优先”

最佳优先（Best-First）常被默认选用，但它有个隐藏陷阱：下界计算本身有开销，而低界值节点可能需要更复杂的计算才能确认是否可行。我在基因序列比对项目中观察到：算法疯狂探索下界为120.5的节点（计算MST需12ms），却忽略下界121.0但只需0.3ms就能验证可行的节点。结果，前10分钟都在算MST，没找到一个可行解。

对策矩阵：

场景	推荐策略	理由
需快速获得可行解（如实时系统）	深度优先（DFS）	快速抵达叶节点，生成首个`best_cost`
已有高质量启发式解（如贪心解f1=0.85）	Best-First + 启发式上界	用启发式解设`best_cost`初值，大幅提高剪枝率
多核环境，内存充足	并行BFS	每个worker负责一部分mask范围，用`multiprocessing.Manager`共享`best_cost`

我在物流调度系统中采用混合策略：启动时用DFS在2秒内获取best_cost=142.7，然后切换为Best-First，并设置timeout=30秒。实测比纯Best-First快4.2倍。

4.4 业务规则注入：当“数学最优”撞上“老板说不行”

算法最优解常被业务规则否决。比如TSP解要求“城市3必须在城市5之前访问”，或“路径总长不能超过100km”。硬编码到分支逻辑中极易出错。

工程化解法：

约束检查前置：在branch前，先调用is_feasible(new_state)验证业务规则。例如：

def is_feasible(curr, mask, next_city, path_tuple): # Rule: city3 before city5 if next_city == 5 and 3 not in path_tuple: return False # Rule: max distance 100km if path_len + distances[curr][next_city] > 100.0: return False return True

限界函数融合规则：将硬约束转化为下界惩罚项。如“城市3必须在5前”，可在calculate_lower_bound中，若mask含5不含3，则lb += 1e6（巨大惩罚），确保该分支被剪。

实操心得：所有业务规则必须有单元测试。我为某银行信贷审批系统写的分支限界，规则包括“同一行业客户不超过3家”、“抵押物估值波动率<15%”，专门写了27个边界case测试，覆盖mask的每一位组合，避免上线后因规则漏洞导致坏账。

5. 性能调优实战：从“能跑”到“秒出”的七步法

5.1 步骤1：基准测试——没有度量，就没有优化

在动手改代码前，先建立基线。用cProfile和line_profiler定位热点：

python -m cProfile -o profile_stats.pstats your_script.py # then in python: import pstats stats = pstats.Stats('profile_stats.pstats') stats.sort_stats('cumulative').print_stats(10)

典型瓶颈分布（n=18 TSP）：

42%：calculate_lower_bound中的min()计算
28%：heapq.heappush/pop
15%：precompute_mst_bounds（仅首次）
15%：路径元组拼接path_tuple + (next_city,)

注意：path_tuple + (next_city,)创建新元组，时间复杂度O(len(path))。n=18时平均路径长9，但高频调用，累积成大头。

5.2 步骤2：限界函数加速——用空间换时间

针对min()瓶颈，预计算min_out_cost和min_in_cost表：

# Precompute for all (curr, mask) pairs min_out_table = {} # (curr, mask) -> min distance from curr to unvisited in mask for curr in range(n): for mask in range(1 << n): unvisited = [i for i in range(n) if not (mask & (1 << i))] if unvisited: min_out_table[(curr, mask)] = min(distances[curr][i] for i in unvisited) else: min_out_table[(curr, mask)] = 0

内存增加O(n·2ⁿ)，但calculate_lower_bound中min_out查询从O(n)降至O(1)。n=18时，min_out_table占内存约12MB，但calculate_lower_bound总耗时从3.2s降至0.4s，提速8倍。

5.3 步骤3：堆操作优化——减少对象创建

heapq中每个元素是元组，Python元组创建有开销。改用array.array存储核心数据，自定义比较逻辑：

import array # Store: [lb, curr, mask, path_len, path_start_idx, path_length] # path data stored in separate array for cache locality heap_data = array.array('d', [0.0] * (max_nodes * 6))

但此法复杂度高，仅在n>25且性能极致要求时采用。对大多数项目，用dataclasses替代元组更实用：

from dataclasses import dataclass @dataclass class Node: lb: float curr: int mask: int path_len: float # path stored separately, only index here path_idx: int def __lt__(self, other): return self.lb < other.lb

__lt__方法比元组比较快15%，且内存更紧凑。

5.4 步骤4：并行化——让多核CPU真正干活

分支限界天然适合并行：不同子树独立探索。但需解决best_cost共享问题。multiprocessing.Manager有锁开销，我们用multiprocessing.Value：

best_cost_shared = multiprocessing.Value('d', float('inf')) # In worker process: if new_lb < best_cost_shared.value: # Try to update with best_cost_shared.get_lock(): if new_lb < best_cost_shared.value: best_cost_shared.value = new_lb

在32核服务器上，n=22 TSP，4进程比单进程快3.1倍（非线性，因通信开销）。

5.5 步骤5：缓存策略——别让CPU重复算同一个数

calculate_lower_bound中mst_lower_bound[mask]已是查表，但min_out_table可进一步优化：

使用functools.lru_cache装饰calculate_lower_bound，但需确保参数可哈希。mask是int，curr是int，完美适配。
设置maxsize=128000（覆盖n=18时所有mask），命中率>99.2%。

5.6 步骤6：编译加速——用Cython重写核心循环

对precompute_mst_bounds和calculate_lower_bound，用Cython重写：

# bounds.pyx def precompute_mst_bounds(double[:, :] distances, int n): cdef int mask, i, j cdef double[:, :] dist_view = distances # ... C-style loops

编译后，预计算时间从1.8秒降至0.07秒，提速25倍。但需权衡：开发时间增加3小时，维护成本上升。

5.7 步骤7：硬件感知——让算法贴合CPU缓存

现代CPU缓存行64字节。distances[i][j]若按行存储，访问distances[i]时，相邻j的值被预加载，但distances[j][i]（转置）可能跨缓存行。TSP中频繁访问distances[curr][next]，故确保距离矩阵按C顺序（行主序）存储。NumPy数组默认如此，但若用列表推导式[[... for j in range(n)] for i in range(n)]，则安全。

最后分享一个血泪经验：在某次GPU移植尝试中，我把distances传到CUDA kernel，结果因内存布局非连续，带宽利用率仅32%。改用np.ascontiguousarray(distances)后，提速2.8倍。算法再优，也架不住IO拖后腿。

6. 超越TSP：分支限界在真实世界的变形与延伸

6.1 整数规划（IP）：从组合优化到资源分配

TSP是分支限界的入门，但工业界更多是整数规划：min c^T x s.t. Ax ≤ b, x ∈ Z^n。分支策略变为“选择分数部分最接近0.5的变量x_k，分支为x_k ≤ floor(x_k*) 和 x_k ≥ ceil(x_k*)”。限界函数即解LP松弛。我在风电场机组启停优化中应用：变量x_i表示第i台机组是否开启（0/1），约束包括电网功率平衡、机组爬坡率、最小启停时间。分支限界在此场景的优势是：可嵌入“机组检修计划”等硬规则——当某台机组本周检修，则在分支时直接剪掉x_i=1的分支，无需修改求解器内核。

6.2 特征选择：机器学习中的隐形战场

在1000维特征中选20个最优子集，是典型的子集搜索。分支策略为“按信息增益排序，依次决定是否包含特征i”。限界函数用“当前子集的信息增益 + 剩余特征最大可能增益上界”。我在某医疗影像诊断模型中，用此法将特征数从1024降至17，AUC从0.821提升至0.849，且模型可解释性大增——医生能清楚看到“这17个影像纹理特征共同指向恶性肿瘤”。

6.3 游戏AI：从国际象棋到实时战略

Alpha-Beta剪枝是分支限界在博弈树中的特例。alpha是当前最大保证值（下界），beta是当前最小保证值（上界），alpha ≥ beta时剪枝。区别在于：博弈树中“限界”来自对手最优反击，需极大极小搜索。我在一个RTS游戏AI中，用分支限界优化单位编队：状态为(unit_types, resources, time_left)，限界为“剩余时间能建造的最大战力”，成功将微操响应时间从350ms降至42ms。