viernes, 5 de marzo de 2010

Proyecto 2

Problema Jeep (Exploration Problem)


Descripción
Maximizar la distancia de un Jeep puede penetrar en el desierto con una cantidad dada de combustible. El jeep se le permite ir hacia adelante, descargar un poco de combustible, y luego regresar a su base con el combustible restante en el tanque. En su base, se puede repostar combustible y partir de nuevo. Cuando llega el combustible que ha guardado anteriormente, entonces se pueden utilizar para llenar parcialmente su tanque.

Problema
Hay n unidades de combustible almacenado en una base fija. El jeep se puede llevar a lo más 1 unidad de combustible en cualquier momento, y puede viajar 1 unidad de distancia en 1 unidad de combustible (el consumo de combustible del jeep se supone que es constante). En cualquier punto en un viaje del jeep puede salir de cualquier cantidad de combustible que está realizando en un vertedero de combustible, o puede recoger cualquier cantidad de combustible que quedaba en un vertedero de combustible en un viaje anterior, siempre y cuando su carga de combustible en ningún caso exceda 1 unidad.

Hay dos variantes del problema:
Explorando el desierto - El jeep debe regresar a la base al final de cada viaje.
Atravesando el desierto - El jeep tiene que volver a la base al final de cada viaje, salvo para el viaje final, cuando el jeep viaja tan lejos como pueda antes de quedarse sin combustible.

En cualquier caso el objetivo es maximizar la distancia recorrida por el jeep en su viaje final. Alternativamente, el objetivo puede ser encontrar la menor cantidad de combustible necesario para producir un viaje de final de una distancia determinada.

En el clásico problema del combustible en el jeep y en los vertederos de combustible es tratado como un continua cantidad. Más complejas variaciones en el problema han sido propuestos en los que el combustible sólo puede ser la izquierda o recogidos en cantidades discretas.


Solución

Una estrategia que aproveche al máximo la distancia recorrida en el viaje de final de la "variante de explorar el desierto" es el siguiente:

• En cada viaje se inicia desde la base con 1 unidad de combustible.
• En el primer viaje del jeep recorre una distancia de 1 / (2n) Las unidades y las hojas (n- 1) /n unidades de combustible en un vertedero de combustible. El jeep todavía tiene 1 / (2n) Unidades de combustible - sólo lo suficiente para regresar a la base.
• En cada uno de los siguientes n- 1 recoge los viajes del jeep 1 / (2n) Unidades de combustible a partir de esta primera descarga de combustible a la salida, por lo que sale de la descarga de combustible de 1 unidad de transporte de combustible. También recoge la 1 / (2n) Unidades de combustible a partir de esta primera descarga de combustible en el camino de regreso, que es justo lo suficiente combustible para regresar a la base.
• En el segundo viaje el jeep viaja a la descarga y recarga las pilas de combustible primero. A continuación, recorre una distancia de 1 / (2n- 2) unidades y las hojas (n- 2) / (n- 1) unidades de combustible en un vertedero de combustible segundo. El jeep todavía tiene 1 / (2n- 2) unidades de combustible, que es justo lo suficiente para regresar a la descarga de combustible en primer lugar. Aquí se recopila 1 / (2n) Unidades de combustible, que es justo lo suficiente combustible para regresar a la base.
• En cada uno de los siguientes n- 2 viajes del jeep recoge 1 / (2n- 2) unidades de combustible de este combustible segundo volcado a la salida, por lo que sale de la descarga de combustible de 1 unidad de transporte de combustible. También recoge la 1 / (2n- 2) unidades de combustible de la segunda descarga de combustible en el camino de regreso, que es justo lo suficiente combustible para regresar a la descarga de combustible en primer lugar.
• El jeep sigue de esta manera, de modo que en el viaje k que establece un nuevo k de combustible o volcado a una distancia de 1 / (2n- 2k+ 2) unidades de la descarga de combustible anterior y las hojas (n--k) / (n--k+ 1) unidades de combustible allí. En cada uno de los siguientes n--k los viajes que recopila 1 / (2n- 2k+ 2) unidades de combustible de la k descarga o en su salida y otro 1 / (2n- 2k+ 2) unidades de combustible en su camino de regreso.





