¿Cuál es el significado de los bordes de peso negativo en un gráfico?

15

Estaba haciendo ejercicios de programación dinámica y encontré el algoritmo Floyd-Warshall. Aparentemente, encuentra los caminos más cortos de todos los pares para un gráfico que puede tener bordes de peso negativos, pero no ciclos negativos.

Entonces, me pregunto cuál es el significado real de los bordes de peso negativo. Una explicación sencilla en inglés sería útil.

c2h5oh
fuente
3
El peso de las aristas puede representar todo en el mundo real, por ejemplo, la cantidad de dinero que se transfiere de una cuenta a otra puede ser positiva o negativa, por ejemplo, si quiere hacer algo significa que debe ir de a-> b en su gráfico con perder el dinero más bajo posible (ruta más corta), entonces puede considerar un peso negativo ... por ejemplo, vea este capítulo del libro que contiene algunas muestras: informit.com/articles/article.aspx?p=169575&seqNum=8
entonces si a ---- (2) ----> b ---- (- 2) ----> c y a ----- (1) ----> c y para ir de aa c, ¿debo elegir la ruta abc ya que el costo total es 0? porque es el camino más corto. corrígeme si estoy equivocado !
c2h5oh
por ejemplo, supongamos que si haciendo el trabajo al pasar del estado de una a b cuesta 2 $ (por ejemplo, el trabajo está comprando libro cuesta 2 $ ), después de que se puede hacer algún proyecto (que gana 2 $ , la función de los medios costo es - 2), luego logró su propósito (ser profesional o c), luego el costo total es 0 y está en su estado. a - (+ 2) -> b - (- 2) -> c: +2 - 2 = 0 (costo total de a: novato, a c: profesional). e(ab)ab2$$PS
así que mi suposición es correcta, incluso si tenemos que viajar 1 borde más, elegiremos abc en lugar de ac.am, ¿verdad?
c2h5oh
Sí, exactamente, su suposición es correcta. Tenga en cuenta que puede leer un poco más (como el enlace que le proporcioné) o en nuestra discusión puede responder su propia pregunta y marcarla como respuesta aceptada.

Respuestas:

16

Saeed Amiri ya ha dado un excelente ejemplo en un comentario: el peso en los bordes puede representar cualquier cosa en el mundo real, por ejemplo, la cantidad de dinero que se transferirá de una cuenta a otra. Las cantidades pueden ser positivas o negativas. Por ejemplo, si desea ir de a b en su gráfico mientras pierde la menor cantidad de dinero posible (ruta más corta), puede considerar los pesos negativos. Para más información, vea este capítulo del libro .unsi

Aparte de eso, hay muchas más aplicaciones. Los pesos negativos dependen de lo que modeles para ser. Por ejemplo, considere este gráfico

