Аноним

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

Материал из WEGA

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

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

1018 байт добавлено ,  7 декабря 2024
→‎Литература
 
(не показано 14 промежуточных версий 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.
Строка 77: Строка 77:




Санковски также показал, как получить еще более быстрое время обновления O(n1.495) за счет увеличения времени выполнения запросов <math>O(n^{1,495}) \;</math>:
Санковски также показал, как получить еще более быстрое время обновления <math>O(n^{1,495}) \;</math> за счет увеличения времени выполнения запросов <math>O(n^{1,495}) \;</math>:




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




Строка 86: Строка 86:




Теорема 5 (Родитти и Цвик 2002 [10]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами. Существует детерминированный алгоритм для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции вставки и удаления за амортизированное время O(mpn), а запросы – за время O(pn) в наихудшем случае.
'''Теорема 5 (Родитти и Цвик 2002 [10]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами. Существует детерминированный алгоритм для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции вставки и удаления за амортизированное время <math>O(m \sqrt{n})</math>, а запросы – за время <math>O(\sqrt{n})</math> в наихудшем случае.'''




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




Заметим, что результаты теорем 5 и 6 являются субквадратичными для m = o(n1,5) и m = o(n2), соответственно. Более того, они не основываются на быстром перемножении матриц, которое является теоретически эффективным, но непрактичным.
Заметим, что результаты теорем 5 и 6 являются субквадратичными для <math>m = o(n^{1,5}) \;</math> и <math>m = o(n^2) \;</math>, соответственно. Более того, они не основываются на быстром перемножении матриц, которое является теоретически эффективным, но непрактичным.




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


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




Теорема 7 (Родитти и Цвик 2004 [12]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами с единичными весами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время O(t + " °g") в наихудшем случае, а операции вставки и удаления – за время
'''Теорема 7 (Родитти и Цвик 2004 [12]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами с единичными весами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время <math>O(t + \frac{n \; log \; n}{k})</math> в наихудшем случае, а операции вставки и удаления – за амортизированное время <math>O(\frac{m \; n^2 log \; n}{t^2} + km + \frac{m \; n \; log \; n}{k})</math>'''




Положив k = (nlogn)1/2 и (nlogn)1/2 < t < n3/4 (log n)1/4 в теореме 7, можно получить амортизированное время обновления O(mn 22l°gn) и время выполнения запросов в наихудшем случае O(t). Самое быстрое время обновления, O(mn), можно получить, если выбрать t = n3/4(log n)1/4.
Положив <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 вершинами и единичными весами ребер. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время O(n1,288), а операции вставки и удаления – за время O(n1,932).
'''Теорема 8 (Санковски [14], 2005). Пусть дан ориентированный граф общего вида с n вершинами и единичными весами ребер. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время <math>O(n^{1,288}) \;</math>, а операции вставки и удаления – за время <math>O(n^{1,932}) \;</math>.'''




Тип графа Тип алгоритма Время обновления Время выполнения запроса Источник
{| class="wikitable" style="text-align:center"
Граф общего вида Монте-Карло 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]
! Источник
|-
| Граф общего вида
| Монте-Карло
| <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]
|}


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


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


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


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


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


== Литература ==
== Литература ==
Строка 172: Строка 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/Служебная:Сравнение_версий/13071...15770