En búsqueda
en profundidad se recorren todos los nodos del árbol o grafo, de manera
ordenada; se trata de ir expandiendo cada uno de los nodos
que va encontrando en el camino, y se queda allí, sin
repetir ninguno de los nodos ya visitados, en el momento que éste encuentra un
nodo hoja, retrocede al nodo anteriormente visitado y avanza desde éste.
La
búsqueda en profundidad no es un algoritmo óptimo, ya que no encuentra la mejor
solución, y tampoco es un algoritmo completo, porque en caso tal de que
encuentre ciclos, el algoritmo se quedara infinitamente allí, sin encontrar
ninguna solución.
Algoritmo
de búsqueda en profundidad:
En
el siguiente ejemplo, se pide para el juego de los sapos y las ranas,
formalizarlo como un problema de búsqueda y aplicarte la búsqueda por profundidad.
Con
la búsqueda en profundidad, se puede observar que en el momento que se tome un
ciclo, se puede quedar allí de manera infinita, ya que al realizar la búsqueda,
se hace siempre siguiendo paso a paso el algoritmo, por lo tanto dependiendo de
nodo que se tome, y sin guiar la búsqueda, se puede encontrar, o no la
solución.
No hay comentarios:
Publicar un comentario