cienciasdelacomputacion.com

Algoritmo primero a lo Ancho

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