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

Comparación de algoritmos para búsqueda sistemática

Fernando P.    22/01/2018

Temas:  Fundamentos

Dentro de la clase de problemas que se pueden resolver mediante técnicas de búsqueda de soluciones, hemos visto varios algoritmos sistemáticos que, cada uno con sus ventajas e inconvenientes, pueden ser usados para tratar de resolver este tipo de problemas.

Vamos a proceder ahora a comparar estos algoritmos usando los criterios para rendimiento que establecimos antes de empezar a ver cada uno de estos algoritmos. No se trata de saber cual es el mejor, porque no está claro que alguno sea mucho mejor que el resto, pero sí de tener en un único lugar toda la información relativa a su rendimiento para poder decidir cual se ajusta mejor a un problema determinado.

Los algoritmos
Todos los algoritmos vistos usan el concepto de árbol de búsqueda para representar el espacio de estados y posibles acciones del problema. En este sentido, todos los algoritmos son parecidos y sólo difieren unos de otros en la forma en la que exploran el árbol de búsqueda.

Los algoritmos vistos son:

Completitud Comparación de algoritmos para búsqueda sistemática
La cuestión de la completitud es muy importante porque es lo que nos garantiza que el algoritmo va a poder encontrar una solución al problema, suponiendo que exista alguna solución a profundidad finita dentro del árbol de búsqueda.

Respecto a esta cuestión hay ciertas diferencias entre los algoritmos vistos. Una restricción común a todos los algoritmos consiste en que no van a ser completos si la expansión de un nodo no resulta en infinitos sucesores, que será algo que debemos asumir para poder establecer la completitud de los algoritmos:

Optimalidad
La optimalidad es importante si tenemos un problema con muchas soluciones posibles y nos interesa la de menor coste. Así que no siempre va a ser necesario encontrar una solución óptima, pero son más comunes los problemas que requieren optimalidad de los que no la requieren.

Hay bastantes diferencias aquí entre los distintos algoritmos:

Coste en tiempo
El coste en tiempo viene a ser una cota superior de la magnitud del tiempo necesario para ejecutar el algoritmo respecto al tamaño del problema, medido usando la máxima profundidad del árbol de búsqueda  d  y una cantidad promedio de sucesores de cada nodo  h.

Se trata de una forma de ver cuanto tiempo adicional vamos a necesitar para resolver un problema cuando su tamaño aumenta. A veces el tiempo de ejecución es un recurso limitado y otras veces no tanto. En general, es una medida importante del rendimiento del algoritmo aunque no hay apenas diferencias entre ellos, la complejidad de todos los algoritmos crece de forma exponencial con la profundidad del árbol de búsqueda:

Coste en espacio
El coste en espacio es una medida análoga al coste en tiempo pero relativa a la cantidad de espacio de almacenamiento que vamos a necesitar en un computador. Se trata de un recurso que normalmente estará limitado, así que es un factor muy importante a tener en cuenta.

Hay bastantes diferencias entre los algoritmos y eso permite escoger el algoritmo que mejor se vaya a adaptar al tamaño de problema con el que nos enfrentamos. Hay algoritmos cuya complejidad respecto al espacio de almacenamiento crece de forma exponencial y otros que sólo crece de forma polinómica:

¿ Cómo elegir uno u otro algoritmo ?
En general, no hay un algoritmo que sea idóneo para cualquier problema. Debemos atender a las características de nuestro problema y ver cual de ellos puede funcionar mejor.

Por ejemplo, si necesitamos un algoritmo que garantice una solución óptima vamos a tener que optar por una búsqueda con coste uniforme. Si no nos interesa una solución óptima, la búsqueda en profundidad será una buena opción.

Probáblemente, la cuestión más relevante a la hora de elegir un algoritmo sea al tamaño que puede llegar a tener el árbol de búsqueda, porque el espacio de almacenamiento en el computador será un recurso limitado y tendremos que elegir un algoritmo que quepa en el espacio que tenemos.

Si hubiera que elegir el algoritmo que tiene problemas menos graves o más fácilmente solucionables habría que pensar en la búsqueda iterativa en profundidad. Pero en problemas específicos, cualquiera de los otros algoritmos puede ser una opción mejor.



Los algoritmos existentes para búsqueda sistemática en árboles de búsqueda no tienen demasiadas diferencias entre ellos, pero sí que existen las suficientes como para que cada uno pueda funcionar bien en determinados problemas.



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 de todos los algoritmos para búsqueda sistemática.



 

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