En Prolog, el Backtracking se conoce como el mecanismo automático del motor de inferencia que busca todas las soluciones posibles a una consulta probando distintas rutas y volviendo atrás cuando un camino falla.
Un programa Prolog puede considerarse como la descripción de un árbol.
Cada vértice del árbol añade una restricción del tipo "esta variable debe ser igual a este término", donde un término es una variable o una estructura compuesta por una constante seguida de cero o más sub términos (existe otro tipo de vértice que indica "no debe haber solución para este subárbol").
Cada rama del árbol describe un camino posible diferente para llegar a una solución. Una solución es un conjunto coherente de restricciones sobre las variables que van desde el vértice raíz hasta una hoja del árbol.
Entendiendo el Backtracking
Prolog, además de considerarse como la descripción de un árbol, también es un motor de búsqueda.
En otras palabras, el Backtracking consiste en explorar múltiples soluciones posibles, probando sistemáticamente alternativas y deshaciendo las decisiones cuando una ruta falla.
Busca entre los hechos que se le proporcionan y se adhiere a las reglas que se le proporcionan. A veces, tanto los hechos como las reglas pueden tener alternativas.
¿Cómo funciona este mecanismo?
- Prolog lee las reglas y los hechos uno a uno de arriba a abajo, esto sería la exploración.
- Cuando encuentra varias opciones para un objetivo, guarda un punto de parada, que sería los puntos de elección.
- Si un camino falla o el usuario pide más respuestas, Prolog vuelve al último punto y prueba la siguiente opción disponible, backtracking.
- El proceso se detiene cuando halla una solución o agota todas las combinaciones posibles, finaliza.
Ejemplo 1. Definiendo una base de conocimientos sobre los gustos de comida de distintas personas, vamos a encontrar a la persona o persona que le guste lo dulce. Si hay varias opciones o la primera no satisface otra condición, Prolog retrocederá para probar la siguiente.
gustos.pl
% Hechos: gustos(Persona, Comida) gusta(ana, pizza). gusta(ana, chocolate). gusta(ignacio, manzana). gusta(ignacio, chocolate). gusta(ignacio, helado). gusta(ana, cebolla). gusta(nadia, papas). % Regla para buscar quién prefiere un dulce es_dulce(chocolate). es_dulce(manzana). es_dulce(helado). persona_con_dulce(Persona, Comida) :- gusta(Persona, Comida), es_dulce(Comida).
Ahora cargamos el programa:
$ swipl 1 ?- [gustos].
Consultamos:
2 ?- persona_con_dulce(nadia,Comida). false.
Nadia no es la persona a la que le gusta lo dulce. Probemos con otra consulta:
3 ?- persona_con_dulce(ana,Comida). Comida = chocolate ; false.
Ana tiene gusto por el chocolate, que es dulce, pero no cumple con la regla en su totalidad. Ahora con otra consulta:
4 ?- persona_con_dulce(ignacio,Comida). Comida = manzana ; Comida = chocolate ; Comida = helado.
Ignacio es la persona a la que le gusta la comida dulce.
Prolog comienza con la primera cláusula que coincide con la consulta e intenta satisfacer sus objetivos. Si tiene éxito, devuelve una respuesta. Si falla, vuelve al punto de elección anterior e intenta la siguiente cláusula. Este proceso continúa hasta que se agoten todas las cláusulas o se encuentre una solución.
Podríamos extender está explicación, pero por el momento será todo.
Seguiremos con este tema y otros en próximas entregas.
Enlaces:
https://blog.adrianistan.eu/introduccion-a-prolog-tutorial-en-espanol/https://www.ecured.cu/Vuelta_atr%C3%A1s_(backtracking)
https://www.tutorialspoint.com/prolog/prolog_backtracking.htm
https://wiki.uqbar.org/wiki/articles/backtracking.html
https://www.linkedin.com/advice/1/how-can-you-use-prolog-efficiently-handle-backtracking-eaqbc?lang=es&lang=es&originalSubdomain=es
Comentarios
Publicar un comentario