Algorithmus zu Graph

Neue Frage »

21.05.2016, 01:44

Auf diesen Beitrag antworten »

Shizmo

Algorithmus zu Graph

Hallo Wink

Zitat:

Gegeben ist ein Straßennetz, welches als gerichteter Graph [latex]G=(V,E)[/latex]

dargestellt wird. Dabei ist jeder Kante $[latex](u,v)\in E[/latex]$ ein Wert $[latex]stau(u,v)\in[0,1][/latex]$ zugeordnet. Dieser gibt die Wahrscheinlichkeit an, dass auf diesem Streckenabschnitt morgens im Berufsverkehr Stau sein wird. Die Wahrscheinlichkeiten von Stau pro Streckenabschnitt ist unabhängig.

Geben Sie einen Algorithmus an, der von einem Startpunkt [latex]s[/latex]

den Weg mit der höchsten Stauwahrscheinlichkeit berechnet.

Also meine erste Idee war eine for each Schleife die über die Adjazenzliste vom Startpunkt geht und immer den Weg mit Kantengewicht 1 wählt und dann sich selber wieder rekursiv aufruft, also so dass es sich so lang in den "Keller" gräbt, bis keine Kante mit 1 mehr da ist.
Aber, vermutlich komm ich da nicht weit, da es ja dazwischen auch Kanten mit Gewicht 0 geben kann und es dann trotzdem noch weiter gehen kann.

Zweite Idee ist evtl den Algorithmus von Dijkstra zu missbrauchen, also einfach immer den Weg mit dem höchsten Gewicht, anstatt dem niedrigsten Gewicht zu nehmen. Könnte das funktionieren?

Nur irgendwie finde ich ist die Angabe nicht gut beschrieben, ich soll einen Weg ausgeben mit der höchsten Stauwahrscheinlichkeit. Von s nach? Oder einfach allgemein vom ganzen Straßennetz??? Macht irgendwie wenig Sinn... unglücklich

21.05.2016, 06:45

Auf diesen Beitrag antworten »

eulerscheZahl

Zunächst einmal würde ich fordern, dass der Graph kreisfrei ist. Sonst könnte man ja im Kreis fahren, bis man in einen Stau kommt.
Dijkstra (oder andere mir bekannte Algorithmen) kannst du hier nicht verwenden, weil man Wahrscheinlichkeiten multipliziert, nicht addiert.

Meine erste Idee wäre, per Tiefensuche jeden möglichen Pfad von s zu einem Blatt zu bilden und die Wahrscheinlichkeiten auszurechnen. Dabei darf in einem Pfad kein Knoten doppelt vorkommen.
Allerdings könnte ich dir auch einen Graphen nennen, bei dem das exponentielle Laufzeit hat.
Mal schauen, ob mir noch was besseres einfällt.

21.05.2016, 09:03

Auf diesen Beitrag antworten »

eulerscheZahl

Ich habe nochmal drüber nachgedacht.
Das Problem bei Dijkstra ist, dass ein besserer Weg existieren kann, aber durch die frühe Wahl des nächsten Knotens ausgeschlossen wird.
Beispiel (siehe Anhang):
Dijkstra wählt Knoten 2 als erstes. Aber von 1 aus ist die Stauwahrscheinlichkeit nach 2 größer, als vom Start aus. Das entspricht den negativen Kantengewichten bei der Addition.
Bellman-Ford sollte aber einen maximalen Stau finden können. Da hast du auch gleich den Wert zu jedem anderen Knoten ausgerechnet.

21.05.2016, 12:07

Auf diesen Beitrag antworten »

Shizmo

Hey, vielen Dank für deine Antwort!
Also ich hab mal das:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:

  für jedes v aus V
      Distanz(v) := unendlich, Vorgänger(v) := keiner
  Distanz(s) := 0

  wiederhole n-1 mal
     für jedes (u,v) aus E
           wenn (Distanz(u) + Gewicht(u,v)) < Distanz(v) dann
              Distanz(v) := Distanz(u) + Gewicht(u,v)
              Vorgänger(v) := u

in das geändert:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:

  für jedes v aus V
      Distanz(v) := 1, Vorgänger(v) := keiner
  Distanz(s) := 0

  wiederhole n-1 mal
     für jedes (u,v) aus E
           wenn (Distanz(u) * Gewicht(u,v)) < Distanz(v) dann
              Distanz(v) := Distanz(u) * Gewicht(u,v)
              Vorgänger(v) := u

D.h. bei deinem Beispielgraph:

Distanz(2) = 0.2 - Vorgänger(2) = s
Distanz(1) = 0.1 - Vorgänger(1) = s
---
Distanz(2) = 0.05 - Vorgänger(2) = 1
Distanz(t) = 0.005 - Vorgänger(t) = 2

