Sugerir un algoritmo (gráfico - posiblemente NP-completo)

Question

Hay una red de ciudades conectadas por carreteras de varias longitudes enteras.

Un viajero desea viajar en su automóvil de una ciudad a otra. Sin embargo, él no quiere minimizar la distancia recorrida; en su lugar, desea minimizar el costo de gasolina del viaje. La gasolina se puede comprar en cualquier ciudad, sin embargo, cada ciudad suministra gasolina a varios precios (enteros) (de ahí que la ruta más corta no sea necesariamente la más barata). 1 unidad de gasolina le permite conducir por 1 unidad de distancia. Su automóvil solo puede contener tanta gasolina en el tanque, y puede elegir cuántas unidades de gasolina comprar en cada ciudad por la que viaja. Encuentre el costo mínimo de gasolina.

¿Alguien sabe un algoritmo eficiente que podría utilizarse para resolver este problema? ¡Incluso el nombre de este tipo de problema sería útil para que yo pueda investigarlo! Obviamente, no es exactamente lo mismo que un problema de ruta más corta. Cualquier otro consejo apreciado!

EDITAR - el problema real que tengo indica que habrá < 1000 ciudades; < 10000 carreteras; y la capacidad del tanque de gasolina estará en algún lugar entre 1 y 100.

Answer 1

Creo que la pregunta es: ¿hay alguna posibilidad de que el petróleo haga que el problema subyacente del vendedor viajante sea más factible desde el punto de vista computacional? De lo contrario, no existe un algoritmo eficiente que no se aproxime.

Por supuesto, puede encontrar soluciones eficientes para cajas de borde, y podría haber más cajas de borde con la condición de gasolina, como en, siempre tome esta ciudad primero porque la gasolina es tan barata.

Answer 2

Creo que puede resolver esto con programación dinámica. Para cada nodo, guarda una matriz de tuplas del costo de la gasolina y la longitud de la ruta donde usa esa gasolina, que contiene la solución óptima. Cada paso que recorre a través de todos los nodos y si hay un nodo que puede ir, que ya tiene una solución, recorre todos los nodos a los que puede acceder con una solución. Seleccione el costo mínimo, pero tenga en cuenta: debe contabilizar el costo de gasolina en el nodo actual. Todos los costos en la matriz que son más altos que el costo en el nodo actual, en cambio, se pueden comprar en el nodo actual. Tenga en cuenta que los nodos que ya tienen una solución deben ser recalculados, ya que los nodos a los que puede acceder desde allí podrían cambiar. Comienza con el nodo final, estableciendo la solución en una matriz vacía (o una entrada con costo y longitud 0). La solución final es tomar la solución al principio y resumir cada costo * de longitud.

Answer 3

me gustaría probar este:

1. encontrar la ruta más corta desde el principio hasta el destino. El algoritmo de Dijkstra es apropiado para esto.
2. Encuentra el costo mínimo de gasolina para viajar en esta ruta. No conozco ningún algoritmo disponible para esto, pero a menos que haya muchas ciudades a lo largo de la ruta, incluso una búsqueda exhaustiva no debería ser computacionalmente inviable.
3. Buscar la siguiente ruta más corta ...

Definición de criterios de parada precisa es un poco de un desafío, podría ser mejor sólo para detener una vez que el costo mínimo encontrado una ruta probado recientemente es mayor que la costo mínimo para una ruta ya probada.

Entonces, use 2 algoritmos, uno para cada parte del problema.

Answer 4

Puede resolver esto directamente usando Djikstra's algorithm si está contento de aumentar el tamaño del gráfico.

Supongamos que su tanque de gasolina podría contener de 0 a 9 unidades de gasolina.

La idea sería dividir cada ciudad en 10 nodos, con el nodo x para que la ciudad t represente en la ciudad t con x unidades de gasolina en el tanque.

Puede construir bordes de costo cero en este gráfico expandido para representar el desplazamiento entre diferentes ciudades (usando gasolina en el proceso para pasar de un nodo de nivel 8 a un nodo de nivel 5 si la distancia era 3), y más bordes para representar el llenado del tanque en cada pueblo con una unidad de gasolina (con un costo que depende de la ciudad).

Luego, la aplicación de Djikstra debería ofrecer la ruta de menor costo desde el principio hasta el final.

Answer 5

Esto podría optimizarse adecuadamente usando un Algoritmo Genético. Algoritmos genéticos golpearon los seres humanos en algunos problemas complejos: http://en.wikipedia.org/wiki/Genetic_algorithm

La esencia de un Algoritmo Genético es:

1. llegar a una función de clasificación de soluciones candidatas
2. llegar a un conjunto de soluciones candidatos únicos . Inicialícelo con algunas posibilidades generadas aleatoriamente. Tal vez 10 o 100 o 1000 ...
3. Copie una solución candidata de la agrupación y perturbe de alguna manera - Agregue una ciudad, elimine una ciudad, agregue dos ciudades, etc. Esto podría mejorar o empeorar las cosas - tu función de clasificación te ayudará a saberlo. ¿Cuál escoges? Por lo general, usted elige lo mejor, pero de vez en cuando, elige intencionalmente uno que no sea para evitar quedarse atascado en un óptimo local.
4. ¿Ya se ha calificado la nueva solución? Si es así, no deseado e ir a
   1. Si no, continuar ...
5. Añadir al candidato perturbado de nuevo a la piscina bajo su rango calculado recién
6. Continuar en esta (repita desde el # 3) hasta que sienta que lo ha hecho lo suficiente
7. Finalmente, seleccione la respuesta con la mejor clasificación. Puede no ser óptimo, pero debería ser bastante bueno.

Answer 6

También podría formular eso como un problema de programación lineal entera (ILP). La ventaja es que hay una cantidad de solucionadores disponibles para esta tarea y la complejidad no crecerá tan rápido como en el caso de la solución de Peters con el tamaño del tanque.

Las variables en este problema en particular serán las cantidades de gasolina comprada en cualquier ciudad, la cantidad en el tanque de automóviles en cualquier ciudad en el camino y las carreteras reales tomadas. Las restricciones deberán garantizar que el automóvil gaste el combustible necesario en cada carretera y no tenga menos de 0 o más que MAX unidades de combustible en cualquier ciudad y que las carreteras constituyan una ruta de A a B. El objetivo ser el costo total del combustible comprado.

Todo esto puede parecer monstruoso (las formulaciones de ILP a menudo sí lo hacen), pero eso no significa que no pueda resolverse en un tiempo razonable.