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

Rendimiento de algoritmos para búsqueda de soluciones

Fernando P.    13/11/2017

Temas:  Fundamentos

El concepto de árbol de búsqueda resulta muy útil a la hora de crear algoritmos para tratar de solucionar problemas que cumplan los requisitos para ser tratados mediante técnicas de búsqueda de soluciones.

Ya hemos visto un algoritmo genérico que permite encontrar soluciones, al menos en teoría, para este tipo de problemas. Pero necesitamos ir más allá y considerar la cuestión del rendimiento porque muchos problemas son demasiado complejos para poder ser resueltos de forma práctica con algoritmos genéricos.

Problemática básica para resolver un problema usando búsqueda de soluciones
Desde un punto de vista práctico, cualquier problema medianamente interesante que pueda ser resuelto mediante búsqueda de soluciones va a necesitar de un computador para ejecutar el algoritmo que permita resolverlo. Es una cuestión de tamaño y/o complejidad.

Naturalmente, un computador tiene recursos finitos y debemos ceñirnos a los recursos que tenemos a la hora de tratar de resolver un problema. No tiene sentido usar un algoritmo que tarde una semana en localizar una solución si necesitamos la solución para dentro de dos días.

Tampoco tiene sentido usar un algoritmo orientado a velocidad para resolver un problema sencillo. A veces los algoritmos sacrifican fiabilidad para conseguir velocidad y si tenemos un problema sencillo la velocidad puede que no sea lo que más nos interese.

Partiendo del algoritmo genérico que hemos visto para localizar soluciones, se han desarrollado muchos algoritmos que son refinamientos de este, más complicados, pero que permiten obtener soluciones en menor tiempo o con menos recursos de computador. Aunque no existe ningún algoritmo mágico que siempre obtenga resultados óptimos con recursos acotados.
Rendimiento algoritmos busqueda
Por todo esto, resulta fundamental conocer para cada algoritmo en qué condiciones es capaz de localizar soluciones al problema y qué recursos va a necesitar para ello. Se trata de lo que llamaríamos de forma genérica evaluación del rendimiento del algoritmo.

En un algoritmo, existen varias cuestiones que pueden ser medidas o consideradas de forma objetiva y que nos van a permitir evaluar de forma precisa el rendimiento de cada algoritmo.

Completitud
Una propiedad básica de cualquier algoritmo es la completitud, que se refiere a si el algoritmo va a ser capaz de localizar siempre una solución para el problema, suponiendo que, efectivamente, exista alguna solución.

Básicamente, vamos a dividir los algoritmos en dos tipos atendiendo a si son capaces de conseguir completitud. Por un lado tenemos algoritmos que siempre van poder localizar una solución (exactos) y otros que no ofrecen tal garantía (heurísticos).

El motivo de que existan algoritmos que no pueden ofrecer completitud es que hay problemas tan complejos que es seguro que un algoritmo exacto va a tardar demasiado y no va a resultar práctico tratar de resolver el problema. Sin embargo, un algoritmo heurístico puede ser mucho más rápido y es preferible tener un 60% de posibilidades de conseguir una solución con un algoritmo heurístico a un 0% con uno exacto.

Optimalidad
Un problema puede tener muchas soluciones pero igual nos interesa la de menor coste, así que el hecho de encontrar una solución no es de gran ayuda, nos interesa la que resulte en menor coste entre todas las que podamos localizar.

De la misma forma que sucede con la optimalidad, hay algoritmos exactos que localizan siempre la mejor solución y otros heurísticos que localizan soluciones razonables.

En general, es muy difícil o directamente imposible encontrar la solución óptima en muchos problemas de buen tamaño. Encontrar una buena solución, una que tenga un coste asumible, suele ser un logro razonable, por lo que no es tan importante exigir optimalidad como lo pueda ser exigir completitud.

Coste en tiempo
El número de iteraciones necesarias en un algoritmo para resolver un problema suele crecer muy deprisa con el tamaño del problema. Se suele medir el coste en tiempo para un algoritmo como una función del tamaño del problema (podemos usar nodos o arcos del árbol de búsqueda). Buenos algoritmos suelen tener coste en tiempo que son funciones polinomiales del tamaño, otros no tan buenos tienen funciones exponenciales.

Cada iteración del algoritmo es tiempo que necesita el computador, puede que un computador rápido pueda hacer miles o millones de iteraciones por segundo, pero no es difícil pensar en problemas que pueden necesitar muchos órdenes de magnitud por encima de eso, como puede ser el caso del problema del viajante de comercio.

Hay diferencias entre unos y otros algoritmos respecto al coste en tiempo, pero a menudo mejorar el coste en tiempo puede suponer sacrificar otra cosa, como puede ser la exactitud o los requisitos de memoria en el computador. No siempre elegir el algoritmo más rápido va a ser lo más conveniente.

Coste en espacio
El coste en espacio se refiere a la cantidad de recursos de computador en forma de memoria que vamos a necesitar para ejecutar un algoritmo dado. Igual que sucede con el tiempo, se trata de un recurso acotado en un computador.

Ya en el algoritmo genérico visto, el algoritmo especifica que es necesario mantener una lista con los nodos visitados y otra lista con la frontera pendiente de explorar. Estas listas van a ir creciendo a medida que se ejecuta el algoritmo y requieren de memoria en el computador. Para problemas de cierto tamaño pueden ser inmensas. Y en algoritmos más elaborados es posible que existan estructuras de datos adicionales que deban ser almacenadas durante la ejecución del mismo.

En general, el coste en espacio no tiene porqué estar correlacionado con el coste en tiempo. Puede suceder que haya problemas cuyo árbol de búsqueda es enorme (mucho espacio) pero que pueden ser resueltos de forma relativamente rápida. Y puede suceder que un problema que no requiera de mucho almacenamiento sí que necesite muchas iteraciones.

Consideraciones sobre el espacio necesario
Calculando el número de nodos y arcos que tendría el árbol de búsqueda completamente expandido, podemos usar la suma de esos números como una medida del espacio de almacenamiento que vamos a poder llegar a necesitar para cualquier algoritmo.

En caso de que no resulte fácil calcular el tamaño del árbol completo, podemos usar otras magnitudes que nos permiten hacernos una idea de lo grande que puede llegar a resultar el árbol de búsqueda.

Una de esas magnitudes es el número máximo de hijos por nodo del árbol. Naturalmente, un elevado número de hijos por nodo tiene el potencial de hacer crecer el tamaño del árbol muy deprisa.

También podemos considerar la longitud máxima (en arcos) desde el estado inicial hasta nodos que ya no se pueden expandir más (no tienen hijos). Una longitud máxima elevada combinada con muchos hijos por nodo es una situación que va a crear árboles muy grandes.

Por último, hay que tener en cuenta que nodos en el árbol de búsqueda no se corresponden con el número de estados del entorno del problema, porque un mismo estado se puede representar con varios nodos dependiendo de las condiciones previas que dieron lugar a ese estado. Esta es la situación que permite que puedan existir bucles en el árbol de búsqueda y que tiene potencial para crear árboles muy grandes incluso en problemas con pocos estados del entorno.



No existen algoritmos exactos acotados en tiempo y espacio para cualquier problema que pueda resolverse usando búsqueda de soluciones. El análisis de cada problema concreto y la elección del algoritmo más adecuado es la única esperanza de poder resolverlo.



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 está completamente dedicado a problemas que pueden ser solucionados mediante búsqueda.



 

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