[科普中国]-分支因子

在计算机运算、树数据结构、博弈论领域中，分支因子（branching factor）是每个结点下的子结点数，即出度。如果各个结点分支因子不同，则可以计算平均分支因子。例如，在国际象棋中，如把一步合法走法算作一个“结点”，那么平均分支因子据信约为35。这表示，棋手每一步走棋平均有大约35种合法走法。相比之下，围棋的分支因子为250。

简介分支因子有多种解释，在计算机运算中，分支因子是指从一步运算进行下一步运算有多种选择。在数据结构中，树由称为结点的元素按照层次结构的方式组织而成。层次结构最顶端的结点称为根。与根结点直接相连的结点称为根的子结点，通常子结点本身也有属于它们自己的子结点。除了根结点外，在这个层次体系中的每个结点都有单一的父结点，也就是与其直接相连的上级结点。一个节点拥有多少个子节点取决于树的类型，这个量值称为树的的分支因子，它决定了当插入结点时树的分支扩展的速度。

一般来说，图可分为有向图和无向图。有向图的所有边都有方向，即确定了顶点到顶点的一个指向；而无向图的所有边都是双向的，即无向边所连接的两个顶点可以互相到达。在一些问题中，可以把无向图当作所有边都是正向和负向的两条有向边组成。顶点的度是指和该顶点相连的边的条数。特别是对于有向图来说，顶点的出边条数称为该顶点的出度1，也可称为分支因子。

因结点数呈指数增长，所以分支因子越大，需要遍历所有分支的算法（如暴力搜索法）的计算量越大。例如，若分支因子为10，则当前位置下一层会有10个结点，下两层会有102即100个结点，下三层会有103即1,000个结点，依此类推。分支因子越大，指数爆炸越快。剪枝算法可以减小分支因子。

指数增长指数增长（包括指数衰减）指一个函数的增长率与其函数值成比例。在定义域为离散的且等差的情况下，也称作几何增长或几何衰减（函数值是一个等比数列）。或指在某一阶段时间内，应用于持续增 长的基数上的不变的增长率。例如，以复利比例增长的储蓄账目；越集越 大的雪球；以年平均3%的速度增长的人口等。指数增长模型也称作马尔萨斯增长模型。

剪枝剪枝，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。剪枝优化三原则: 正确、准确、高效的原则搜索算法，绝大部分需要用到剪枝。然而，不是所有的枝条都可以剪掉，这就需要通过设计出合理的判断方法，以决定某一分支的取舍。 在设计判断方法的时候，需要遵循一定的原则。

正确性

枝条不是爱剪就能剪的。 如果随便剪枝，把带有最优解的那一分支也剪掉了的话，剪枝也就失去了意义。 所以，剪枝的前提是一定要保证不丢失正确的结果。

准确性

在保证了正确性的基础上，我们应该根据具体问题具体分析，采用合适的判断手段，使不包含最优解的枝条尽可能多的被剪去，以达到程序“最优化”的目的。 可以说，剪枝的准确性，是衡量一个优化算法好坏的标准。

高效性

设计优化程序的根本目的，是要减少搜索的次数，使程序运行的时间减少。 但为了使搜索次数尽可能的减少，我们又必须花工夫设计出一个准确性较高的优化算法，而当算法的准确性升高，其判断的次数必定增多，从而又导致耗时的增多，这便引出了矛盾。 因此，如何在优化与效率之间寻找一个平衡点，使得程序的时间复杂度尽可能降低，同样是非常重要的。 倘若一个剪枝的判断效果非常好，但是它却需要耗费大量的时间来判断、比较，结果整个程序运行起来也跟没有优化过的没什么区别，这样就太得不偿失了。

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学