Una base formal para la determinación heurística de caminos de costo mínimo

Aunque el problema de determinar el camino de costo mínimo a través de un grafo surge naturalmente en varias aplicaciones interesantes, no ha existido una teoría subyacente para guiar el desarrollo de procedimientos de búsqueda eficientes. Además, no existe un marco conceptual adecuado dentro del cual se puedan comparar las diversas estrategias de búsqueda ad hoc propuestas hasta la fecha. Este artículo describe cómo la información heurística del dominio del problema puede incorporarse en una teoría matemática formal de búsqueda en grafos y demuestra una propiedad de optimalidad de una clase de estrategias de búsqueda.