Ich versuche die Hauptbegriffe der Graphentheorie und der darin enthaltenen Algorithmen zu verstehen. Die meisten Algorithmen scheinen einen "Entspannungszustand" zu enthalten. Ich bin mir nicht sicher, was das ist.
Könnte jemand mir das bitte erklären?
Ein Beispiel dafür ist der Dijkstras-Algorithmus, hier ist der Pseudo-Code.
%Vor%Danke
Entspannungsstufe:
u und v
Der Entspannungsschritt stellt im Grunde folgendes:
v mit einem Pfad der Entfernung dist[v] erreichen kann. Könnte ich das verbessern, indem ich stattdessen zu v bis u gehe? (wo der Abstand der letzteren wäre dist[u] + weight(u, v) ) Grafisch:
%Vor% Sie kennen einen Pfad s~>v , der den Abstand dist[v] hat, und Sie kennen einen Pfad s~>u , der den Abstand dist[u] hat. Wenn dist[u] + weight(u, v) < dist[v] , dann ist der Pfad s~>u->v kürzer als s~>v , also solltest du diesen besser verwenden!
(Ich schreibe a~>b als Pfad von any Länge von a bis b , während a->b eine direkte einzelne Kante von a bis b ).
Sie können auch diese Vorlesung lesen: Ссылка
Eine der Bedeutungen des englischen Wortes "Entspannung" nimmt etwas ab. Da Sie in den Zeilen 14, 15 und 16 im Wesentlichen prüfen, ob Sie die aktuell berechnete Entfernung verringern (optimieren) können, nehme ich an, dass dies deshalb "Entspannungszustand" genannt wird.
Tags und Links graph-theory graph condition