Backtracking

En un programa desarrollado usando el paradigma lógico, existe un “motor” que actúa como control de secuencia para separar el algoritmo de búsqueda de soluciones del conocimiento de cada programa.

Durante la ejecución de un programa va evaluando y combinando las reglas lógicas de la base de conocimiento para lograr los resultados esperados. La implementación del mecanismo de evaluación puede ser diferente en cada lenguaje del paradigma, pero en todos los casos debe garantizar que se agoten todas las combinaciones lógicas posibles para ofrecer el conjunto completo de respuestas alternativas posibles a cada consulta efectuada. El más difundido se denomina backtracking, que utiliza una estrategia de búsqueda de soluciones en estructuras de árboles denominada primero en profundidad.

El motor de Prolog usa el mecanismo de backtracking para encontrar soluciones a una consulta. Supongamos que tenemos la siguiente base de conocimientos:

hijo(homero,bart).
hijo(homero,maggie).
hijo(homero,lisa).

item(bart,patineta).
item(bart,gomera).
item(lisa,saxo).

copado(patineta).
copado(saxo).

itemCopadoDeHijo(Persona,Item):- 
  hijo(Persona,Hijo),
  item(Hijo,Item), copado(Item).

Si hacemos la consulta existencial:

?- itemCopadoDeHijo(P,I).`
P = homero, I = patineta;
P = homero, I = saxo;
false.

¿Cómo se llega a esa solución?

El motor hace la consulta hijo(Persona,Hijo) que tiene 3 respuestas posibles en base a nuestros hechos. Por cada una de esas soluciones posibles iniciales tendrá diferentes caminos por los cuales avanzar.

1)

2)

3)