Problema de la teoría de grafos (nombre desconocido)

7

Estoy tratando de resolver el siguiente tipo de problema. No sé si ya existe un nombre para esto, o una solución; Sin embargo, estoy dispuesto a apostar que hay. Esperaba que alguien pudiera indicarme la implementación de una solución, o al menos decirme el nombre del problema.

Supongamos que un viajero tiene una cierta cantidad de monedas de oro y algunas monedas de bronce. Debe comenzar una ciudad A, ir a la ciudad B, luego a la ciudad C y finalmente a la ciudad D.

Hay dos (o más) carreteras que pasan de A a B, etiquetadas como AB1 y AB2 (etc.). La carretera AB1 tiene un peaje de 5 monedas de oro, y AB2 tiene un peaje de 5 monedas de bronce.

Carreteras de la ciudad B a C: BC1 tiene un peaje de 10 monedas, que puede ser cualquiera de las dos monedas. BC2 requiere 8 monedas de oro.

Las carreteras de C a D tienen algún tipo de configuración similar.

Suponiendo que sabemos cuánto dinero tiene el viajero, y que no hay intercambio posible entre monedas de bronce y oro: ¿existe un método para determinar si el viajero tiene dinero suficiente para pasar de A a B, a C, y finalmente a D?

Este es el tipo de problema que necesito una solución para ... ¿Hay un nombre para este problema? ¿Hay una solución a este problema (aparte de la fuerza bruta)? Supongo que este es un problema similar a los problemas de flujo, pero no sé cómo abordarlo.

    
pregunta Serge 29.07.2013 - 19:34

4 respuestas

3

Si estoy leyendo su pregunta correctamente, su problema tiene dos propiedades interesantes:

  1. La gráfica está conectada secuencialmente, A- > B- > C- > D. Puede haber múltiples bordes entre los nodos, pero nunca hay bordes que "omitan" los nodos (A- > C, B- > D) o que vuelvan (C- > A).
  2. El objetivo final es la viabilidad frente a la optimalidad. Es decir, desea saber si un viajero tiene suficiente dinero en comparación con la ruta que menos cuesta absolutamente.

¿Eso es correcto? Si es así, hay algunos trucos disponibles.

Primero, calcula el valor esperado tanto en oro como en bronce entre cada ciudad. El valor esperado sería el mínimo que esperaría pagar. Dado que AB1 = 5 de oro, AB2 = 5 de bronce y AB3 = 10 de oro o de bronce (estoy agregando el camino para ilustrar un punto), nunca seleccionaría AB3. AB1 o AB2 le ofrecen una mejor solución, independientemente de la moneda que utilice. Por lo tanto, el valor esperado entre A y B es 5 de oro y 5 de bronce. El valor esperado entre B y C es 8 de oro y 10 de bronce. Nuevamente, nunca seleccionaríamos BC1 (10 de oro o bronce) cuando gastar oro como BC2 (8 de oro) siempre es más barato. Continúe calculando los valores esperados para el resto de su ruta.

A continuación, sume sus valores esperados para cada moneda. Básicamente, usted está actuando como si pagara todos los peajes usando un tipo de moneda, pero lo hace para ambos tipos en una sola pasada. Si sus valores esperados son:

  • A- > B 5 gold, 5 bronze
  • B- > C 8 oro, 10 bronce
  • C- > D 10 gold, 7 bronze

Sus totales son 23 de oro y 22 de bronce. Si comenzó con 23 o más de oro y 22 o más de bronce, ha terminado. Usted sabe que existe una solución viable. Es más probable que sus totales esperados sean mayores que las monedas disponibles.

En ese caso, haga una elección entre pares de valores esperados versus considerar ambas opciones. Si te queda poco oro, gasta el bronce donde más oro devuelve. Por ejemplo, si comienzo con 13 de oro, puedo seleccionar la opción de pago de bronce entre C- > D para crear una solución viable. Si comienzo con 5 de bronce, puedo seleccionar la opción de pago de oro entre B- > C y C- > D para crear una solución viable.

Una vez más, eso es probablemente una ilusión. Es probable que seas corto tanto en oro como en bronce. Si ese es el caso, comience con una heurística para resolver los valores esperados: si tiene un mayor déficit de oro, seleccione los valores esperados que produzcan los mayores ahorros en oro antes de resolver el bronce, intente compensar el déficit con la menor cantidad de "opciones" posibles. etc ... Al final, es posible que aún tenga que probar cada combinación de valores esperados para probar que una solución viable existe o no.

Tenga en cuenta que esto no tiene en cuenta los peajes que involucran a ambas monedas. Un peaje de 2 de bronce y 5 de bronce arruina mi truco de valor esperado.

    
respondido por el Corbin March 29.07.2013 - 23:28
3

No estoy seguro de que pueda estar relacionado con un algoritmo de flujo, porque un problema de flujo le permitiría ir parcialmente por la carretera AB1 y parcialmente por la carretera AB2, por ejemplo.

Creo que estás bastante estancado en la primera búsqueda profunda, pero tienes oportunidades para podar. Por ejemplo, si una carretera requiere 8 monedas de oro y otra entre las mismas dos ciudades requiere 10 monedas de oro, no necesita molestarse en atravesar esta última. Eso te deja con un camino de oro, uno de bronce y uno "cualquiera de los dos" entre cada ciudad. Además, tenga en cuenta que el orden en que visita las ciudades no importa desde el punto de vista del algoritmo. Si las rutas de CD tienen un costo mayor que las de AB, es posible que pueda acelerarlas moviéndolos primero.

    
respondido por el Karl Bielefeldt 29.07.2013 - 21:00
1

Si su viajero tuviera que volver al inicio, sería una variación del enlace . Como es, es sólo un problema de optimización de ruta. Lo abordaría utilizando Depth First Search , pero eso se debe a que es uno de los dos o tres algoritmos transversales de gráficos I recuerda de la escuela de posgrado.

    
respondido por el Dan Pichelman 29.07.2013 - 19:58
1

Es solo un problema de ruta más corto / costo mínimo declarado como un problema de decisión. Pero con un coste bidimensional. ¿Hay un camino que cueste menos que x monedas de oro y menos que y monedas de bronce?

Eso hace que el problema sea mucho más difícil de resolver en el caso general, ya que puede haber un gran número de posibles pares óptimos (oro, bronce) por nodo. El verdadero desafío en esto es lidiar con el costo bidimensional, la búsqueda de gráficos es parte, solo está ahí para contar la historia. Podría ser cualquier tipo de optimización.

    
respondido por el Patrick 29.07.2013 - 22:12

Lea otras preguntas en las etiquetas