Revolución IA

La Inteligencia Artificial está llamada a protagonizar la próxima Revolución tecnológica

Inicio Sobre Revolucionia Temas Para saber más Contacto

Algoritmo para búsqueda con coste uniforme

Fernando P.    18/12/2017

Temas:  Fundamentos

En el contexto de problemas que se pueden resolver usando técnicas de búsqueda de soluciones ya hemos visto que hay una clase de algoritmos que operan mediante búsqueda sistemática.

También hemos visto el algoritmo más sencillo, denominado de búsqueda en anchura y ahora vamos a ver un refinamiento de este algoritmo que soluciona algunas cuestiones que presentaba su aplicación a ciertos problemas.

Construcción del árbol de búsqueda
Como ya comentábamos para el algoritmo para búsqueda en anchura, la idea fundamental subyacente a los algoritmos que pueden usarse para búsqueda de soluciones es el concepto de árbol de búsqueda. En general, las diferencias entre unos y otros algoritmos van a estar en la forma en la que se construye este árbol de búsqueda.

El algoritmo para búsqueda en anchura se definía como una sencilla instancia del algoritmo general para costruir árboles de búsqueda.

El principal inconveniente que teníamos con el algoritmo para búsqueda en anchura consistía en que sólo garantizaba una solución óptima en el caso de que todas las secuencias de acciones tuvieran un coste que fuera una función no decreciente en la longitud de su camino en el árbol de búsqueda. Caso especial de esta situación es que todos los arcos del árbol de búsqueda tengan el mismo coste.

Este inconveniente se puede solventar con una modificación sencilla al propio algoritmo para búsqueda en anchura. El algoritmo resultante de esta modificación lo vamos a denominar algoritmo de búsqueda con coste uniforme.

Búsqueda con coste uniforme Algoritmo para búsqueda con coste uniforme
La idea fundamental de este nuevo algoritmo consiste en explorar siempre el nodo de la frontera que tenga menor coste, entendido como suma de todos los costes desde el nodo inicial a ese nodo.

Denominamos al algoritmo como de búsqueda con coste uniforme porque la forma de explorar propuesta expande el arbol de forma uniforme respecto al coste de sus nodos. Todos los nodos de la frontera van a tener tendencia a tener un coste similar.

Para implementar este algoritmo necesitamos tres cambios en el algoritmo de búsqueda en anchura. En primer lugar debemos cambiar la lista FIFO que representa la frontera por una lista ordenada en base al coste de cada nodo.

En segundo lugar, la comprobación de nodo destino se hace cuando se expande ese nodo, no antes. De esta forma nos aseguramos que no hay ningún otro camino de coste inferior a ese nodo, por la propia política del algoritmo de expandir primero los nodos de menor coste.

En último lugar, puede suceder que lleguemos a un nodo que ya está en la frontera, pero que lleguemos a él con un camino de menor coste. En este caso hay que recolocar ese nodo dentro de la frontera con el nuevo coste (menor).

En la ilustración adjunta hay un ejemplo de cómo se aplicaría el algoritmo a un caso sencillo de árbol de búsqueda.

Sumario del algoritmo para búsqueda con coste uniforme
Con las ideas dadas en el punto anterior, estamos en condiciones de dar un sumario completo del algoritmo, que es una modificación del algoritmo para búsqueda en anchura:

  1. Crear la frontera como una lista ordenada por coste, vacía
  2. Insertar el estado incial del problema en la frontera (coste 0)
  3. Crear vacía la lista  V  de nodos ya visitados
  4. Si la frontera está vacía el problema no tiene solución. Detenerse
  5. Sacar el siguiente nodo de la frontera (menor coste), sea  n  el nodo elegido y sea  cn  el coste para  n
  6. Añadir  n  a  V
  7. Si  n  es el nodo destino hemos terminado. La solución es la secuencia de nodos/acciones en  V  que conectan el origen con  n  a coste  cn
  8. Ampliar el árbol expandiendo el nodo  n. Sea  X  el conjunto de nodos que resultan de expandir  n
  9. Sea  Y  la lista de nodos en  X  que no estén ya en  V
  10. Para cada nodo  p  en  Y  repetir 11 a 13
  11. Sea  cnp  el coste entre los nodos  n  y  p
  12. Si  p  está en la frontera con coste mayor a  cn+cnp, reordenar  p  en la frontera con coste  cn+cnp
  13. Si  p  no está aún en la frontera, insertarlo con coste  cn+cnp
  14. Ir a 4

