Аноним

Компромиссы при решении динамических графовых задач: различия между версиями

Материал из WEGA

Компромиссы при решении динамических графовых задач (посмотреть исходный код)

Версия от 04:25, 7 декабря 2024

386 байт добавлено ,  7 декабря 2024
→‎Литература
 
(не показано 10 промежуточных версий 1 участника)
Строка 8: Строка 8:
'''Определение 1 (Динамический алгоритм на графе)'''. Пусть дан граф и свойство графа P. Динамический алгоритм на графе представляет собой структуру данных, поддерживающую выполнение последовательности следующих операций в различном порядке:
'''Определение 1 (Динамический алгоритм на графе)'''. Пусть дан граф и свойство графа P. Динамический алгоритм на графе представляет собой структуру данных, поддерживающую выполнение последовательности следующих операций в различном порядке:


insert(u, v): вставка дуги (u, v) в граф;
insert(u, v): вставка ребра (u, v) в граф;


delete(u, v): удаление дуги (u, v) из графа;
delete(u, v): удаление ребра (u, v) из графа;


query(..):      ответ на запрос о выполнении свойства P графа.
query(..):      ответ на запрос о выполнении свойства P графа.
Строка 26: Строка 26:
'''Определение 2 (Полностью динамическая задача о транзитивном замыкании)'''. Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке:
'''Определение 2 (Полностью динамическая задача о транзитивном замыкании)'''. Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке:


insert(u, v): вставка дуги (u, v) в граф;
insert(u, v): вставка ребра (u, v) в граф;


delete(u, v):  удаление дуги (u, v) из графа;
delete(u, v):  удаление ребра (u, v) из графа;


query(x, y): возвращает ''true'', если существует ориентированный путь между вершинами x и y, и ''false'' в противном случае.
query(x, y): возвращает ''true'', если существует ориентированный путь между вершинами x и y, и ''false'' в противном случае.
Строка 35: Строка 35:
'''Определение 3 (Полностью динамическая задача нахождения кратчайших путей между всеми парами)'''. Задача заключается в поддержке взвешенного ориентированного графа и выполнении последовательности следующих операций в различном порядке:
'''Определение 3 (Полностью динамическая задача нахождения кратчайших путей между всеми парами)'''. Задача заключается в поддержке взвешенного ориентированного графа и выполнении последовательности следующих операций в различном порядке:


insert(u, v, w): вставка дуги (u, v) с весом w в граф;
insert(u, v, w): вставка ребра (u, v) с весом w в граф;


delete(u, v): удаление дуги (u, v) из графа;
delete(u, v): удаление ребра (u, v) из графа;


query(x, y): возвращает расстояние между x и y в графе либо значение <math>+ \infty</math> в случае, если не существует ориентированного пути из x в y.
query(x, y): возвращает расстояние между x и y в графе либо значение <math>+ \infty</math> в случае, если не существует ориентированного пути из x в y.
Строка 89: Строка 89:




'''Теорема 6 (Родитти и Цвик 2004 [11]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами. Существует детерминированный алгоритм для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции вставки и удаления за амортизированное время O(m+ n log n), а запросы – за время O(n) в наихудшем случае.'''
'''Теорема 6 (Родитти и Цвик 2004 [11]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами. Существует детерминированный алгоритм для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции вставки и удаления за амортизированное время O(m + n log n), а запросы – за время O(n) в наихудшем случае.'''




Строка 97: Строка 97:
'''Динамический алгоритм нахождения кратчайших путей'''
'''Динамический алгоритм нахождения кратчайших путей'''


Первыми эффективный компромиссный алгоритм для динамического поиска кратчайших путей предложили Родитти и Цвик для специального случая разреженных графов с единичными весами ребер [12]:
Первый эффективный компромиссный алгоритм для динамического поиска кратчайших путей предложили Родитти и Цвик для специального случая разреженных графов с единичными весами ребер [12]:




Строка 103: Строка 103:




Положив <math>k = (n \; log \; n)^{1/2}</math> и <math>(n \; log \; n)^{1/2} \le t \le n^{3/4} \; (log \; n)^{1/4}</math> в теореме 7, можно получить амортизированное время обновления <math>O(\frac{m \; n^2 \; log \; n}{t^2})</math> и время выполнения запросов в наихудшем случае <math>O(t) \;</math>. Самое быстрое время обновления, <math>O(m \sqrt{n \; log n})</math>, можно получить, если выбрать <math>t = n^{3/4}(log \; n)^{1/4}</math>.
Положив <math>k = (n \; log \; n)^{1/2}</math> и <math>(n \; log \; n)^{1/2} \le t \le n^{3/4} \; (log \; n)^{1/4}</math> в теореме 7, можно получить амортизированное время обновления <math>O(\frac{m \; n^2 \; log \; n}{t^2})</math> и время выполнения запросов в наихудшем случае <math>O(t) \;</math>. Самое быстрое время обновления, <math>O(m \sqrt{n \; log \; n})</math>, можно получить, если выбрать <math>t = n^{3/4}(log \; n)^{1/4}</math>.




