Diferencia entre revisiones de «Estructuras de datos dinámicas/Algoritmos de búsqueda»
Contenido eliminado Contenido añadido
Nueva página: = Introducción = Los algoritmos de búsqueda que se exponen a continuación se aplican a o árboles. Como se verá, muchos problemas pueden modelarse de manera de generar un árbol c... |
Sin resumen de edición |
||
Línea 1:
= Introducción =
Los algoritmos de búsqueda que se exponen a continuación se aplican a
== Definiciones ==
=== Criterio de parada ===
Es el criterio que se toma para decidir que la búsqueda ha llegado a su fin. En este punto se puede devolver una solución, o determinar que no hay solución posible.
=== Criterio de camino agotado ===
Es el criterio que se toma para decidir que la búsqueda desde el nodo actual no puede llevar a una solución, de manera que, de quedar otros caminos posibles, debería continuar por alguno de ellos.
=== Expansión de nodos repetidos ===
Frecuentemente, en los problemas que se modelan, es posible llegar a una solución posible o intermedia a través de varios caminos. Esto hace que un algoritmo de búsqueda pueda generar más de una vez el mismo nodo. Los problemas que devienen de la expansión reiterada de un mismo nodo van desde una ligera carga extra hasta la no convergencia del algoritmo, dependiendo de la naturaleza del problema y del algoritmo utilizado.
=== Aristas de costo negativo ===
= 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 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 ==
Expandir un camino hasta su máxima profundidad puede ser útil para acotar la solución en problemas de optimización. Esto es, si se ha encontrado una solución posible con determinada valoración, no se admitirá expandir nodos con una valoración peor, y así el algoritmo puede ir eliminando ramas sin la carga de procesamiento de recorrerlas.
== Complejidad computacional ==
Línea 13 ⟶ 22:
== Definición ==
== Complejidad computacional ==
= Búsqueda en profundidad iterativa =
= Búsqueda de costo fijo =
| |||