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

Ejemplos de problemas para búsqueda de soluciones

Fernando P.    30/10/2017

Temas:  Fundamentos

En previos artículos, se ha visto que las técnicas de búsqueda de soluciones pueden aplicarse para construir agentes inteligentes que resuelvan ciertos problemas verificando una serie de condiciones en su entorno y que tengan una estructura determinada.

Ya se ha visto algún ejemplo sencillo de este tipo de problemas, pero vamos a profundizar un poco más y vamos a hablar de problemas reales complejos que se resuelven mediante este tipo de técnicas.

Problemas de itinerarios
En la introducción a la búsqueda de soluciones se describió un problema muy simple que consistía en localizar un itinerario entre dos estaciones dadas de la red de Metro de Madrid que fuera lo más rápido posible.

Este problema es real y puede complicarse la modelización para incorporar incidencias, posibles congestiones u otros factores que pueden aparecer en el itinerario real, tal y como se vio en el artículo que trataba sobre la abstracción en la búsqueda de soluciones.

Si extendemos el problema de metro para incluir otros medios de transporte público y la posibilidad de buscar itinerarios entre ciudades el problema se complica bastante. Por ejemplo, en Google Maps tenemos un ejemplo de agente inteligente que es capaz de resolver el problema de buscar itinerarios usando transporte público.
Busqueda itinerario Metro
Si en vez de transporte público, optamos por transporte individual, podemos considerar el problema de ir de un lugar a otro usando un automóvil. Se trata de una variación del problema original de Metro, en este caso tenemos puntos de un mapa conectados por carreteras o calles, con una distancia dada.

Naturalmente, Google Maps también nos sirve para buscar un itinerario usando el automóvil y es capaz de usar como criterio de coste la distancia o el tiempo.

En general, los problemas de itinerarios, que consisten en ir de un sitio a otro mediante una serie de caminos conocidos a priori, se resuelven bien usando técnicas de búsqueda. Resulta obvio, pero en el caso de automóviles autónomos es vital poder resolver este tipo de problemas, seguramente con complicaciones añadidas.

Un caso interesante de problema de itinerarios es el problema de buscar vuelos comerciales que nos lleven de una ciudad a otra. Es un problema muy popular, con bastantes sitios web que ofrecen este tipo de servicios.

La complicación de buscar vuelos comerciales consiste en que los vuelos tienen fechas y horas establecidas y hay que ver cómo conectarlos para no perder mucho tiempo en los cambios de avión. Es fácil ver que la función de coste en este problema puede ser bastante complicada porque puede interesarnos minimizar el tiempo, el precio total, el número de cambios de avión o el número de compañías involucradas.

Problemas en forma de grafos
En general, un problema que se pueda representar como un grafo seguramente se va a poder solucionar usando búsqueda de soluciones. Veamos cómo queda la estructura de uno de estos problemas:

Los problemas de itinerarios son ejemplos claros de problemas que se pueden representar bien usando grafos. Pero con una abstracción adecuada, es posible representar como grafos problemas que aparentemente no tienen nada que ver con itinerarios.

Por ejemplo, resolver el cubo de Rubik puede modelizarse como un grafo. Cada estado del cubo es un nodo y cada rotación de una cara del cubo es un arco a otro nodo. El problema de este grafo es que tiene del orden de 1020 nodos, es un grafo demasiado grande para intentar cualquier cosa con él. No es práctico resolver el cubo directamente así, es mejor descomponerlo en una sucesión de problemas más sencillos.

El problema del viajante de comercio (TSP) Travelling Salesman Problem
Se trata de un problema muy famoso en Matemáticas, es simple de explicar pero muy difícil de resolver a nada que tenga cierto tamaño.

Tenemos un viajante de comercio y una lista de ciudades con sus distancias entre cada par de ellas. El viajante debe salir de una ciudad concreta, visitar el resto de ciudades una sóla vez y volver a la ciudad de origen.

El problema consiste en buscar un itinerario factible de mínima longitud. El problema se representa fácilmente con un grafo, pero con 30 ciudades el tamaño del grafo es ya del orden de 1030 nodos. Como sucede con el cubo de Rubik, se hace necesario descomponer el problema en otros más pequeños para poder obtener soluciones razonables.

El TSP es una forma de problema de itinerario que tiene ciertas restricciones. Hay versiones del problema que incorporan restricciones adicionales, como puede ser restricciones de precedencia entre ciudades.

El interés del TSP es que se puede ver también como un problema en el que hay que realizar una serie de tareas con una serie de restricciones. Esta forma de ver el problema nos abre un mundo de posibilidades para modelizar otros problemas y resolverlos de la misma forma.

Consideremos el problema de ensamblar un automóvil. Se trata de un proceso que involucra realizar muchas tareas en secuencia y con bastantes restricciones. Por ejemplo no podemos pintarlo si ya están puestos los cristales o no podemos poner las ruedas sin las transmisiones montadas. También hay cuestiones de eficiencia en el orden de las tareas como puede ser que las puertas montadas estorban mucho para trabajar en el interior.

Es posible modelizar el ensamblado de un automóvil mediante un grafo como el siguiente:

El ejemplo del ensamblado del automóvil no significa que la mejor forma de resolverlo sea necesariamente de forma similar al TSP, es una ilustración de cómo podemos abstraer el problema para formularlo en una forma parecida a otro problema conocido.

Pero sí que hay problemas reales en los que se aplica directamente el TSP. Por ejemplo, el reparto diario de mercancías a muchas tiendas de grandes cadenas comerciales y otros problemas similares de logística vienen a ser aplicaciones del TSP. Y como en el TSP, ocurre a veces que algunos de estos problemas de logística que son sencillos de formular resultan muy difíciles de resolver de forma óptima.



Hay muchos problemas reales que tenemos cerca de una forma u otra y que se resuelven con técnicas de búsqueda de soluciones, unas veces se pueden resolver de forma óptima y otras hay que hacer concesiones y conformarse con soluciones aceptables.



Para saber más:

Este libro tiene varios capítulos dedicados a agentes inteligentes así como resolución de problemas mediante búsqueda, con numerosos ejemplos, y seguramente sea el mejor recurso que se puede encontrar para profundizar en este tema.

Página de la Wikipedia sobre grafos. Los grafos son una herramienta muy potente para modelizar problemas y son especialmente útiles para el caso de problemas que se pueden resolver mediante búsqueda de soluciones.

Página de la Wikipedia sobre el problema TSP. Es un problema clásico en optimización que tiene muchas variantes y aplicaciones. En la práctica se puede resolver bien usando técnicas que localizan soluciones aceptables, pero encontrar soluciones óptimas puede ser impracticable para problemas de cierto tamaño.



 

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