El tiempo de viaje de $n$ personas por grupo: la generalización de la Puente-y-Antorcha Problema

Question

Estoy trabajando en un proyecto relacionado con una evacuación de emergencia:

Encontrar el tiempo mínimo para hacer $n$ a las personas a evacuar la ciudad (tiempo de viaje de los más lentos). Hay 1 vehículo que puede contener $p$ gente y viajar a la velocidad de la más lenta persona del grupo. Una persona tiene que traer de vuelta el vehículo utilizado para el transporte.

Este problema es una generalización para el puente de cruce / de la antorcha problema.

He encontrado la solución para$p \leq 2$, lo que viene a ser la gente por el tiempo de viaje y recorrer de a pares si es mejor que el par de la gente a viajar juntos, con 2 corredores o para viajar por separado con 1 corredor.

He intentado adaptarlo a $p=3$, pero las cosas se intensificó rápidamente y que terminó con muchas de las estrategias para comparar, para cada grupo de 3 personas con 1, 2, 3 corredores y no podía encontrar una manera de generalizar para $p \geq 3$.

Answer 1

Me gustaría retirar el papel de La capacidad-$C$ antorcha problema (detrás de un paywall) y este similar (mismo?) el papel de La Capacidad-$C$ Antorcha Problema Versión completa (incluyendo todas las pruebas) (pdf) por Backhouse y Truong. Dado que la respuesta a tu pregunta es el objeto de estos trabajos de investigación, que sería difícil de sintetizar sus algoritmos en una respuesta aquí, así que no voy, pero parecen contener un algoritmo que resuelve la pregunta que se busca responder.

Resumen La antorcha problema (también conocido como el problema del puente o la linterna problema) se trata de obtener un número de personas a través de un puente tan rápido como sea posible bajo ciertas restricciones. Aunque muy resumidamente problema, la solución es sorprendentemente no-trivial. El caso en el que sólo hay cuatro personas y la capacidad del puente es de dos es un conocido rompecabezas, ampliamente difundida en Internet. Consideramos que el problema general en el que el número de personas, sus tiempos de cruce y de la capacidad del puente de todos los parámetros de entrada. Se presentan dos métodos para determinar el menor total de tiempo de cruce: el primero expresa el problema como un entero-programación de problema que puede ser resuelto por una lineal estándar-paquete de programación, y el segundo expresa el problema de ruta más corta problema en un grafo dirigido acíclico, es decir, como una dinámica de un problema de programación. La complejidad de los lineales-solución de programación es difícil de predecir; su finalidad principal es la de actuar como una prueba independiente de la exactitud de los resultados devueltos por el segundo método de solución. La dinámica de la solución de programación tiene la mejor y peor caso de tiempo de complejidad proporcional al cuadrado del número de personas. Una comparación empírica de la eficiencia de ambos métodos también se presenta.