15 junio 2007

Analisis y diseño de algoritmos: un enfoque practico

Para que luego digan que lo que estudiamos no es útil. Imaginemos que tenemos que ir desde Málaga hasta Oulu(Finlandia). Para ello distintas compañias de vuelo ofrecen ofertas pero ningún vuelo es directo, es decir, tienes que hacer escalas en otros aeropuertos intermedios. A ti, que vas buscando lo más barato, te da igual pasar una noche en Colonia(Alemania) o Barcelona. ¿Cómo harías para encontrar el vuelo más económico?. Para este caso tenemos algo parecido a esto (cutre dibujo):


Obviamente en problemas reales hay que tener en cuenta más factores. En este caso, se podría haber tenido en cuenta el tiempo total del trayecto de las diferentes rutas o los gastos de cambiar de aeropuerto en la misma ciudad (caso de Londres).

Para resolver este problema hay dos opciones:
a)A lo cazurro. Te pones a calcular todas las posibles combinaciones hasta que te aburras y te quedas con la más barata. Este es un grafo simple con pocos nodos, tampoco costaría mucho. Pero imaginemos un grafo con todas las principales ciudades de europa, la cosa se complicaría bastante.
b)Aplicando alguna técnica algorítmica. Para encontrar el camino mínimo entre dos vertices tenemos varias opciones. Una de ellas es el algoritmo de Dijkstra que encuentra el camino mínimo entre un vertice y el resto y otra opción sería mediante programación dinámica.

La algoritmia no solo estudia como aplicar dichas técnicas a cierto problema dado sino el coste computacional que tiene, o sea, el tiempo y los recursos de los que hace uso.

Bueno, aplicando programación dinámica al problema (no lo hago aqui porque es muy tedioso), obtenemos que el viaje más ecónomico se realiza de la siguiente forma: Málaga-Palma de Mallorca-Helsinski-Oulu.

Relacionada: NP contra P: La algoritmia como ciencia y arte

delicous menéame

2 comentarios:

Lúcida dijo...

Quién me iba a decir a mi que la forma más corta de llegar a Finlandia es tirando por Palma de Mallorca.Que cosas. Suerte con los exámenes!!!

Anónimo dijo...

eres un friki