理学参数算法释 measure and conquer加权分治 一种算法分析方法（见算法分析）。最常见的解决NP难问题的精确算法就是分支算法（branching）。分支算法的思路非常直观：把问题分解成更小的子问题，然后逐个解决它们，最后将这些子问题的解合并成原问题的解。分支算法另一个常见的名称是搜索树算法（search tree algorithms）或剪枝算法（pruning search trees）。分支算法一般有两个主要步骤，一个是对实例进行处理，这一步通常是在多项式时间完成，它对实例进行简化，有可能在这一步就已经找到解或判定此实例；另一个是将一个实例分成多个更小的的实例。绝大部分分支算法的正确性都是一目了然的，因此主要难点在于它的时间分析。加权分治正是针对这个情况提出的一个分析方法。