Algoritmos Voraces: Problema del viajante con prisa

Seguimos con problemas que se pueden resolver mediante algoritmos voraces. Vamos imaginar que tenemos a una persona que desea viajar en coche desde un punto A hasta otro punto B (n kilómetros). El viajante dispone de un mapa de carretera que indica la distancia entre las gasolineras que están situadas en el trayecto que va a realizar. En el punto de origen, el tanque del coche se encuentra lleno. Conocemos un máximo de kilómetros que el coche puede realizar sin la necesidad de repostar (x kilómetros / xsu objetivo es pararse a repostar el menor número de veces posibles. El algoritmo voraz nos determinará en qué gasolineras el viajante tiene que parar a repostar.

Gasolinera

Veamos el problema con un ejemplo:

Gasolinera

En este ejemplo el viajante tiene que realizar un trayecto de 56 km. En su ruta dispone de 5 gasolineras, siendo conocedor de sus distancias entre ellas (vector g[i]). El número de kilómetros máximos que puede realizar sin repostar es 30, por lo tanto repostamos en una gasolinera si no podemos llegar a la siguiente. Si el viajante del problema avanza hasta la primera gasolinera se encuentra con lo siguiente:

Gasolinera

Vemos que no es necesario repostar puesto que podríamos llegar a la siguiente gasolinera sin problemas. Esto no ocurre cuando llegamos a la tercera gasolinera:

Gasolinera

Aquí calculamos los kilómetros que tendríamos que realizar para llegar a la siguiente gasolinera y nos indica que no poseemos suficiente combustible. Por lo tanto, debemos de repostar en la tercera gasolinera. Cabe decir que cuando repostamos los kilómetros que hemos realizado desde la última vez que repostamos (kms) vuelven a 0.

El mejor caso posible (que no tuviéramos que parar a repostar en ninguna gasolinera) tendríamos que recorrer el vector una sola vez, por lo que la complejidad sería O(n). El peor de los casos evidentemente sería tener que parar en todas las gasolineras, por lo cual tendríamos una complejidad O(n²). Así pues, la complejidad de este algoritmo se encuentra en un punto intermedio entre O(n) y 0(n²), según el número de gasolineras donde haya que parar.

Más información | Algoritmos Voraces en Wikipedia

Más noticias sobre: Matemáticas, Programación
Comentarios (6) | Trackback

Comentarios

¿que pasa si hay tráfico por un accidente en la carretera? ¿O si el viaje va lento por ser temporada de vacaciones?
Por maximizar el uso de la gasolina nos podemos quedar a medio puerto. Habría que añadirle una variable, un colchón de seguridad, un ¿que probabilidad hay de ...? .

saludos!
Mario

#1 | Escrito por Caso Patologico | 13 sep 2006 18:31:03

Buenas Mario. El problema básico del viajante con prisa es así y es ideal, es decir, excento de otras variables que puedan influir como la velocidad del tráfico, las condiciones climatológicas, ...

Un saludo!

#2 | Escrito por Alfonso Jiménez | 13 sep 2006 18:36:21

No en entiendo que haya que recorrer el vector cada vez que se para en una gasolinera.

Solo hay que comprobar al llegar a cada gasolinera la distancia a la siguiente para saber si parar o no ¿o es que hay algo que no he entendido?

#3 | Fran | 14 sep 2006 00:20:22

¿ Qué utilidad tiene este ejemplo?

#4 | Escrito por javi | 14 sep 2006 00:56:34

Fran: No hay que recorrer el vector cada vez que se para en una gasolinera. El recorrido es secuencial, cuando seleccionamos una gasolinera k candidata comprobamos si es prometedora, es decir, evaluamos g[k+1]>kmMax-Kms (o kms==kmMax cuando kprimera parte de algoritmos voraces. Si tenéis curiosidad no dudéis en comentarlo y os implemento los métodos.

javi: Más que un ejemplo es una técnica de programación. Un problema clásico de diseño de algoritmos.

Un saludo!

#5 | Escrito por Alfonso Jiménez | 14 sep 2006 15:56:53

Los algoritmos voraces son muy utilizados para dirigir el trafico por la red, para ello se hace como en el ejemplo que aparece en cualquiera de las dos noticias, solo que se tienen en cuenta varios parametros a la vez como puedan ser distacncia, coste...

Con esta informacion los nodos generan tablas para saber como encaminar el trafico de manera eficiente, ademas cada cierto tiempo se revisa el algoritmo para subsanar posible problemas como congestion o caidas de los nodos.

Por ejemplo tienes el algoritmo OSPF.

#6 | miguel | 14 sep 2006 18:48:57

¡Añade tu comentario!