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 52:
== 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.
Si el costo de los movimientos es uniforme, la búsqueda seguirá el mismo orden de expansiones que la búsqueda en anchura.
== Complejidad computacional ==▼
== La función de costo ==
La función de costo de un nodo representa el costo del mejor camino conocido para llegar desde el nodo inicial hasta el nodo. Para el nodo inicial deberá valer 0.
▲== Complejidad computacional ==
= Búsqueda heurística =▼
▲= Búsqueda heurística =
== Definición ==
El nodo que más conviene expandir es el nodo a través del cual pasa el camino con menor costo. Sería útil contar con la información del costo total del camino que significaría atravesar cada nodo. La búsqueda de costo fijo estima este valor con el costo parcial de llegar a este nodo. En muchos casos, esto no es suficiente. No se puede contar con el valor exacto, esto implicaría tener el problema resuelto. Lo que puede hacerse es estimar el costo desde el nodo actual hasta el nodo final, de manera de expandir primero el nodo a través del cual se estime que se llegará a la solución con costo óptimo.
== Complejidad computacional ==▼
== La función de costo ==
La función de costo es equivalente a la función de costo en la búsqueda de costo fijo.
== La función heurística ==
La función heurística debe estimar la función de costo desde el nodo actual hasta el nodo objetivo. Debe ser optimista, ya que si la estimación fuera superior al valor real, un nodo que llega a la solución óptima puede quedar excluido de la búsqueda. Mientras más se ajuste la heurística al valor real, se expandirán menos nodos innecesariamente.
▲== Complejidad computacional ==
|