Уровень алгоритма

Алгоритм Δ-шагания: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][досмотренная версия]
(Общее описание алгоритма)
 
 
(не показано 14 промежуточных версий 3 участников)
Строка 1: Строка 1:
== Свойства и структура алгоритмов ==
+
{{level-a}}
 +
== Свойства и структура алгоритма ==
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
  
Алгоритм дельта-шагания<ref>Meyer, U, and P Sanders. “Δ-Stepping: a Parallelizable Shortest Path Algorithm.” Journal of Algorithms 49, no. 1 (October 2003): 114–52. doi:10.1016/S0196-6774(03)00076-2.</ref> предназначен для решения [[Поиск кратчайшего пути от одной вершины (SSSP)|задачи поиска кратчайшего пути на графе]]. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм изначально проектировался с целью эффективной параллелизации.
+
'''Алгоритм дельта-шагания'''<ref>Meyer, U, and P Sanders. “Δ-Stepping: a Parallelizable Shortest Path Algorithm.” Journal of Algorithms 49, no. 1 (October 2003): 114–52. doi:10.1016/S0196-6774(03)00076-2.</ref> (англ. Δ-Stepping) предназначен для решения [[Поиск кратчайшего пути от одной вершины (SSSP)|задачи поиска кратчайшего пути на графе]]. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм изначально проектировался с целью эффективной параллелизации.
  
=== Математическое описание ===
+
=== Математическое описание алгоритма ===
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
 
=== Макроструктура алгоритма ===
 
=== Макроструктура алгоритма ===
=== Описание схемы реализации последовательного алгоритма ===
+
=== Схема реализации последовательного алгоритма ===
 +
Псевдокод последовательного алгоритма:
 +
 +
'''Входные данные''':
 +
  граф с вершинами ''V'', рёбрами ''E'' с весами ''W'';
 +
  вершина-источник ''u'';
 +
  параметр ''Δ'' > 0.
 +
'''Выходные данные''': расстояния ''d''(''v'') до каждой вершины ''v'' ∈ ''V'' от вершины ''u''.
 +
 +
'''procedure''' DeltaStepping(''V'', ''E'', ''W'', ''u'', ''Δ''):
 +
      ''LightEdges'' := { e ∈ E | W(e) ≤ Δ }
 +
      ''HeavyEdges'' := { e ∈ E | W(e) > Δ }
 +
      '''for each''' ''v'' ∈ ''V'' '''do''' ''d''(''v'') := ∞
 +
      Relax(''u'', 0)
 +
      '''while''' any({ ''Buckets''(i) ≠ ∅ }):
 +
          ''Bucket'' := first({ ''Buckets''(i) ≠ ∅ })
 +
          ''Deleted'' := ∅
 +
          '''while''' ''Bucket'' ≠ ∅:
 +
              ''Requests'' := FindRequests(''Bucket'', ''LightEdges'')
 +
              ''Deleted'' := ''Deleted'' ∪ ''Bucket''
 +
              ''Bucket'' := ∅
 +
              RelaxAll(''Requests'')
 +
          RelaxAll(FindRequests(''Deleted'', ''HeavyEdges''))
 +
         
 +
'''procedure''' Relax(''v'', ''x''):
 +
    '''if''' ''x'' < ''d''(''v''):
 +
        ''OldBucket'' := B(⌊''d''(''v'') / ''Δ''⌋)
 +
        ''NewBucket'' := B(⌊''x'' / ''Δ''⌋)
 +
        ''OldBucket'' := ''OldBucket'' \ {''v''}
 +
        ''NewBucket'' := ''NewBucket'' ∪ {''v''}
 +
        ''d''(''v'') := ''x''
 +
       
 +
'''procedure''' RelaxAll(''R''):
 +
    '''for each''' (''v'', ''x'') ∈ ''R'' '''do''' Relax(''v'', ''x'')
 +
   
 +
'''function''' FindRequests(''V<nowiki>'</nowiki>'', ''E<nowiki>'</nowiki>''):
 +
    '''return''' { (''w'', ''d''(''w'') + ''W''(''v'', ''w'')) | ''v'' ∈ ''V<nowiki>'</nowiki>'' and (''v'', ''w'') ∈ ''E<nowiki>'</nowiki>''}
 +
 
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
  
Строка 13: Строка 51:
  
 
=== Информационный граф ===
 
=== Информационный граф ===
=== Описание ресурса параллелизма алгоритма ===
+
=== Ресурс параллелизма алгоритма ===
  
 
Средняя время работы параллельного алгоритма на графах со случайными весами на <math>O(n)</math> процессорах составляет <math>O((dL + \ln n) \ln n)</math> со средней работой <math>O(n + m + dL \ln n)</math>
 
Средняя время работы параллельного алгоритма на графах со случайными весами на <math>O(n)</math> процессорах составляет <math>O((dL + \ln n) \ln n)</math> со средней работой <math>O(n + m + dL \ln n)</math>
  
=== Описание входных и выходных данных ===
+
=== Входные и выходные данные алгоритма ===
 +
 
 +
