Complexity of State-Space Search for Optimal Solutions

In the worst case, a state-space search algorithm must explore every node in a state space. Thus the worst-case complexity is linear in the size of the state space. On the other hand, if the lower-bound cost function used by the algorithm is exact, the complexity is linear in the length of the path from the initial node to a goal node. However, these extreme cases rarely occur and thus convey little information about the actual performance of an algorithm. Average-case complexity is therefore a more realistic performance measure. This chapter considers an average-case complexity of a state-space search algorithm. The main purpose of an average-case analysis is to find the relationship between the average-case complexity and the accuracy of lower-bound cost functions used by a search algorithm.