Diferencia entre revisiones de «Estructuras de datos dinámicas/Algoritmos de búsqueda»
Contenido eliminado Contenido añadido
Sin resumen de edición |
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
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 =
|