¿Cuál es la ruta más rápida para disminuir peso cuando el tiempo es proporcional a peso x distancia?

Question

Usted tiene un camión en el punto de partida que es la realización de todas las parcelas para el día.

$$\rm Time\ taken = Total\ Lorry\ Weight \times Distance\ travelled $$

Después de visitar cada una de las zonas que tienen que regresar al punto de partida.

Camión de peso es $30$. Usted debe tomar todas las gestantes parcelas con usted en cada viaje. El combustible no tiene peso, su combustible es eterna y que no pierda tiempo al dejar los paquetes.

¿Cuál es la ruta óptima para la entrega de todos los paquetes y volver al punto de partida?

---

Mis pensamientos iniciales para la solución de este era trabajar hacia atrás y trabajar que la entrega sería agregar la menor cantidad de tiempo total en todo el viaje. A continuación, repita esto hasta que llegué a la primera parada.

Me han dicho que no es la manera correcta de hacer el trabajo de forma no segura de lo que iba a hacer la ruta que tengo para que sea más óptimo.

Answer 1

Esta no es una respuesta ya que no puedo probarlo, pero tal vez otros pueden (o mostrar el error de mi forma de ser).

Si todas las parcelas pesaba la misma, la estrategia óptima sería para descargar la más cercana de las parcelas de la primera. Esto significa que podríamos clasificar las zonas a visitar en primer lugar por su clasificación según su distancia $d$, es decir, el rango $r=d$.

Si todas las distancias eran los mismos, la estrategia óptima sería para descargar la más pesada de las parcelas de la primera. Esto significa que podríamos clasificar las zonas a visitar en primer lugar por su clasificación a la inversa por su peso $w$, es decir, $r=\frac{1}{w}$.

Poniendo estos dos observaciones juntos, parece una buena primera aproximación sería la de clasificar las zonas de acuerdo a $r=\frac{d}{w}$. Si hago esto, entonces la simulación por ordenador muestra esto le da exactamente la ruta óptima para la primera $2$ zonas, la primera $3$ zonas, etc hasta la primera $6$ zonas (después de que mi algoritmo recursivo encontrado desbordamiento).

Me parece entonces que una simple clasificación de las zonas por $r=\frac{d}{w}$ le dará la ruta óptima.

EDITAR

Cambió mi simulación de recursiva para no recursivo y encontró la respuesta tiene, al menos, $8$ zonas.

EDIT2

Mejora de la simulación muestra que se trabaja para $11$ zonas. Estoy convencido de. :) Solo queda demostrar que siempre va a funcionar.