Posts Tagged ‘primero a lo ancho’
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