cienciasdelacomputacion.com

Algoritmo primero en profundidad

El algoritmo primero en profundidad funciona de la manera como lo muestra este esquema:

A continuacion, el algoritmo de busqueda Depth First:

Begin
open := [Start];
closed := [ ];
while open ? [ ] do
begin
remove leftmost state from open, call it X;
if X is a goal then returns SUCCESS
else begin
generate children of X;
put X on closed;
discard children of X if already on open or closed;
put remaining children on left end of open
end
end
return FAIL
end

A continuacion se muestra un arbol, el cual va a ser recorrido hasta encontrar el nodo U

La implementacion del algoritmo seria:

open = [A]; closed = [ ]
open = [B,C,D]; closed = [A]
open = [E,F,C,D]; closed = [B,A]
open = [K,L,F,C,D]; closed = [E,B,A]
open = [S,L,F,C,D]; closed = [K,E,B,A]
open = [L,F,C,D]; closed = [S,K,E,B,A]
open = [T,F,C,D]; closed = [L,S,K,E,B,A]
open = [F,C,D]; closed = [T,L,S,K,E,B,A]
Continua hasta encontrar U, o open = [ ].

Algoritmos de Generacion y Prueba y Breath First

Una mejora al algoritmo es asegurarse de que una solución no es probada más de una vez. Esto es sencillo si todas las soluciones son enumeradas – solo se deben probar en orden.
Si el conjunto de soluciones no se puede enumerar, otra alternativa es generar las soluciones de manera aleatoria, pero mantener una lista o arreglo con todas las soluciones probadas, y antes de probar una nueva.
El problema con esta alternativa es que toma mucho tiempo resolver un problema, la lista de soluciones probadas crece, y se podría estar invirtiendo mucho tiempo verificando si la solución fue probada antes.
Si el conjunto de soluciones posibles es grande – o infinita, lo mejor es generar las soluciones de manera aleatoria y sin verificar. La posibilidad de que una solución fue probada más de una vez es baja, y el consumo de tiempo en verificarlo es alto.

Breath First:

Algoritmo:

Begin
open := [Start];
closed := [ ];
while open ? [ ] do
begin
remove leftmost state from open, call it X;
if X is a goal then returns SUCCESS
else begin
generate children of X;
put X on closed;
discard children of X if already on open or closed;
put remaining children on right end of open
end
end
return FAIL
end

Busqueda Data driven(Conducida por datos)

Búsqueda empieza con los hechos o datos conocidos y un conjunto de movimientos legales o reglas para cambiar de estado.
La búsqueda se realiza aplicando las reglas a los datos o hechos, produciendo nuevos datos o hechos. Este proceso continua hasta generar una ruta que satisfaga la condición del objetivo.

Ddado que el sistema tiene que aprender a realizar una busqueda, esta generalmente se dara a ciegas, es decir no se conoce, por supuesto, donde se encuentra la informacion buscada. Por ende se han desarrollado estrategias de búsqueda a ciegas, como son:

• Generar y Probar
• Búsqueda primero a lo ancho
• Búsqueda primero a lo profundo
• Búsqueda de costo uniforme
• Búsqueda en profundidad limitada
• Búsqueda en profundidad iterativa
• Búsqueda bidireccional

GENERATE-AND-TEST (Generar y probar)

1. Generar una posible solución. (estado o camino)
2. Comprobar para ver si es una solución, mediante comparación con los elementos del conjunto de objetivos aceptables.
3. Si la solución ha sido encontrada salir, de otra manera, retornar al paso 1.