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 34:
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 para garantizar la mejor solución es la misma que en la búsqueda en anchura, es decir
 
<math>C = \cfrac{i^{n+1} - 1}{i - 1} </math>
 
La diferencia es que en este caso no tendremos certeza de haber encontrado la mejor solución hasta que se hayan expandido todas las ramas hasta el nivel de la mejor solución encontrada (siempre hablando de problemas con costo uniforme), y, aunque el problema tenga la mejor solución en un nivel n, el algoritmo podría explorar por otra rama hasta una profundidad mucho mayor, incluso indefinidamente, por lo cual la complejidad computacional en el peor de los casos está determinada por la profundidad a la cual se encuentra la solución más costosa de todas las ramas.
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, que aumentará en cada iteración. Esto evita el riesgo de internarse indefinidamente en una rama no finita, y evita también la necesidad de guardar pista de todos los nodos expandidos (sólo hace falta guardar los de la rama actual).
 
== Ventajas y desventajas ==
Línea 51:
= Búsqueda de costo fijo =
== Definición ==
Un algoritmo de búsqueda de costo fijo tiene asociada una función de costo que se aplica cada nodo, que representará el costo del mejor camino conocido para llegar desde el nodo inicial hasta el nodo en cuestión. El algoritmo de optimización deberá obtener el mejor camino entre el nodo inicial y un nodo caracterizado como el nodo de destino.
La expansión a realizar será la del nodo cuyo costo resulte menor,
== Complejidad computacional ==