Nur ich frage mich noch, warum man das multipliziert, dadurch werden die Wahrscheinlichkeiten ja weniger anstatt mehr. Denn der Weg nach 2, müsste ja über 1 länger dauern und das tut es ja auch nach dem Algorithmus, also die Vorgänger sagen das zumindest aus, aber 0.2 > 0.05.

LG

21.05.2016, 12:15

Auf diesen Beitrag antworten »

eulerscheZahl

Du musst mit der Gegenwahrscheinlichkeit rechnen:
P(Stau auf s-1-2-t Weg) = 1 - (1-0.1) * (1-0.5) * (1-0.1) = 0.595
P(Stau auf s-2-t Weg) = 1 - (1-0.2) * (1-0.1) = 0.28

21.05.2016, 12:27

Auf diesen Beitrag antworten »

Shizmo

Hmm okay, also so?

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:

  für jedes v aus V
      Distanz(v) := 1, Vorgänger(v) := keiner
  Distanz(s) := 0

  wiederhole n-1 mal
     für jedes (u,v) aus E
           wenn (Distanz(u) * (1 - Gewicht(u,v)) ) < Distanz(v) dann
              Distanz(v) := Distanz(u) * (1 - Gewicht(u,v)) 
              Vorgänger(v) := u

21.05.2016, 13:05

Auf diesen Beitrag antworten »

eulerscheZahl

Distanz(s) = 0
Mit deiner Formel multiplizierst du immer mit 0, sodass alle Werte 0 werden.

Setze zu Beginn alle Werte auf 0. (Das heißt, es gibt nirgendwo Stau. Sonst hättest du ja sicher Stau).
wenn (1 - (1 - Distanz(u)) * (1 - Gewicht(u,v))) > Distanz(v) dann
...
hier musst du schauen, ob du eine größere Stauwahrscheinlichkeit findest. Die Formel habe ich auch geändert.

21.05.2016, 20:11

Auf diesen Beitrag antworten »

Shizmo

Ups, hatte mit Distanz(s)=1 begonnen.

Aber ja du hast recht, dann wäre ja überall Stau.
So wie du gesagt hast funktioniert es auf jeden Fall.
Vielen Dank soweit!

Ich weiß nur noch nicht wieso du mit Gegenwahrscheinlichkeiten rechnest, also ja es ist schon klar, sonst werden die Zahlen kleiner und dann macht das keinen Sinn mehr, aber wie begründest du das?

21.05.2016, 20:24

Auf diesen Beitrag antworten »

eulerscheZahl

Wir haben zwei Wahrscheinlichkeiten:
p_Knoten ist die Wahrscheinlichkeit, dass du bereits im Stau standest, bevor du den Knoten erreicht hast
p_Kante ist die Wahrscheinlichkeit, dass entlang der Kante Stau ist.

Was uns interessiert, ist, ob es Stau gibt. Der kann beim Knoten, bei der Kante oder bei beidem sein.
Also P(Stau) = 1-P(kein Stau) = 1-(kein Stau bei Knoten) * (kein Stau bei Kante) = 1-(1-p_Knoten)*(1-p_Kante)

Alternativ: P(Stau) = p_Knoten + p_Kante - p_Knoten*p_Kante.
Addiere die Einzelwahrscheinlichkeiten und ziehe die Schnittmenge wieder ab.

Durch Umformung wirst du sehen, dass beide Formeln gleich sind.

21.05.2016, 20:46

Auf diesen Beitrag antworten »

Shizmo

Ah okay danke!!! Daumen hoch

Eine Frage gibt es noch, für was brauch ich die Zeile:

code:
1:	wiederhole n − 1 mal

Ist ja nachdem ersten Durchgang schon alles richtig berechnet oder irre ich mich??

LG

21.05.2016, 20:52

Auf diesen Beitrag antworten »

eulerscheZahl

Du irrst dich.
Es wird von jedem Knoten aus der nach aktuellem Stand beste Weg berechnet.
Für meinen Beispielgraphen: wenn du die Knoten in der Reihenfolge (s, 1, 2, t) durchgehst, reicht ein Durchgang.
machst du aber (t, 2, 1, s), hast du nach dem ersten Durchgang nur die Werte für s und 1 richtig. Beim nächsten Durchlauf reparierst du Knoten 2. Erst im dritten Durchgang kommst du dann mit dem richtigen Wert von 2 nach t.
Wenn du die topologische Sortierung kennst, kannst du je nach Graphen sicher noch was machen, um die Durchläufe zu reduzieren. Aber in der einfachen Variante wiederholst du einfach stupide.

21.05.2016, 21:02

Auf diesen Beitrag antworten »

Shizmo

Alles klar, vielen, vielen Dank!! Du hast mir wie immer sehr geholfen!!! Daumen hoch

Neue Frage »

Antworten »

Algorithmus zu Graph

Verwandte Themen