Diferencia entre revisiones de «Estructuras de datos dinámicas/Algoritmos de búsqueda»

Contenido eliminado Contenido añadido
Rgfernan (discusión | contribs.)
Rgfernan (discusión | contribs.)
Sin resumen de edición
Línea 79:
= Implementación =
== El algoritmo de búsqueda genérico ==
Para implementar tanto la búsqueda en profundidad, como la búsqueda en anchura, la de costo fijo y la heurística, puede utilizarse un algoritmo genérico:
 
# Colocar el nodo inicial en la lista abierta.
Para el caso de la búsqueda de costo fijo, nótese que si se agrega a la lista abierta un nodo correspondiente a un estado que ya está allí, pero con un valor de costo diferente, no habrán expansiones repetidas, ya que una vez en la lista cerrada, cuando se tome de la lista abierta el nodo con estado repetido, será siempre con un mayor valor de costo, y se descartará.
# Elegir el próximo elemento de la lista abierta a extraer, y realizar la extracción.
# Si se corresponde con un estado final, devolver el elemento o la secuencia de acciones correspondiente, si no, continuar.
# Explandirlo, colocando los descendientes que correspondan en la lista abierta.
# Colocarlo en la lista cerrada y volver a 2.
 
De las características de la estructura de datos utilizada como lista abierta, dependerán las características del algoritmo:
 
Si la estructura es una pila, el algoritmo elegirá siempre el último nodo generado, y a partir de ese nodo generará nuevos nodos, que serán agregados a la pila, y el primero será elegido, y así sucesivamente; es decir que la búsqueda será en profundidad.
 
Si la estructura es una cola, los nodos se expandirán en el orden que se generen, de manera que todos los nodos de un nivel deberán ser expandidos antes de comenzar a expandir los del siguiente; la búsqueda será en anchura.
 
Si la estructura es una cola de prioridad, y la función de ordenamiento es la función costo, de manera que el elemento elegido sea siempre el de menor costo, la búsqueda será de costo uniforme. Si la función de ordenamiento combina la función de costo con una función heurística, la búsqueda será heurística.
 
 
---------------------
 
{{nota|1}}Para el caso de la búsqueda de costo fijo, nótese que si se agrega a la lista abierta un nodo correspondiente a un estado que ya está allí, pero con un valor de costo diferente, no habrán expansiones repetidas, ya que una vez en la lista cerrada, cuando se tome de la lista abierta el nodo con estado repetido, será siempre con un mayor valor de costo, y se descartará.