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 2:
Los algoritmos de búsqueda que se exponen a continuación se aplican a árboles. Como se verá, muchos problemas de optimización pueden modelarse de manera de generar un árbol cuyos nodos constituyen posibles soluciones o pasos intermedios a la solución del problema; cada uno de estos algoritmos define un orden en el cual se generarán los nodos del árbol, y una forma en la cual se encontrará la solución buscada.
== Definiciones ==
=== Costo ===
Los algoritmos de optimización por búsqueda trabajan con el concepto de costo, que es la función que debe ser optimizada. Cada paso en el camino que constituye la solución óptima, tendrá asociado un costo en sí mismo, y el costo global será función de los costos de cada uno de esos pasos.
=== 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.
Línea 9 ⟶ 11:
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 ===
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 profundidad =
== Definición ==
| |||