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
Sin resumen de edición
Línea 10:
=== 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.
Si debe evitarse la expansión repetida, deberá guardarse pista de los nodos ya expandidos. En algunos casos, tales como una búsqueda en profundidad que genere un número limitado de nodos, pero que puedan repetirse, pueden generarse bucles en una rama, de manera que para evitarlos, sólo se debe guardar pista de los nodos expandidos en la rama atual.
=== Aristas de costo negativo ===
Una arista de costo negativo, en la semántica del problema, significará que uno de los pasos posibles en el camino de una solución, contribuye mejorar solución.
Esto es un problema para los algoritmos que evitan caminos del árbol de búsqueda basándose en el costo que tiene alcanzar cada nodo, porque esto no prevé que en futuros pasos la función costo puede mejorar.
= 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>
 
Por lo tanto, tanto el tiempo de procesamiento como el requerimiento de memoria tendrán un orden exponencial, tanto si evita o no expansiones repetidas.
== Ventajas y desventajas ==
Expandir los nodos de forma uniforme garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna, de manera que apenas se encuentre una solución, puede devolverse, porque será la mejor, o bien expandir todo el nivel en el cual se hubiere encontrado, parta obtener todas las soluciones posibles.
 
La desventaja principal es el alto orden de complejidad computacional, que hace que, de no mantenerse muy limitados los parámetros i y n del problema, crezcan rápidamente los requerimientos y se vuelvan inaceptables.
= Búsqueda en profundidad =
== Definición ==
Línea 18 ⟶ 32:
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. Además, el requerimiento de memoria es limitado, aun si se garantiza que no cicle, ya que sólo hace falta guardar los datos de la rama actual.
 
== Complejidad computacional ==
La cantidad mínima de nodos a ser expandidos es la misma que en la búsqueda en anchura, es decir
 
= 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>
 
La diferencia es que
 
= Búsqueda en profundidad iterativa =
== Definición ==
Un algoritmo de búsqueda en profundidad iterativa recorre los nodos de un árbol en profundidad, pero con un valor de profundidad restringido
 
== Ventajas y desventajas ==
La búsqueda en profundidad iterativa aprovecha ventajas de la búsqueda en anchura y de la búsqueda en profundidad:
* El requerimiento limitado de memoria.
* La uniformidad al expandir los nodos, que garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna.
 
= Búsqueda de costo fijo =