Seminario de sistemas

...

Permítanme mostrarles un algoritmo de búsqueda muy básico conocido como la Búsqueda Inicial en Profundidad (haga click para ver la imagen).

Este programa le permite a usted encontrar un camino de solución desde el punto de INICIO hasta alguna META. El algoritmo BIP es muy simple de implementar, ya que es un algoritmo recursivo. Lo que el algoritmo BIP hace es ir a través del hijo de cada nodo en una manera secuencial, por consiguiente aunque es una forma muy fácil de implementar un algoritmo de búsqueda, no es eficiente con respecto al tiempo.

Pero... ¿Por qué buscar un grafo?

Los nodos de un grafo corresponden a los estados parciales de la solución del problema y los arcos corresponden a los pasos del proceso de resolución de problemas. El grafo además define una o más condiciones para la meta, las cuales son soluciones para una instancia del problema. El proceso de encontrar un camino de solución desde el inicio hasta la meta es llamado Estado en un Ámbito de Búsqueda (Luger y Stubblefield 1997).

A través de un grafo usted puede encontrar las soluciones a varios problemas que en su mente parecen muy fáciles. Por ejemplo, un juego completo de ajedrez puede ser representado con grafos, problemas matemáticos, virtualmente cualquier cosa que involucre una toma de decisiones.

El siguiente programa es la representación en Prolog del grafo que está más arriba.

=========LISTA #1=============

% Nombre: Anderson Silva

% Fecha : Marzo 10, 1999

% ========================================

% Un grafo que será usado por un

% Algoritmo de Búsqueda Inicial en

% Profundidad en la Base de Conocimientos.

% ========================================

% linked/2

% Un nodo y sus hijos

linked(a, [b,c,d]).

linked(b, [e,f]).

linked(c, [g,h]).

linked(d, [i,j]).

linked(e, [k,l]).

linked(f, [l,m]).

linked(g, [n]).

linked(h, [o,p]).

linked(i, [p,q]).

linked(j, [r]).

linked(k, [s]).

linked(l, [t]).

linked(m, []).

linked(n, []).

linked(o, []).

linked(p, [u]).

linked(q, []).

linked(r, []).

linked(s, []).

linked(t,