Dijkstras Algorithmus < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:35 Di 27.07.2010 | | Autor: | Katrin89 |
| Aufgabe | Optm.problem:
max [mm] y^T*b
[/mm]
s.d. [mm] y^T*A<=d^T
[/mm]
d ist die Distanz |
Hallo,
wie der Algo abläuft weiß ich in etwa, aber es halt an der Bestimmung des minimalen Potential y:
Ablauf:
1) suche den Weg von s nach t, setze [mm] y_s=0 [/mm] und U={s}, lege die anderen Potentiale [mm] y_v [/mm] für v aus [mm] V\U [/mm] mit der Distanz von s nach v d_(sv)
2) solange U ungleich V gilt, wähle ein v aus [mm] V\U [/mm] mit minimalem Potential [mm] y_v, [/mm] setze U={u,v} und datiere auf:
[mm] y_w=min (y_w, y_v+d_(vw) [/mm] )
Ich weiß, dass [mm] y_v [/mm] der ausgehende Konten ist, für den vorher ein Minmum berechnet wurde und ich betrachte von diesem ausgehend die Distanz zu den anderen Knoten, die noch nicht in U sind.
Aber mir ist nicht klar, wie ich [mm] y_w [/mm] berechne. Es müsste mir der Entfernung von s nach w für alle w aus [mm] V\U [/mm] belegt werden.
Dazu eine Frage:
Wenn ich von s nach w gehe, gibt es auf diesem Weg irgendeine Einschränkung? Mein Vermutung ist, dass man nicht über den Knoten gehen kann, den man gerade betrachtet, der also neu in U aufgenommen wurde. Stimmt das?
Oh Gott, ich hoffe, ihr versteht, was ich meine!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:36 Fr 30.07.2010 | | Autor: | martin2 |
Also, im Grunde gehst du wie folgt vor.
Anfangs ist in deinem U nur der Startknoten drin, die Distanz zu ihm selber ist logischerweise 0. Nennen wir den Startknoten s. Nun guckst du dir alle von s ausgehenden Kanten (s,w) an und setzt für alle w [mm] y_{w} [/mm] auf c(s,w) wobei das die jeweiligen Kosten der Kante (s,w) darstellt. Für alle Knoten die du vom Startknoten aus nicht erreichts setzt du: [mm] y_{r} [/mm] = [mm] \infty [/mm] .
Nun suchst du dir die kürzeste Distanz aus U heraus und fügst diesen Knoten v zu U hinzu (also immer U= U [mm] \cup [/mm] {v} )
Du gehst nun analog vor und setzt für alle Kanten (v,w), die aus U herausführen (die die in U reinführen sind irrelevant, da du die minimalste Distanz dorthin schon kennst) [mm] y_{w} [/mm] = [mm] y_{v} [/mm] + c(v,w)
all das geschieht im Grunde durch die Minimumbetrachtung. Wenn der Knoten schon in U ist, dann wird [mm] y_{v} [/mm] + c(v,w) niemals kleiner sein und du kannst weitergehen. Ist der Knoten noch nicht in U (ist die Distanz sogar teilweise noch [mm] \infty [/mm] ) und logischerweise ist [mm] y_{v} [/mm] + c(v,w) kleiner.
Hoffe das war verständlich. Es gibt keine Beschränkung beim Suchen eines neuen Knotens oder Weges.
Gruß
Martin
|
|
|
|