Solución a "explorar el desierto" variante de n= 3, mostrando el contenido de combustible del jeep y los depósitos de combustible al comienzo de cada viaje y en el punto de rotación de los buques en cada viaje.






Cuando el jeep se inicia su último viaje, hay n- 1 vertederos de combustible. El más lejano contiene 1 / 2 de una unidad de combustible, el siguiente más alejado contienen 1 / 3 de una unidad de combustible, y así sucesivamente, y el basurero más cercano combustible tiene apenas 1 /n unidades de combustible a la izquierda. Junto con 1 unidad de combustible con la que se inicia desde la base, esto significa que el jeep se puede recorrer una distancia total de ida y vuelta de la de unidades en su último viaje (la máxima distancia recorrida en el desierto es la mitad de este).
Se recoge la mitad del combustible restante en cada uno de volcado a la salida, lo que llena su tanque. Después de dejar el más alejado de combustible volcado viaja a 1 / 2 de una unidad más en el desierto y luego regresa a la basura más alejado de combustible. Se acumula el combustible restante de cada descarga de combustible en el camino de regreso, que es justo lo suficiente para llegar a la siguiente o la descarga de combustible, en la etapa final, para regresar a la base.

La distancia recorrida en el último viaje es el no número de armónicos [1] , Hn. Como no están acotadas en los números armónicos, es posible superar cualquier distancia en el viaje final, como a lo largo de suficiente combustible está disponible en la base. Sin embargo, la cantidad de combustible necesario y el número de depósitos de combustible, tanto aumentar de forma exponencial con la distancia que debe recorrerse.

La "travesía del desierto" variante se pueden resolver con una estrategia similar, excepto que ya no hay ninguna obligación de recoger el combustible en el camino de regreso en el viaje final. Así que en el viaje k el jeep se establece un nuevo k de combustible o volcado a una distancia de 1 / (2n- 2k+ 1) unidades de la descarga de combustible y las hojas anteriores (2n- 2k- 1) / (2n- 2k+ 1) unidades de combustible allí. En cada uno de los próximos n--k- 1 viaje que recopila 1 / (2n- 2k+ 1) unidades de combustible de la k descarga o en su salida y otro 1 / (2n- 2k+ 1) unidades de combustible en su camino de regreso.

Ahora, cuando el jeep se inicia su último viaje, hay n- 1 vertederos de combustible. El más lejano contiene 1 / 3 de una unidad de combustible, el siguiente más lejos contener 1 / 5 de una unidad de combustible, y así sucesivamente, y el basurero más cercano de combustible acaba de 1 / (2n- 1) unidades de combustible a la izquierda. Junto con 1 unidad de combustible con la que se inicia desde la base, esto significa que el jeep se puede recorrer una distancia total de la de unidades en su viaje final. Recoge todo el combustible restante en cada uno de volcado a la salida, lo que llena su tanque. Después de dejar el más alejado de combustible volcado viaja una distancia mayor de 1 unidad.

Tenga en cuenta que lo que es posible en teoría, cruzar un desierto de cualquier tamaño dado suficiente combustible en la base. Como antes, la cantidad de combustible necesario y el número de depósitos de combustible, tanto aumentar de forma exponencial con la distancia que debe recorrerse.

--------------------------

Ln Máxima distancia Alcanzada, n combustible

Referencias

[1] http://en.wikipedia.org/wiki/Harmonic_number

http://mathworld.wolfram.com/JeepProblem.html

http://en.wikipedia.org/wiki/Jeep_problem


http://page.mi.fu-berlin.de/rote/Papers/pdf/Optimal+logistics+for+expeditions+-+the+jeep+problem+with+complete+refilling.pdf


1 comentario:

Elisa dijo...

Me hubiera gustado ver análisis asintótico del algoritmo - lo que analizar tú es la asintótica de la solución óptima. Pero que bien que hiciste el proyecto :)