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.

Reprinted in Readings in Planning, edited by J. Allen, J. Hendler, and A. Tate, Morgan Kaufmann Publishers, San Mateo, California, 1990. Also Reprinted in Computation and Intelligence: Collected Readings, edited by George F. Luger, AAAI Press, 1995. See also: Artificial Intelligence, Volume 2, Issues 3–4, Winter 1971, Pages 189–208 In IJCAI-71: INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE. British Computer Society, London.. Revised version in Artificial Intelligence, 2(3), pp 189-208.