Was ist der Entspannung Zustand in der Graphentheorie

Ich versuche zu verstehen die wichtigsten Konzepte der Graphen-Theorie und die algorithmen, die innerhalb es. Die meisten algorithmen scheinen, um eine "Entspannung Zustand" ich bin unsicher, was das ist.

Könnte jemand es mir erklären, bitte.

Ein Beispiel HIERFÜ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

InformationsquelleAutor alchemey89 | 2010-04-07
  1. 37

    Entspannung Schritt:

    • Sie haben zwei Knoten u und v
    • Für jeden Knoten, Sie haben eine vorläufig Abstand aus dem Quell-Knoten (für alle Knoten außer für die Quelle, es beginnt bei der positiven Unendlichkeit und es nur sinkt bis zum erreichen seiner minimum).

    Entspannung Schritt im Grunde ist diese Frage:

    • Ich weiß schon, dass ich erreichen kann v mit einem Weg der Entfernung dist[v]. Könnte ich verbessern, indem Sie zu v durch u statt? (wo der Abstand der letzteren wäre dist[u] + weight(u, v))

    Grafisch:

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

    Wissen Sie einige Pfad s~>v die Entfernung dist[v], und Sie wissen, einige Pfad s~>u die Entfernung dist[u]. Wenn dist[u] + weight(u, v) < dist[v], dann ist der Weg s~>u->v ist kürzer als s~>v, so würden Sie besser verwenden!

    (Ich Schreibe a~>b bedeutet, einen Weg der alle Länge von a zu b, während a->b ich meine eine direkte single edge von a zu b).

    Möglicherweise möchten Sie auch zu überprüfen, in diesem Vortrag: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed17.htm

    • Freut mich zu hören (hoffentlich habe ich nicht zu verwechseln Sie mit den Tippfehler, der jetzt behoben ist). Sie könnte auch durch drücken der tick-symbol auf der linken Seite zu markieren, dies als die richtige Antwort, wenn Sie denken, es ist (ich sicherlich denke, es ist :))
    InformationsquelleAutor Dimitris Andreou
  2. 10

    Einer der Bedeutungen des englischen Wortes "Entspannung" sinkt etwas. Denn bei Linien 14,15 und 16 sind im wesentlichen geprüft, ob Sie verringert werden kann(Optimierung) der aktuell berechneten Abstand, ich denke, das ist, warum es heißt "Entspannung Zustand".

    InformationsquelleAutor Petar Minchev
Schreibe einen Kommentar