The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving
Ira Pohl · International Joint Conference on Artificial Intelligence · 1973
To solve difficult problems heuristically, requires detailed attention to computational efficiency. This paper describes how a heuristic problem solving system, HPA, attempts to find a near optimal solution to the traveling salesman problem. A critical innovation over previous search algorithms is an explicit dynamic weighting of the heuristic information. The heuristic information is weighted inversely proportional to its depth in the search tree -- in consequence it produces a narrower depth first search than traditional weightings. At the same time, dynamic weighting retains the catastrophe protection of ordinary branch and bound algorithms.