The Branching Factor of Regular Search Spaces

Abstract

Many problems, such as the sliding-tile puzzles, generate search trees where different nodes have different numbers of children, in this case depending on the position of the blank. We show how to calculate the asymptotic branching factors of such problems, and how to efficiently compute the exact numbers of nodes at a given depth. This information is important for determining the complexity of various search algorithms on these problems. In addition to the sliding-tile puzzles, we also apply our technique to Rubik's Cube. While our techniques are fairly straightforward, the literature is full of incorrect branching factors for these problems, and the errors in several incorrect methods are fairly subtle. Introduction Many AI search algorithms, such as depth-first search (DFS), depth-first iterative-deepening (DFID), and Iterative-Deepening-A* (IDA*) (Korf 1985) search a problem-space tree. While most problem spaces are in fact graphs with cycles, detecting these cycles in general req...