Apache KIE OptaPlanner 中的穷举搜索算法详解
穷举搜索概述
穷举搜索(Exhaustive Search)是Apache KIE OptaPlanner项目中的一种优化算法，它能够保证找到全局最优解并准确识别。然而，这种算法存在严重的可扩展性问题，即使对于玩具数据集(toy data set)也难以应对，因此在真实场景中几乎无法使用。
暴力搜索(Brute Force)
算法原理
暴力搜索算法会生成并评估每一个可能的解决方案。它构建了一个搜索树，随着问题规模的增加，这个搜索树会呈指数级爆炸式增长，很快就会遇到可扩展性的瓶颈。
重要提示：由于时间限制，暴力搜索在现实世界问题中基本不可用，这一点在"穷举搜索的可扩展性"部分有详细说明。
配置方法
暴力搜索的最简配置如下：
<solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
...
<exhaustiveSearch>
<exhaustiveSearchType>BRUTE_FORCE</exhaustiveSearchType>
</exhaustiveSearch>
</solver>
分支定界(Branch and Bound)
算法原理
分支定界算法同样会探索指数级增长的搜索树节点，但它会优先调查更有希望的节点，并剪枝掉无价值的节点。
对于每个节点，算法会计算乐观边界(optimistic bound)：该节点可能达到的最佳分数。如果某个节点的乐观边界低于或等于全局悲观边界(pessimistic bound)，则该节点(包括其所有子节点分支)将被剪枝。
技术说明：学术论文通常使用"下界"(lower bound)代替"乐观边界"，"上界"(upper bound)代替"悲观边界"。由于OptaPlanner是最大化分数(支持结合正负约束)，为避免混淆，使用了不同的术语。
重要提示：与暴力搜索类似，分支定界在现实世界问题中也基本不可用，原因同样是时间限制。
配置方法
分支定界的最简配置：
<solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
...
<exhaustiveSearch>
<exhaustiveSearchType>BRANCH_AND_BOUND</exhaustiveSearchType>
</exhaustiveSearch>
</solver>
关键配置要点：要使剪枝生效，需要设置InitializingScoreTrend。特别是当趋势设置为ONLY_DOWN(或至少在前导分数级别中包含ONLY_DOWN)时，可以剪枝大量节点。
高级配置选项包括：
-
节点探索类型(nodeExplorationType)：
DEPTH_FIRST(默认)：深度优先探索BREADTH_FIRST：广度优先探索(不推荐)SCORE_FIRST：优先探索分数更高的节点OPTIMISTIC_BOUND_FIRST：优先探索乐观边界更好的节点
-
实体排序方式(entitySorterManner)：
DECREASING_DIFFICULTY：先初始化难度更大的规划实体DECREASING_DIFFICULTY_IF_AVAILABLE(默认)NONE：按原始顺序初始化
-
值排序方式(valueSorterManner)：
INCREASING_STRENGTH：按强度递增评估规划值INCREASING_STRENGTH_IF_AVAILABLE(默认)DECREASING_STRENGTH：按强度递减评估DECREASING_STRENGTH_IF_AVAILABLENONE：按原始顺序尝试
穷举搜索的可扩展性
穷举搜索存在两大可扩展性问题：
- 内存消耗呈灾难性增长
- 性能表现急剧下降
基准测试显示，无论是暴力搜索还是分支定界，都会很快遇到性能瓶颈。例如，在N皇后问题中，几十个皇后就会触及性能墙；在云平衡问题中，这个墙会突然出现。
实际应用建议：在生产环境中，穷举搜索算法基本无用。建议改用构造启发式算法配合局部搜索，这些方法可以轻松处理数千个皇后/计算机的规模问题。
硬件限制说明：增加硬件资源对这些可扩展性问题几乎没有明显改善。摩尔定律在面对规划实体数量增加时完全无能为力。
