cards-deck: 100-199_university::111-120_theoretic_cs::111_algorithms_datastructures

| Relaxation | Relaxieren |

anchored to [[111.00_anchor]]

Overview

[!Definition] Intuition von Relaxation was beschreiben wir damit, was wird für jeden Knoten gespeichert? #card Wir wollen für jeden Knoten einen Wert speichern, der mit $v.dist$ oder auch $\detlta(v)$ beschrieben wird. Dieser Wert dient dabei der derzeitig vermuteten Distanz von einem Ursprung zu dem ausgewählten Punkt $v$.

Zu Beginn setzen wir diesen dabei auf $\infty$, weil wir damit angeben dass es noch keinen Pfad gibt ( und weil wir später immer checken, ob es einen kleineren Wert gibt und es somit einfacher wird).

Führen wir die Funktion jetzt aus, checken wir folglich, ob es einen kürzeren Pfad gibt ^1704708762291

Wir tracken mit einer Relaxation also die derzeitige Distanz zu unserem ausgewählten Knoten $v$ vom Startpunkt $s$.

Umsetzung

[!Tip] Relaxation Ausführung wir haben das Konzept kürzere Kosten zu eine Punkt zu finden, wie setzen wir das um ? #card Generell ist der Ansatz: -> Herausfinden, ob wir den derzeit kürzesten Pfad verbessern können. Dabei betrachten wir die Kanten $(u,v)$, also jene, die von einem Punkt zu unserem jetzigen hinzeigen. Dadurch können wir dann herausfinden, ob (u,v) kürzer ist, als das derzeitig gespeicherte –> Es wird hierbei die Distanz aus $u$ entnommen und auf die Kosten der Kante $(u,v)$ hinzuaddiert! ^1704708762304

Wir können jetzt einen möglichen PseudoCode schreiben, der diesen Vergleich darstellt / definiert:

def Relax(u,v):
# wir prüfen, ob die neue Distanz kürzer ist
if v.dist > u.dist + w(u,v) # bzw bei uns v.dist > u.dist + c(u,v) 
	# sie ist kürzer, update also
	v.dist = u.dist+ w(u,v)
	v.Vorgaenger =u # wir speichern, also woher er zuvor gekommen ist!

Anwendung

Wir können dieses System immer dann verwenden, wenn wir Algorithmen betrachten, die irgendwie den kürzesten Pfad suchen ( SSSP/ASAP)

Wir finden ihn etwa in

• Bei Bellman-Ford