The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem solving

TLDR

Heuristic problem solving demands careful attention to computational efficiency. The paper presents the HPA system, designed to find near‑optimal solutions to the traveling salesman problem. HPA introduces dynamic weighting of heuristic information, inversely proportional to search‑tree depth, yielding a narrower depth‑first search than traditional weightings. Dynamic weighting preserves catastrophe protection typical of branch‑and‑bound algorithms.

Abstract

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.