A.3.4. Tipo de búsqueda
Poniendo en relación el modelo procesal descrito con los algoritmos generales para
la resolución de problemas podemos decir que:
- Se trata de una estrategia de búsqueda por descomposición en
subproblemas. Los árboles dibujados en las Figuras A.4 a A.10 son
representaciones abreviadas de árboles de búsqueda AND/OR. Así, el árbol
AND/OR para el proceso de la Figura A.7 sería el de la Figura A.11.
- Es una estrategia de búsqueda en profundidad (depth–first) con retroceso
(backtracking).
- Es una búsqueda a ciegas. Los heurísticos son dependientes del tipo de problema
concreto para el que se escribe el programa, y Prolog pretende ser un
lenguaje para cualquier tipo de problema. La satisfacción de restricciones
es un tipo particular e importante de problemas, para el que se pueden
introducir heurísticos específicos, como comentaremos en el Apartado
siguiente.
En cualquier caso, Prolog permite que se pueda alterar su estrategia de búsqueda. En
el Apartado A.4.2 veremos cómo puede expresarse en Prolog el conocimiento
algorítmico para el problema de la ordenación de datos. De modo similar,
es posible expresar el conocimiento de las distintas estrategias de búsqueda,
incluyendo los heurísticos, y realizar programas que las sigan. A esto se le llama
metaprogramación, y el lector interesado puede acudir, por ejemplo, al libro de Bratko
(2001) [7],
DIT-ETSIT-UPM