Строка 109: Строка 109:




Теорема 8 (Санковски [14], 2005). Пусть дан ориентированный граф общего вида с n вершинами и единичными весами ребер. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время <math>O(n^{1,288}) \;</math>, а операции вставки и удаления – за время <math>O(n^{1,932}) \;</math>.
'''Теорема 8 (Санковски [14], 2005). Пусть дан ориентированный граф общего вида с n вершинами и единичными весами ребер. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время <math>O(n^{1,288}) \;</math>, а операции вставки и удаления – за время <math>O(n^{1,932}) \;</math>.'''




{| class="wikitable"
{| class="wikitable" style="text-align:center"
|-
|-
! Тип графа
! Тип графа
! Тип алгоритма
! Тип алгоритма
! Время обновления
! Время обновления
! Время выполнения запроса
! Время запроса
! Источник
! Источник
|-
|-
|  
| Граф общего вида
|  
| Монте-Карло
|  
| <math>O(m \sqrt{n} \; log^2 n)</math> аморт.
|  
| <math>O(n / log \; n)</math>
|  
| Хензингер, Кинг [6]
|-
|-
|  
|width="140pt"| Ориентированный ациклический граф
|  
| Монте-Карло
|  
| <math>O(n^{1,575}) \;</math>
|  
| <math>O(n^{0,575}) \;</math>
|  
| Деметреску, Итальяно [4]
|-
|-
|  
| Граф общего вида
|  
| Монте-Карло
|  
| <math>O(n^{1,575}) \;</math>
|  
| <math>O(n^{0,575}) \;</math>
|  
| Санковски [13]
|-
|-
|  
| Граф общего вида
|  
| Монте-Карло
|  
| <math>O(n^{1,495}) \;</math>
|  
| <math>O(n^{1,495}) \;</math>
|  
| Санковски [13]
|-
|-
|  
| Граф общего вида
|  
| Детерминированный
|  
| <math>O(m \sqrt{n})</math> аморт.
|  
| <math>O(\sqrt{n)}</math>
|  
| Родитти, Цвик [10]
|-
|-
|  
| Граф общего вида
|  
| Детерминированный
|  
| <math>O(m + n \; log \; n)</math> аморт.
|  
| O(n)
|  
| Родитти, Цвик [11]
|}
|}


Граф общего вида Монте-Карло O(mpn log2 n) аморт. O(n/logn) Хензингер и Кинг [6]
Ориентированный ациклический граф Монте-Карло O(n1,575) O(n0,575) Деметреску, Итальяно [4]
Граф общего вида Монте-Карло O(n1,575) O(n0,575) Санковски [13]
Граф общего вида Монте-Карло O(n1,495) O(n1,495) Санковски [13]
Граф общего вида Детерминированный O(mn) аморт. O(pn) Родитти, Цвик [10]
Граф общего вида Детерминированный O(m + n log n) аморт. O(n) Родитти, Цвик [11]


Таблица 1. Полностью динамический алгоритм транзитивного замыкания с неявным представлением решения
Таблица 1. Полностью динамические алгоритмы транзитивного замыкания с неявным представлением решения


== Применение ==
== Применение ==
Строка 173: Строка 167:


== Открытые вопросы ==
== Открытые вопросы ==
Остается нерешенным фундаментальный вопрос: можно ли решить задачу о нахождении кратчайших путей между всеми парами из определения 3 за время ниже квадратичного на операцию в случае графов с вещественными весами ребер.
Остается нерешенным фундаментальный вопрос: можно ли решить полностью динамическую задачу о нахождении кратчайших путей между всеми парами из определения 3 за время на операцию ниже квадратичного в случае графов с вещественными весами ребер.


== См. также ==
== См. также ==
► Алгоритм поиска кратчайших путей в разреженных графах
* [[Алгоритм поиска кратчайших путей в разреженных графах]]
► Алгоритм поиска кратчайших путей при помощи матричного произведения
* [[Алгоритм поиска кратчайших путей при помощи матричного произведения]]
► Декрементный алгоритм нахождения кратчайших путей между всеми парами
* [[Декрементный алгоритм нахождения кратчайших путей между всеми парами]]
► Полностью динамический алгоритм нахождения кратчайших путей между всеми парами
* [[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]]
► Полностью динамический алгоритм транзитивного замыкания
* [[Полностью динамический алгоритм транзитивного замыкания]]
► Полностью динамический алгоритм достижимости с единственным источником
* [[Полностью динамический алгоритм достижимости с единственным источником]]


== Литература ==
== Литература ==
Строка 215: Строка 209:


16. Yannakakis, M.: Graph-theoretic methods in database theory. In: Proc. 9-th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Nashville (1990). pp. 230-242
16. Yannakakis, M.: Graph-theoretic methods in database theory. In: Proc. 9-th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Nashville (1990). pp. 230-242
[[Категория: Совместное определение связанных терминов]]
Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/13075...15770