Búsquedas por profundidad
La búsqueda en profundidad, llamada DepthFirstSearch en inglés, es un algoritmo usado para recorrer o buscar elementos en un árbol o un grafo y pertenece al grupo de las búsquedas no informadas (sin heurísticas). Su procedimiento consiste en visitar todos los nodos de forma ordenada pero no uniforme en un camino concreto, dejando caminos sin visitar en su proceso. Una vez llega al final del camino vuelve atrás hasta que encuentra una bifurcación que no ha explorado, y repite el proceso hasta acabar el árbol (esto se conoce como Backtracking). En la siguiente figura mostramos el orden de visita, siendo los números en naranja dicho orden:
En cada llamada recursiva marcaremos el nodo actual como visitado y luego verificamos si es el nodo buscado para salir de la recursión, este será nuestro caso base. De no ser el nodo requerido, se hace la llamada recursiva con todos los nodos hijos del nodo actual, pero en este caso, a diferencia del recorrido BFS, no se visitarán todos los hijos de forma consecutiva, sino que el algoritmo recorrerá en profundidad hasta llegar a un nodo extremo o nodo hoja, antes de retornar al ambiente de recursión en donde se encuentran los otros nodos hijos. El orden en que se eligen las ramas en un recorrido DFS está determinado por el tipo de recorrido de procesamiento de árbol que se haya elegido, estos pueden ser:
- Pre-orden: Se procesa primero la raíz, luego la rama izquierda y luego las ramas siguientes hasta llegar a la que se encuentra más a la derecha.
- Post-orden: Se procesa el árbol desde las ramas izquierdas hasta la que se encuentra más a la derecha. Finalmente se procesa el nodo raíz
- Simétrico o In-orden: Se procesa la rama de la izquierda, luego el nodo raíz y luego la rama derecha.
Aplicado al caso del Problema de las jarras:
En el caso del problema de las jarras, se genera el siguiente grafo de búsqueda en profundidad:
Este grafo de búsqueda por profundidad nos denota la
siguiente tabla de búsqueda en profundidad:
Estados de la solución: ((2 3) (4 1) (0 1) (1 0) (1 3) (4 0) (0 0))
Búsquedas por anchura
La búsqueda en anchura (o búsqueda en amplitud), llamada BreadthFirstSearch en inglés, es un algoritmo usado para recorrer o buscar elementos en una estructura de datos como los árboles y los grafos.Pertenece al grupo de las búsquedas no informadas(sin heurísticas). Su procedimiento consiste en ir visitando todos los nodos de un nivel antes de proceder con el siguiente nivel tal y como mostramos en la siguiente figura (los números en naranja indican el orden de exploración de los nodos):
De modo que lo primero que hará será visitar la raíz, luego los hijos de la raíz, luego los hijos de cada uno de estos hijos y así sucesivamente.
Aplicado al caso del Problema de las jarras:
En el caso del problema de las jarras, se genera el
siguiente grafo de búsqueda en anchura:
Este grafo de búsqueda por anchura nos denota la
siguiente tabla de búsqueda en anchura:
0 comentarios: