Я пытаюсь понять основное понятие теории графов и алгоритмов в ней. Большинство алгоритмов, кажется, содержит "Релаксационное Условие", я не уверен в том, каково это.
Мог кто-то объяснять это мне.
Примером этого является dijkstras алгоритм, вот псевдокод.
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[]
Спасибо
Шаг расслабления:
u
и v
На этапе релаксации в основном задается следующий вопрос:
v
некоторым путем на расстоянии dist [v]
. Могу я улучшить это, перейдя к v
через u
? (где расстояние последнего будет dist [u] + weight (u, v)
) Графически:
s ~~~~~~~> v
\ ^
\ |
\~~~~~> u
Вы знаете некоторый путь s ~> v
, который имеет расстояние dist [v]
, и вам известен некоторый путь s ~> u
, который имеет расстояние dist [u]
. Если dist [u] + weight (u, v)
s ~> u-> v
короче, чем s ~> v
, так что лучше воспользуйтесь этим!
(Я пишу a ~> b
, чтобы обозначить путь любой длины от a
до b
, а a-> b
Я имею в виду прямое одиночное ребро от a
до b
).
Вы также можете проверить эту лекцию: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed17.htm
Одно из значений английского слова «релаксация» - что-то уменьшать. Поскольку в строках 14,15 и 16 вы, по сути, проверяете, можете ли вы уменьшить (оптимизировать) текущее вычисленное расстояние, я думаю, поэтому это называется «условием релаксации».