Аноним

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

Материал из WEGA

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

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

12 616 байт добавлено ,  7 декабрь
→‎Литература
 
(не показано 16 промежуточных версий 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.
Строка 65: Строка 65:




'''Следствие 1 (Деметреску и Итальяно [4, 5], 2000). Пусть дан ориентированный ациклический граф с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий запросы за время <math>O(n^{0,575}) \;</math>:, а операции вставки и удаления – за время <math>O(n^{1,575}) \;</math>.'''
'''Следствие 1 (Деметреску и Итальяно [4, 5], 2000). Пусть дан ориентированный ациклический граф с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий запросы за время <math>O(n^{0,575}) \;</math>, а операции вставки и удаления – за время <math>O(n^{1,575}) \;</math>.'''




Строка 74: Строка 74:




'''Следствие 2 (Санковски [13], 2004). Пусть дан ориентированный граф общего вида с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий запросы за время <math>O(n^{0,575}) \;</math>:, а операции вставки и удаления – за время <math>O(n^{1,575}) \;</math>.'''
'''Следствие 2 (Санковски [13], 2004). Пусть дан ориентированный граф общего вида с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий запросы за время <math>O(n^{0,575}) \;</math>, а операции вставки и удаления – за время <math>O(n^{1,575}) \;</math>.'''
 
 
Санковски также показал, как получить еще более быстрое время обновления <math>O(n^{1,495}) \;</math> за счет увеличения времени выполнения запросов <math>O(n^{1,495}) \;</math>:
 
 
'''Теорема 4 (Санковски [13], 2004). Пусть дан ориентированный граф общего вида с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий запросы и операции вставки и удаления за время <math>O(n^{1,495}) \;</math>.'''
 
 
Родитти и Цвик представили алгоритмы с лучшими границами для разреженных графов:
 
 
'''Теорема 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) в наихудшем случае.'''
 
 
Заметим, что результаты теорем 5 и 6 являются субквадратичными для <math>m = o(n^{1,5}) \;</math> и <math>m = o(n^2) \;</math>, соответственно. Более того, они не основываются на быстром перемножении матриц, которое является теоретически эффективным, но непрактичным.
 
 
'''Динамический алгоритм нахождения кратчайших путей'''
 
Первый эффективный компромиссный алгоритм для динамического поиска кратчайших путей предложили Родитти и Цвик для специального случая разреженных графов с единичными весами ребер [12]:
 
 
'''Теорема 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>'''
 
 
Положив <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>.
 
 
Позднее Санковски разработал первый алгоритм с временем выполнения ниже квадратичного для плотных графов, основанный на быстром умножении матриц [14]:
 
 
'''Теорема 8 (Санковски [14], 2005). Пусть дан ориентированный граф общего вида с n вершинами и единичными весами ребер. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время <math>O(n^{1,288}) \;</math>, а операции вставки и удаления – за время <math>O(n^{1,932}) \;</math>.'''
 
 
{| 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]
|}
 
 
Таблица 1. Полностью динамические алгоритмы транзитивного замыкания с неявным представлением решения
 
== Применение ==
Задача о транзитивном замыкании особенно актуальна в сфере управления базами данных для поддержки транзитивных запросов на динамических графах отношений [16]. Она возникает также во множестве других областей – таких как компиляторы, интерактивные системы верификации, сбор мусора и промышленная робототехника.
 
 
В число сценариев применения динамических алгоритмов нахождения кратчайших путей входят оптимизация сетей [1], форматирование документов [8], маршрутизация в системах коммуникации, робототехника, инкрементная компиляция, системы управления информацией о дорожном движении [15] и анализ потоков данных. Полный обзор реальных областей применения динамических алгоритмов нахождения кратчайших путей приведен в [9].
 
== Открытые вопросы ==
Остается нерешенным фундаментальный вопрос: можно ли решить полностью динамическую задачу о нахождении кратчайших путей между всеми парами из определения 3 за время на операцию ниже квадратичного в случае графов с вещественными весами ребер.
 
== См. также ==
* [[Алгоритм поиска кратчайших путей в разреженных графах]]
* [[Алгоритм поиска кратчайших путей при помощи матричного произведения]]
* [[Декрементный алгоритм нахождения кратчайших путей между всеми парами]]
* [[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]]
* [[Полностью динамический алгоритм транзитивного замыкания]]
* [[Полностью динамический алгоритм достижимости с единственным источником]]
 
== Литература ==
1. Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs (1993)
 
2. Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 251-280 (1990)
 
3. Demetrescu, C., Finocchi, I., Italiano, G.: Dynamic Graphs. In: Mehta, D., Sahni, S. (eds.) Handbook on Data Structures and Applications (CRC Press Series, in Computer and Information Science), chap. 36. CRC Press, Boca Raton (2005)
 
4. Demetrescu, C., Italiano, G.: Fully dynamic transitive closure: Breaking through the O(n2) barrier. In: Proc. of the 41st IEEE Annual Symposium on  Foundations of Computer Science (FOCS'00), Redondo Beach (2000), pp. 381-389
 
5. Demetrescu, C., Italiano, G.: Trade-offs for fully dynamic reachability on dags: Breaking through the O(n2) barrier. J. ACM 52, 147-156(2005)
 
6. Henzinger, M., King, V.: Fully dynamic biconnectivity and transitive closure. In: Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS'95), Milwaukee (1995), pp. 664-672
 
7. Huang, X., Pan, V.: Fast rectangular matrix multiplication and applications. J. Complex. 14, 257-299(1998)
 
8. Knuth, D., Plass, M.: Breaking paragraphs into lines. Software-practice Exp. 11,1119-1184 (1981)
 
9. Ramalingam, G.: Bounded incremental computation. In: Lecture Notes in Computer Science, vol. 1089. Springer, New York (1996)
 
10. Roditty, L., Zwick, U.: Improved dynamic reachability algorithms for directed graphs. In: Proceedings of 43th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Vancouver (2002), pp. 679-688
 
11. Roditty, L., Zwick, U.: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), Chicago (2004), pp. 184-191
 
12. Roditty, L., Zwick, U.: On Dynamic Shortest Paths Problems. In: Proceedings of the 12th Annual European Symposium on Algorithms (ESA), Bergen (2004), pp. 580-591
 
13. Sankowski, P.: Dynamic transitive closure via dynamic matrix inverse. In: FOCS '04: Proceedings of the45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), pp. 509-517. IEEE Computer Society, Washington, DC (2004)
 
14. Sankowski, P.: Subquadratic algorithm for dynamic shortest distances. In: 11th Annual International Conference on Computing and Combinatorics (COCOON'05), Kunming (2005), pp. 461-470
 
15. Schulz, F., Wagner, D., Weihe, K.: Dijkstra's algorithm on-line: an empirical case study from public railroad transport. In: Proc. 3rd Workshop on Algorithm Engineering (WAE'99), London (1999), pp. 110-123
 
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/Служебная:Сравнение_версий/13046...15770