1294
правки
Компромиссы при решении динамических графовых задач: различия между версиями
Перейти к навигации
Перейти к поиску
Компромиссы при решении динамических графовых задач (посмотреть исходный код)
Версия от 11:25, 7 декабря 2024
, 7 декабрь→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показано 16 промежуточных версий 1 участника) | |||
| Строка 8: | Строка 8: | ||
'''Определение 1 (Динамический алгоритм на графе)'''. Пусть дан граф и свойство графа P. Динамический алгоритм на графе представляет собой структуру данных, поддерживающую выполнение последовательности следующих операций в различном порядке: | '''Определение 1 (Динамический алгоритм на графе)'''. Пусть дан граф и свойство графа P. Динамический алгоритм на графе представляет собой структуру данных, поддерживающую выполнение последовательности следующих операций в различном порядке: | ||
insert(u, v): вставка | insert(u, v): вставка ребра (u, v) в граф; | ||
delete(u, v): удаление | delete(u, v): удаление ребра (u, v) из графа; | ||
query(..): ответ на запрос о выполнении свойства P графа. | query(..): ответ на запрос о выполнении свойства P графа. | ||
| Строка 26: | Строка 26: | ||
'''Определение 2 (Полностью динамическая задача о транзитивном замыкании)'''. Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке: | '''Определение 2 (Полностью динамическая задача о транзитивном замыкании)'''. Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке: | ||
insert(u, v): вставка | insert(u, v): вставка ребра (u, v) в граф; | ||
delete(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): вставка | insert(u, v, w): вставка ребра (u, v) с весом w в граф; | ||
delete(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> | '''Следствие 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 | |||
[[Категория: Совместное определение связанных терминов]] | |||