分支定界 vs A*：资源约束项目调度中的搜索算法对决

在资源约束项目调度（RCPSP）这一经典组合优化问题上，来自运筹学的分支定界（B&B）与来自人工智能的A*算法长期各自发展，却共享着相似的搜索哲学。一项最新研究通过系统性实验揭示了两种方法在相同条件下的性能差异，并指出了重复状态检测在精确搜索中的关键作用。

两种搜索范式的碰撞

分支定界和A分别根植于运筹学与人工智能两个领域。B&B通常通过分支策略和界限剪枝来逐步缩小搜索空间，而A则依赖启发式函数引导的最优优先搜索。尽管二者在理论上都属于精确搜索方法，但它们在探索状态空间时的具体机制——尤其是对重复状态的处理方式——可能导致计算性能的显著差异。

这项研究以RCPSP作为测试场景，首先建立了混合整数线性规划（MILP）、状态-动作表示与时间Petri网表示之间的形式化关系。这种表示层面的统一，为在同等条件下比较两种算法奠定了基础。

重复状态检测（Duplicate State Detection） 是图搜索算法中的一项关键技术，用于识别并避免对已经访问过的状态进行重复探索。在状态空间搜索中，不同的决策序列（或路径）可能到达完全相同的状态，若不加检测，算法会多次展开同一状态，导致冗余计算甚至指数级的时间浪费。A*算法通常维护一个“闭集”（closed set）来记录已扩展的状态，确保每个状态最多被处理一次；而基础的分支定界实现往往缺乏显式的闭集机制，仅依赖界限剪枝，因此可能反复探索等价状态。在资源约束项目调度中，由于调度决策的顺序灵活性，等价状态的出现极为频繁，重复状态检测的缺失会显著削弱搜索效率。

隔离搜索机制的影响

为了聚焦于搜索机制本身的差异，研究团队有意采用了相对基础的算法实现，而非当前最先进的求解器。他们使用了相同的下界和最佳优先节点选择策略，从而将比较重点放在搜索机制上，特别是对不同调度决策序列到达的等价状态识别能力上。

这种控制变量的实验设计使得研究者能够观察到：当底层边界和节点选择逻辑一致时，搜索图的结构差异如何影响整体性能。

线性规划松弛（Linear Programming Relaxation） 是分支定界中常用的下界增强技术。其基本思想是暂时放松原混合整数规划问题中的整数约束，将问题转化为一个线性规划问题求解，所得最优值即为原问题的一个下界。松弛越紧（即下界越接近真实最优值），分支定界需要探索的节点就越少。然而，更强的松弛通常意味着每次求解线性规划的开销更大，且可能涉及更复杂的约束生成。文章指出，这种计算开销有时会抵消搜索空间缩小带来的收益，因此单纯增强下界并不必然提升整体性能。

A*在基准测试中的优势

在480个基准RCPSP实例上的实验结果显示，基于图的A算法显著优于所考虑的分支定界变体。在相同的时间和内存限制下，A能够为全部480个实例证明最优性，而最佳优先B&B仅能为445个实例完成证明。

这一差距主要归因于A在搜索过程中对重复状态的检测能力——当不同的调度决策序列导致相同状态时，A能够通过闭集机制避免重复探索，而基础B&B实现往往缺乏这种机制。

深度优先与内存权衡

研究同时揭示了不同B&B变体的特性差异。深度优先B&B虽然占用内存更少，并且即使在时间限制内未完成搜索时也能找到可行解，但其非最优优先的探索顺序可能导致在证明最优性方面效率较低。

另一方面，更强的线性规划松弛虽然能够缩小搜索空间，却引入了不可忽视的计算开销。这种权衡表明，单纯依靠增强下界并不总能带来整体性能的提升。

跨领域融合的启示

这项工作的核心价值在于澄清了两种搜索方法之间的计算权衡，并为研究者选择合适方法提供了依据。重复状态检测的重要性在两个社区中尚未得到同等重视，而实验表明它可能是决定性能的关键因素之一。

研究者建议，未来的工作可以探索如何将一种方法中的有效机制（如A*的重复状态检测或B&B的内存效率策略）融入另一种方法中，从而在资源约束调度及其他组合优化问题上取得更好的平衡。