Informatiker Board | Druckvorschau: Algorithmus zu Graph

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Algorithmus zu Graph (http://www.informatikerboard.de/board/thread.php?threadid=3039)

Geschrieben von Shizmo am 21.05.2016 um 01:44:

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

Geschrieben von eulerscheZahl am 21.05.2016 um 06:45:

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.

Geschrieben von eulerscheZahl am 21.05.2016 um 09:03:

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.

Geschrieben von Shizmo am 21.05.2016 um 12:07:

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

Geschrieben von eulerscheZahl am 21.05.2016 um 12:15:

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

Geschrieben von Shizmo am 21.05.2016 um 12:27:

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

Geschrieben von eulerscheZahl am 21.05.2016 um 13:05:

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.

Geschrieben von Shizmo am 21.05.2016 um 20:11:

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?

Geschrieben von eulerscheZahl am 21.05.2016 um 20:24:

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.

Geschrieben von Shizmo am 21.05.2016 um 20:46:

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

Geschrieben von eulerscheZahl am 21.05.2016 um 20:52:

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.