'''Входные данные''': взвешенный граф <math>(V, E, W)</math> (<math>n</math> вершин <math>v_i</math> и <math>m</math> рёбер <math>e_j = (v^{(1)}_{j}, v^{(2)}_{j})</math> с весами <math>f_j</math>), вершина-источник <math>u</math>.
 +
 
 +
'''Объём входных данных''': <math>O(m + n)</math>.
 +
 
 +
'''Выходные данные''' (возможные варианты):
 +
# для каждой вершины <math>v</math> исходного графа – последнее ребро <math>e^*_v = (w, v)</math>, лежащее на кратчайшем пути от вершины <math>u</math> к <math>v</math>, или соответствующая вершина <math>w</math>;
 +
# для каждой вершины <math>v</math> исходного графа – суммарный вес <math>f^*(v)</math> кратчайшего пути от от вершины <math>u</math> к <math>v</math>.
 +
 +
'''Объём выходных данных''': <math>O(n)</math>.
 +
 
 
=== Свойства алгоритма===
 
=== Свойства алгоритма===
== Программная реализация алгоритмов ==
+
 
 +
Предельные случаи алгоритма Δ-шагания:
 +
* при <math>\Delta \to 0</math>: [[алгоритм Дейкстры]];
 +
* при <math>\Delta \to \infty</math>: [[алгоритм Беллмана-Форда]].
 +
 
 +
== Программная реализация алгоритма ==
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
+
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Возможные способы и особенности реализации параллельного алгоритма ===
+
=== Результаты прогонов ===
=== Масштабируемость алгоритма и его реализации ===
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
+
 
 
== Литература ==
 
== Литература ==
  
 
<references />
 
<references />
 +
 +
[[Категория:Начатые статьи]]
 +
 +
[[en:Δ-stepping algorithm]]

Текущая версия на 10:22, 5 июля 2022


1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Алгоритм дельта-шагания[1] (англ. Δ-Stepping) предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм изначально проектировался с целью эффективной параллелизации.

1.2 Математическое описание алгоритма

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

Псевдокод последовательного алгоритма:

Входные данные:
  граф с вершинами V, рёбрами E с весами W;
  вершина-источник u;
  параметр Δ > 0.
Выходные данные: расстояния d(v) до каждой вершины vV от вершины u.

procedure DeltaStepping(V, E, W, u, Δ):
     LightEdges := { e ∈ E | W(e) ≤ Δ }
     HeavyEdges := { e ∈ E | W(e) > Δ }
     for each vV do d(v) := ∞
     Relax(u, 0)
     while any({ Buckets(i) ≠ ∅ }):
         Bucket := first({ Buckets(i) ≠ ∅ })
         Deleted := ∅
         while Bucket ≠ ∅:
             Requests := FindRequests(Bucket, LightEdges)
             Deleted := DeletedBucket
             Bucket := ∅
             RelaxAll(Requests)
         RelaxAll(FindRequests(Deleted, HeavyEdges))
         
procedure Relax(v, x):
    if x < d(v):
        OldBucket := B(⌊d(v) / Δ⌋)
        NewBucket := B(⌊x / Δ⌋)
        OldBucket := OldBucket \ {v}
        NewBucket := NewBucket ∪ {v}
        d(v) := x
        
procedure RelaxAll(R):
    for each (v, x) ∈ R do Relax(v, x)
    
function FindRequests(V', E'):
    return { (w, d(w) + W(v, w)) | vV' and (v, w) ∈ E'}

1.6 Последовательная сложность алгоритма

Средняя последовательная сложность алгоритма на графах со случайными весами [math]O(n + m + dL)[/math], где [math]L[/math] – максимальный суммарный вес кратчайшего пути, [math]d[/math] – максимальная длина кратчайшего пути.

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

Средняя время работы параллельного алгоритма на графах со случайными весами на [math]O(n)[/math] процессорах составляет [math]O((dL + \ln n) \ln n)[/math] со средней работой [math]O(n + m + dL \ln n)[/math]

1.9 Входные и выходные данные алгоритма

Входные данные: взвешенный граф [math](V, E, W)[/math] ([math]n[/math] вершин [math]v_i[/math] и [math]m[/math] рёбер [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math] с весами [math]f_j[/math]), вершина-источник [math]u[/math].

Объём входных данных: [math]O(m + n)[/math].

Выходные данные (возможные варианты):

  1. для каждой вершины [math]v[/math] исходного графа – последнее ребро [math]e^*_v = (w, v)[/math], лежащее на кратчайшем пути от вершины [math]u[/math] к [math]v[/math], или соответствующая вершина [math]w[/math];
  2. для каждой вершины [math]v[/math] исходного графа – суммарный вес [math]f^*(v)[/math] кратчайшего пути от от вершины [math]u[/math] к [math]v[/math].

Объём выходных данных: [math]O(n)[/math].

1.10 Свойства алгоритма

Предельные случаи алгоритма Δ-шагания:

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Возможные способы и особенности параллельной реализации алгоритма

2.3 Результаты прогонов

2.4 Выводы для классов архитектур

3 Литература

  1. Meyer, U, and P Sanders. “Δ-Stepping: a Parallelizable Shortest Path Algorithm.” Journal of Algorithms 49, no. 1 (October 2003): 114–52. doi:10.1016/S0196-6774(03)00076-2.