正则搜索树的分支因数

Branching Factor of Regular Search Trees

正则搜索树的分支因数对算法的复杂度有决定性影响。尤其在深度优先的启发式搜索中,决定时间复杂度的启发式分布与分支因数紧密相关。本文介绍两种分支因数的计算方法:数值法与解析法。在数码难题及鲁比克魔方这两类实际的问题空间上,用这两种方法可获得相同结果。这些结果是进一步研究算法时间复杂度的必要基础。

The branching factor of a regular search tree has a decisive effect on the time complexity of a search algorithm. It is closely relative to the equilibrium distribution that is necessary to determine the time complexity. In this paper, we present both analytic and numerical techniques for computing the exact number of nodes at a given depth, and determining the asymptotic branching factor. We give the branching factor of Ruble's Cube and Sliding-tile Puzzles from the Five Puzzle to the Ninety-Nine Puzzle.