Weighted heuristic search in networks |
| |
Authors: | A Bagchi P K Srimani |
| |
Institution: | Indian Institute of Management Calcutta, P.O. Box 16757, Calcutta-700 027, India |
| |
Abstract: | The evaluation function
used in heuristic search algorithms commonly has the form
, where n is any node in the network,
is the cost of the best path currently known from the start node to n, and
is the heuristic estimate associated with node n. A more general form of the evaluation function can be obtained by incorporating a weighting parameter α: , where 0≤ α ≤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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|