Diferencia entre revisiones de «Estructuras de datos dinámicas/Algoritmos de búsqueda»

Contenido eliminado Contenido añadido
Rgfernan (discusión | contribs.)
Sin resumen de edición
Rgfernan (discusión | contribs.)
Sin resumen de edición
Línea 15:
= Búsqueda en profundidad =
== Definición ==
Un algoritmo de búsqueda en profundidad recorre todos los nodos de un grafo o árbol de manera ordenada, pero no uniforme. Consiste en ir expandiendo cada uno de los nodos a medida que los encuentra, empezando siempre por el primer nodo hijo no visitado del nodo actual; cuando ya no quedan más nodos hijos que visitar en el actual, regresa (backtracking), y el padre del nodo pasa a ser el nodo actual.
El criterio de camino agotado debe ser elegido cuidadosamente, de manera de evitar la expansión indefinida de nodos. Asimismo, para garantizar la convergencia, en muchos casos debe evitarse la expansión de nodos repetidos, al menos en un mismo camino.
== Ventajas y desventajas ==
Línea 24:
= Búsqueda en anchura =
== Definición ==
Un algoritmo de búsqueda en anchura recorre todos los nodos de un árbol de manera uniforme. Expande cada uno de los nodos de un nivel antes de continuar con el siguiente.
== Complejidad computacional ==
Si la solución se encuentra en el nivel n, y la cantidad máxima de hijos de un nodo es i, habrá que expandir, en el peor de los casos, la cantidad de nodos de un árbol de orden i y de altura n:
 
<math>C = \cfrac{i^{n+1} - 1}{i - 1} </math>
 
 
= Búsqueda en profundidad iterativa =