Summary: The evaluation function \(\hat f\) used in heuristic search algorithms commonly has the form \(\hat f(n)=\hat g(n)+\hat h(n)\), where n is any node in the network, \(\hat g(n)\) is the cost of the best path currently known from the start node to n, and \(\hat h(n)\) is the heuristic estimate associated with node n. A more general form of the evaluation function can be obtained by incorporating a weighting parameter \(\alpha: \hat f(\alpha,n)= (1-\alpha)\hat g(n)+ \alpha \hat h(n)\), where \(0\leq \alpha \leq 1\). Such an evaluation function has been used in some recent experimental investigations of the 8-puzzle problem. In this paper a theoretical framework is developed for the analysis of the worst-case behavior of weighted heuristic search algorithms. A new algorithm is proposed whose worst-case performance characteristics are greatly superior to those of earlier algorithms in terms of the following two measures: how good is the solution, and how many nodes are expanded. Bounds are also obtained on some useful network parameters for both general and special types of heuristic estimate functions.