Was ist die Relaxationsbedingung in der Graphentheorie?

Question

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 mir bitte jemand erklären.

Ein Beispiel dafür ist Dijkstras-Algorithmus, hier ist der Pseudo-Code.

1 function Dijkstra(Graph, source): 
2  for each vertex v in Graph:   // Initializations 
3   dist[v] := infinity    // Unknown distance function from source to v 
4   previous[v] := undefined   // Previous node in optimal path from source 
5  dist[source] := 0      // Distance from source to source 
6  Q := the set of all nodes in Graph 
    // All nodes in the graph are unoptimized - thus are in Q 
7  while Q is not empty:     // The main loop 
8   u := vertex in Q with smallest dist[] 
9   if dist[u] = infinity: 
10    break       // all remaining vertices are inaccessible from source 
11   remove u from Q 
12   for each neighbor v of u:   // where v has not yet been removed from Q. 
13    alt := dist[u] + dist_between(u, v) 
14    if alt < dist[v]:    // Relax (u,v,a) 
15     dist[v] := alt 
16     previous[v] := u 
17  return dist[] 

Dank

Answer 1

Entspannung Schritt:

• Sie haben zwei Knoten, u und v
• Für jeden Knoten, haben Sie einen vorläufigen Abstand von dem Quellknoten (für alle Knoten mit Ausnahme der Quelle, es beginnt bei positiver Unendlichkeit und es verringert sich nur bis zum Erreichen seines Minimums).

Der Entspannungsschritt im Grunde fragt diese:

• Ich weiß schon, dass ich v mit einem gewissen Weg des Abstandes dist[v] erreichen kann. Könnte ich das verbessern, indem ich stattdessen v durch u gehe? (Wobei der Abstand der letzteren wäre dist[u] + weight(u, v))

Grafisch:

s ~~~~~~~> v 
\  ^
    \  | 
    \~~~~~> u 

Sie kennen einige Pfade s~>v die dist[v] distanziert hat, und Sie wissen, einigen Weg s~>u die dist[u] hat distanzieren. Wenn dist[u] + weight(u, v) < dist[v], dann ist der Pfad s~>u->v kürzer als s~>v, also sollten Sie besser dieses verwenden!

(I a~>b schreibe aus a zu b einen Pfad von jeder Länge bedeuten, während a->b meine ich eine direkte Einfach Kante von a bis b).

Sie können auch diesen Vortrag überprüfen möchten: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed17.htm

Answer 2

Eine der Bedeutungen des Englisch Wort „Entspannung“ etwas abnimmt. 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 der Grund für die "Entspannungsbedingung" ist.