También llamadas búsqueda a ciegas el término
significa que ellas no tienen información adicional acerca de los estados más
allá de la que proporciona la definición del problema. Todo lo que ellas pueden
hacer es generar los sucesores y distinguir entre un estado objetivo es “más
prometedor” que otro se llama búsqueda informada o búsqueda heurística. La
búsqueda no informada tiene las siguientes estrategias:
BUSQUEDA PRIMERO EN ANCHURA
La
búsqueda primero en anchura es una estrategia sencilla en la que se expande
primero el nodo raíz, a continuación se expanden todos los sensores del nodo
raíz, después sus sucesores, etc. La búsqueda primero en anchura se puede
implementar llamando a la búsqueda árboles con una frontera vacía que sea una
cola primero en entrar primero en salir (FIFO), asegurando que los nodos
primeros visitados serán los primeros expandidos. La cola FIFO pone todos los
nuevos sensores generados al final de la cola, lo que significa que los nodos
más superficiales se expanden antes que los nodos más profundos.
BUSQUEDA PRIMERO EN PROFUNDIDAD
La
búsqueda primero en profundidad siempre expande el nodo más profundo en la
frontera actual de árbol de búsqueda. La búsqueda procede inmediatamente al
nivel más profundo del árbol de búsqueda, donde los nodos no tienen ningún
sucesor. Cuando estos nodos se expanden, son quitados de la frontera, entonces
la búsqueda retrocede al siguiente nodo más superficial que todavía tenga
sucesores inexplorados. Esta estrategia puede implementarse por la búsqueda de
árboles con una cola último en entrar primero en salir (LIFO), es común aplicar
la búsqueda primero en profundidad con una función recursiva que se llama en
cada uno de sus hijos, esta tiene unos requisitos muy sencillos de memoria.
Necesita almacenar solo un camino desde la raíz a un nodo hoja, junto con los
nodos hermanos restantes no expandidos para cada nodo del camino.
Una variante de la búsqueda
primero en profundidad, llamada también búsqueda hacia atrás, utiliza aún menos
memoria, en esta solo se genera un sucesor a la vez; cada nodo parcialmente
expandido recuerda que sucesor se expande a continuación. El inconveniente de
la búsqueda primero en profundidad es que puede hacer una elección equivocada y
obtener un camino muy largo aun cuando una elección diferente llevaría a una
solución cerca de la raíz del árbol de búsqueda. (Russell, Norving, 2008).
CONCULUSION
la búsqueda una de las operaciones más sencillas y elementales en
cualquier estructura de datos, se han estandarizado el uso de estos
algoritmos para ello, por lo que se conocen como algoritmos de búsqueda.
Sin embargo, es importante resaltar que pueden utilizarse para
muchísimas otras operaciones con grafos que no necesariamente incluyan
la búsqueda de algún elemento dentro del grafo.
No hay comentarios:
Publicar un comentario