Informatiker Board | Algorithmen | Algorithmus zu Graph

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Algorithmus zu Graph

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Algorithmus zu Graph

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Algorithmus zu Graph

Zitatantwort auf diesen Beitrag erstellen

Hallo

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 01:44

Nehmen Sie Shizmo in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

__________________
Syntax Highlighting fürs Board (Link)

21.05.2016 06:45

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

eulerscheZahl hat dieses Bild (verkleinerte Version) angehängt:

__________________
Syntax Highlighting fürs Board (Link)

21.05.2016 09:03

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

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:07

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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

__________________
Syntax Highlighting fürs Board (Link)

21.05.2016 12:15

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Shizmo: 21.05.2016 12:27.

21.05.2016 12:27

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

__________________
Syntax Highlighting fürs Board (Link)

21.05.2016 13:05

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

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:11

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

__________________
Syntax Highlighting fürs Board (Link)

21.05.2016 20:24

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

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:46

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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.

__________________
Syntax Highlighting fürs Board (Link)

21.05.2016 20:52

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

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

21.05.2016 21:02

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Algorithmus zu Graph