Ventajas e inconvenientes del algoritmo
El algoritmo para búsqueda con coste uniforme hereda la sencillez del algoritmo para búsqueda en anchura y es capaz de localizar la solución óptima (camino de mínimo coste entre el origen y el destino) siempre que no haya una secuencia infinita de arcos con coste cero en el árbol del búsqueda.

En principio, este algoritmo no tiene inconvenientes insalvables, pero se debe suponer que todos los arcos del árbol de búsqueda (acciones a tomar en el problema) tienen un coste positivo. Es una restricción razonable y en estas condiciones el algoritmo es completo, siempre localiza la solución óptima.

Rendimiento del algoritmo
Cuando vimos el algoritmo para búsqueda en anchura se calcularon expresiones para la complejidad del mismo, tanto en tiempo como en espacio de almacenamiento, que eran ambas  O(hd), donde  h  es el número promedio de descendientes por nodo y  d  es la profundidad a evaluar.

Para el caso del algoritmo de búsqueda con coste uniforme, no es tan sencillo calcular las expresiones de complejidad.

Podemos hacer una aproximación a la complejidad del algoritmo en el peor de los casos, asumiendo que todos los arcos del árbol de búsqueda tienen un coste mínimo  δ  y que el coste de la solución óptima es  C. Entonces se verifica que la complejidad en tiempo (y espacio) para este nuevo algoritmo es  O(h1+C/δ).

Igual que sucede en el algoritmo para búsqueda en anchura, tenemos complejidades exponenciales que pueden no ser viables para problemas complejos.

Si todos los arcos del árbol de búsqueda tienen un coste parecido, este nuevo algoritmo viene a funcionar de forma parecida al algoritmo para búsqueda en anchura, pero con peor rendimiento debido a que necesita explorar un nivel adicional antes de estar seguro de que ha llegado al nodo destino.

Si hay diferencias significativas entre los costes de los arcos del árbol de búsqueda, entonces este nuevo algoritmo es más eficiente que el algoritmo para búsqueda en anchura y puede suceder que tenga éxito en problemas que aquel no pueda abordar por su excesivo tamaño.



El algoritmo de búsqueda con coste uniforme es completo en situaciones razonables. Tiene los mismos problemas de complejidad que el algoritmo para búsqueda en anchura aunque puede funcionar en algunos problemas en los que aquel se vuelve inmanejable.



Para saber más:

Libro de Stuart Russell y Peter Norvig que trata todas las técnicas de Inteligencia Artificial. No hace demasiado énfasis en cuestiones conectivistas (redes neuronales artificiales) y contiene abundante material del resto de técnicas. El capítulo 3 contiene una discusión detallada del algoritmo para búsqueda con coste uniforme.



 

Inicio Powered by NetBSD
 
HTML5
 
En general, todo el contenido de este sitio web es original, salvo referencias o enlaces a otros sitios web y citas o reproducciones expresamente presentadas como tales.

No está permitida la reproducción ni la copia del contenido de este sitio web sin el permiso expreso de la propiedad del mismo.

Este sitio web no utiliza cookies ni ningún otro mecanismo para almacenar información en los navegadores de los visitantes ni para realizar seguimiento de los mismos.

2017,2018 Revolucionia.net
Sobre Revolucionia
Temas
Para saber más
Contacto