6.5.1 Búsqueda no informada: Algoritmo de Coste Uniforme

La idea del algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices, enumerando todos los nodos del espacio de estados por costes (valores de g) crecientes; cuando se obtiene el camino más corto desde el vértice origen, a la estación destino objetivo de la búsqueda, el algoritmo se detiene.

{búsqueda de coste uniforme}

abierta ←s0

Repetir Si

vacío?(abierta) entonces

devolver(negativo)

nodo←primero(abierta)

Si meta?(nodo)entonces

devolver(nodo)

sucesores←expandir(nodo)

Para cada n∈sucesores hacer

n.padre←nodoordInsertar(n,abierta,g)

Fin{repetir}

En el algoritmo se almacena cada nodo con su valor g y se insertan los nuevos nodos expandidos en una estructura dinámica (una cola con prioridad) en orden ascendente según su valor de g; la búsqueda de coste uniforme es completa al ser los costes números enteros positivos, siendo no acotada la sucesión de valores g, por lo que si el nodo meta existe en el espacio de estados, será expandido alguna vez; y óptima, puesto que al expandir todos los nodos del espacio de estados por valores crecientes de g, cuando se expande el primer nodo meta, éste será el nodo meta de menor valor de g.

El análisis de completitud y optimalidad de la búsqueda de coste uniforme se basa en que en el hecho de que la sucesión de costes (valores de g) nunca disminuye; el problema es que, al encontrarse éste desinformado sobre la estación destino, realizará una evaluación de recorrido mínimo desde la estación origen a todos las estaciones contenidas en la Red, deteniéndose su ejecución al llegar a la estación destino seleccionada, tal como una búsqueda en amplitud hace, lo cual provoca que no resulte eficiente, pues su uso implica de un gran esfuerzo computacional, ya que, a diferencia del algoritmo de búsqueda A*, del cual hablaremos a continuación, al no encontrarse informado sobre la estación “final”, y por tanto no guiado hacia el destino, calcula rutas mínimas de recorrido desde la estación origen a todas sus adyacentes que nosotros consideramos candidatas de formar parte del camino mínimo a la estación destino, provocando que, para estaciones origen y destino muy distanciadas entre sí y algo aisladas, de comunicación no tan directa (pensemos en una estación destino en una línea con pocas correspondencias con otras líneas, como por ejemplo, el tramo final de la línea 7), el uso del mismo resulte muy pesado, con tiempos de ejecución elevados, y con un uso exhaustivo de las prestaciones del equipo (memoria RAM) sobre el cual se esté utilizando la aplicación, en ocasiones no permitiendo incluso la obtención de una solución.

Una vez llegados a la fase final de verificación del correcto funcionamiento del sistema, procederemos a una comparación de los 3 agentes para distintos supuestos (estación origen -> estación destino) en un banco de pruebas, verificando que cumplen con su cometido y respetan la especificación impuesta en todos los casos. Los resultados del mismo, junto con la toma de una serie de conclusiones, vendrán expuestos en un anexo ofrecido en el siguiente enlace perteneciente al presente blog de seguimiento del proyecto final de carrera Poiritem: http://wp.me/pGu8u-aO

Creative Commons License
Poiritem by Ismael Rihawi Aragón is licensed under a Creative Commons Reconocimiento-No comercial-Sin obras derivadas 3.0 España License.
About these ads

Los comentarios están cerrados.