Компромиссы при решении динамических графовых задач: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 75: | Строка 75: | ||
'''Следствие 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>.''' | ||
Санковски также показал, как получить еще более быстрое время обновления O(n1.495) за счет увеличения времени выполнения запросов <math>O(n^{1,495}) \;</math>: | |||
Теорема 4 (Санковски [13], 2004). Пусть дан ориентированный граф общего вида с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий запросы и операции вставки и удаления за время O(n1,495). | |||
Родитти и Цвик представили алгоритмы с лучшими границами для разреженных графов: | |||
Теорема 5 (Родитти и Цвик 2002 [10]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами. Существует детерминированный алгоритм для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции вставки и удаления за амортизированное время O(mpn), а запросы – за время O(pn) в наихудшем случае. | |||
Теорема 6 (Родитти и Цвик 2004 [11]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами. Существует детерминированный алгоритм для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции вставки и удаления за амортизированное время O(m+ n log n), а запросы – за время O(n) в наихудшем случае. | |||
Заметим, что результаты теорем 5 и 6 являются субквадратичными для m = o(n1,5) и m = o(n2), соответственно. Более того, они не основываются на быстром перемножении матриц, которое является теоретически эффективным, но непрактичным. | |||
'''Динамический алгоритм нахождения кратчайших путей''' | |||
Первыми эффективный компромиссный алгоритм для динамического поиска кратчайших путей предложили Родитти и Цвик для специального случая разреженных графов с единичными весами ребер [12]: | |||
Теорема 7 (Родитти и Цвик 2004 [12]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами с единичными весами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время O(t + " °g") в наихудшем случае, а операции вставки и удаления – за время | |||
Положив 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. | |||
Позднее Санковски разработал первый алгоритм с временем выполнения ниже квадратичного для плотных графов, основанный на быстром умножении матриц [14]: | |||
Теорема 8 (Санковски [14], 2005). Пусть дан ориентированный граф общего вида с n вершинами и единичными весами ребер. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи нахождения кратчайших путей между всеми парами, поддерживающий запросы о расстоянии за время O(n1,288), а операции вставки и удаления – за время O(n1,932). | |||
Тип графа Тип алгоритма Время обновления Время выполнения запроса Источник | |||
Граф общего вида Монте-Карло 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. Полностью динамический алгоритм транзитивного замыкания с неявным представлением решения | |||
== Применение == | |||
Задача о транзитивном замыкании особенно актуальна в сфере управления базами данных для поддержки транзитивных запросов на динамических графах отношений [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 | |||