ingrese la descripción de la imagen aquí

  • Química: los pesos se pueden usar para representar el calor producido durante una reacción química. (Modos: compuestos, borde : si el compuesto v se puede obtener ("químicamente reducido") de u . En este gráfico: produce 4 kJ para convertir s - a y 2 kJ para convertir a a t . Necesita 5 kJ para regresar s de t .mituvvtu4 4s-un2unt5 5st

  • Vida Real: Piense en un conductor, que se le paga para conducir su patrón de a t pero se paga entre una y B (digamos que viaja entre su domicilio y su lugar de trabajo).stunsi

  • Juegos: supongamos que juegas piedra-papel o tijera por dinero. Nodos: piedra, papel, tijeras. Bordes: cualquier relación (camarilla). Pesos: apuesta. En este gráfico: (olvídate de ), aquí, s supera a , a supera a t y t supera a s , y gana 4,2, -5 respectivamente.sisununtts

Subhayan
fuente
Hola gracias por la respuesta ¿Alguien puede explicar el ejemplo piedra-papel-tijera? ¿Cómo se les ocurrieron los pesos 4, 2, -5 para ellos?
Saurabh Goyal
3

No soy un tipo de química, pero aún así creo que este ejemplo valdrá la pena para ayudarlo a pensar fuera del procesador, la teoría de la red y otras cosas relacionadas.

Considere un gráfico que simule el comportamiento de una molécula en una reacción química, es decir, qué caminos puede tomar durante la reacción y los pesos representa la energía absorbida o liberada en la transición, por lo que si queremos que la energía salga de la reacción representamos energía liberada con + cinco pesos y absorbidos energía con -ve.

pj
fuente
1

ingrese la descripción de la imagen aquí

Un borde negativo es simplemente un borde que tiene un peso negativo. Podría estar en cualquier contexto relacionado con el gráfico y a qué se refieren sus bordes. Por ejemplo, el CD de borde en el gráfico anterior es un borde negativo. Floyd-Warshall funciona minimizando el peso entre cada par del gráfico, si es posible. Entonces, para un peso negativo, simplemente podría realizar el cálculo como lo habría hecho para los bordes de peso positivo.

El problema surge cuando hay un ciclo negativo. Echa un vistazo a la gráfica de arriba. Y hágase la pregunta: ¿cuál es el camino más corto entre A y E? Al principio, puede sentir que ABCE cuesta 6 (2 + 1 + 3). Pero, en realidad, observando más profundamente, observarías un ciclo negativo, que es BCD. El peso de BCD es 1 + (- 4) +2 = (-1). Mientras recorro de A a E, podría seguir pedaleando dentro de BCD para reducir mi costo en 1 cada vez. Al igual, la ruta A (BCD) BCE cuesta 5 (2 + (- 1) + 1 + 3). Ahora, repetir el ciclo infinitas veces seguiría reduciendo el costo en 1 cada vez. Podría lograr un camino negativo infinito más corto entre A y E.

El problema es evidente para cualquier ciclo negativo en un gráfico. Por lo tanto, cada vez que hay un ciclo negativo, el peso mínimo no está definido o es infinito negativo, por lo que Floyd-Warshall no puede funcionar en tal caso.

Como complemento, es posible que desee echar un vistazo al algoritmo de Bellman-Ford que detecta si un gráfico tiene un ciclo negativo o no y, de lo contrario, devuelve el camino más corto entre dos nodos.

divanshu
fuente
44
No creo que esto responda la pregunta. La pregunta no es "por qué un ciclo negativo es un problema", sino más bien "por qué uno tendría bordes con pesos negativos en la vida real".
Juho
0

Por ejemplo, imagine una red logística donde el peso w (i, j) de una arista ij es el costo para pasar del vértice i al vértice j. Si hiciera un acuerdo comercial con otras compañías para transportar sus productos, w (i, j) sería una ganancia en lugar de un costo, por lo que puede interpretar este peso como un costo negativo.

Luis Pargas Carmona
fuente
-2

Congestión de tráfico en un mapa:

Otro ejemplo del mundo real de asociar pesos a un borde podría ser que los pesos representan las condiciones del tráfico en un mapa (más negativo, más desfavorable); podríamos usar esta representación para calcular distancias óptimas.

Realmente podemos usar la metáfora del "peso" para representar cualquier cosa de valor positivo / negativo entre dos puntos en un gráfico

Ranga
fuente
Bienvenido al sitio! No creo que este sea un muy buen ejemplo. En el caso de la congestión del tráfico, parece más natural pesar los bordes en el mapa por el tiempo que toma viajar por la carretera, por lo que una congestión alta conduciría a un alto peso. Después de todo, el objetivo generalmente es llegar al destino rápidamente y uno preferiría tomar un camino corto pero congestionado en lugar de un camino no congestionado mucho más largo. Además, normalmente queremos usar el menor costo como métrica: eso funciona bien con la ponderación que sugerí, y muy mal con la que usted sugirió.
David Richerby