| Die letzten 10 Beiträge |
| Shizmo |
Alles klar, vielen, vielen Dank!! Du hast mir wie immer sehr geholfen!!! 
|
| 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. |
| Shizmo |
Ah okay danke!!!
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 |
| 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. |
| 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? |
| 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. |
| 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 |
|
|
| 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 |
| 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 |
| 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.
eulerscheZahl hat dieses Bild (verkleinerte Version) angehängt:
|
| Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen. |
|
|
