Полностью динамический алгоритм достижимости с единственным источником: различия между версиями
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Полностью динамическое транзитивное замыкание с единстве…») |
Irina (обсуждение | вклад) |
||
| (не показано 8 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Полностью | [[Полностью динамический алгоритм транзитивного замыкания]] с единственным источником | ||
== Постановка задачи == | == Постановка задачи == | ||
Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм является полностью динамическим, если он поддерживает как вставку ребер, так и удаление, и частично динамическим, если поддерживает либо вставку, либо удаление ребер. | Динамический алгоритм на графе поддерживает заданное свойство <math>\mathcal{P}</math> графа, подверженного динамическим изменениям – таким как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен быстро обрабатывать запросы о свойстве <math>\mathcal{P}</math>, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм является ''полностью динамическим'', если он поддерживает как вставку ребер, так и удаление, и ''частично динамическим'', если поддерживает либо вставку, либо удаление ребер. | ||
Пусть дан граф, имеющий n вершин и m ребер. Задача поиска транзитивного замыкания (или задача достижимости) заключается в построении булевой матрицы M размера n x n, такой, что M[x, y] = 1 в том и только том случае, если существует ориентированный путь в графе из вершины x в вершину y. Полностью динамическую версию этой задачи можно определить следующим образом. | Пусть дан граф, имеющий n вершин и m ребер. Задача поиска [[Транзитивное_замыкание_орграфа|транзитивного замыкания]] (или задача [[Достижимость|достижимости]]) заключается в построении булевой матрицы M размера n x n, такой, что M[x, y] = 1 в том и только том случае, если существует ориентированный путь в графе из вершины x в вершину y. Полностью динамическую версию этой задачи можно определить следующим образом. | ||
Определение 1 (Полностью динамическая задача достижимости). Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке: | '''Определение 1 (Полностью динамическая задача достижимости'''). Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке: | ||
• insert(u,v): вставка дуги (u, v) в граф; | • ''insert(u, v)'': вставка дуги (u, v) в граф; | ||
• delete(u,v): удаление дуги (u, v) из графа; | • ''delete(u, v)'': удаление дуги (u, v) из графа; | ||
• reachable(x,y): возвращает true, если существует ориентированный путь между вершинами x и y, и false в противном случае. | • ''reachable(x, y)'': возвращает ''true'', если существует ориентированный путь между вершинами x и y, и ''false'' в противном случае. | ||
Далее будет исследована версия полностью динамической задачи достижимости для случая с единственным источником, в которой нас интересуют только запросы с фиксированной вершиной-источником s. Эта версия определяется следующим образом. | Далее будет исследована версия полностью динамической задачи достижимости для случая ''с единственным источником'', в которой нас интересуют только запросы с фиксированной вершиной-источником s. Эта версия определяется следующим образом. | ||
Определение 2 (Полностью динамическая задача достижимости с единственным источником). Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке: | '''Определение 2 (Полностью динамическая задача достижимости с единственным источником)'''. Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке: | ||
• insert(u,v): вставка дуги (u, v) в граф; | • ''insert(u, v)'': вставка дуги (u, v) в граф; | ||
• delete(u,v): удаление дуги (u, v) из графа; | • ''delete(u, v)'': удаление дуги (u, v) из графа; | ||
• reachable( | • ''reachable(y)'': возвращает ''true'', если существует ориентированный путь между вершиной-источником s и вершиной y, и ''false'' в противном случае. | ||
''' | '''Подходы к решению''' | ||
Простое решение этой задачи заключается в хранении явной информации о достижимости любой вершины из источника и обновлении этой информации при помощи любого алгоритма обхода графа из вершины s после каждой операции вставки или удаления. Такой подход требует O(m + n) времени на операцию, а последующие запросы о достижимости могут быть выполнены за константное время. | |||
Еще одним простым решением является ответ на запросы путем поточечного вычисления достижимости, без необходимости сохранения явной информации о достижимости после каждой вставки или удаления. Это можно выполнить за время O(m + n) при помощи любого алгоритма обхода графа. Подобный подход позволяет давать ответы на запросы за время O(m + n) и выполнять обновления за константное время. Заметим, что при использовании обоих подходов время выполнения самой медленной операции составляет O(m + n), что для плотных графов доходит до <math>O(n^2) \;</math>. | |||
Первым улучшением по сравнению с двумя базовыми решениями стал алгоритм Деметреску и Итальяно, которые показали, как поддерживать операции обновления за время O( | |||
Первым улучшением по сравнению с двумя базовыми решениями стал алгоритм Деметреску и Итальяно, которые показали, как поддерживать операции обновления за время <math>O(n^{1,575}) \;</math>, а запросы о достижимости – за время O(1) [1] в ориентированном ациклическом графе. Их результат основывается на простой редукции решения для задачи с единственным источником до [[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами|задачи для всех пар]]. Используя результат Санковски [2], можно расширить вышеприведенные границы для общего случая ориентированных графов. | |||
== Основные результаты == | == Основные результаты == | ||
Простая редукция, предложенная в [1], позволяет сохранять актуальность информации о достижимости из единственного источника, за время ниже квадратичного на одну операцию в ориентированном графе, при выполнении последовательности операций вставки и удаления ребра в различном порядке. Упомянутые границы были впервые приведены для случая ориентированных ациклических графов, однако их можно распространить на | Простая редукция, предложенная в [1], позволяет сохранять актуальность информации о достижимости из единственного источника, за время ниже квадратичного на одну операцию в ориентированном графе, при выполнении последовательности операций вставки и удаления ребра в различном порядке. Упомянутые границы были впервые приведены для случая ориентированных ациклических графов, однако их можно распространить на ориентированные графы общего вида при помощи следующей теоремы [2]: | ||
Теорема 1. Пусть дан ориентированный граф общего вида с n вершинами. Существует структура данных для решения полностью динамической задачи достижимости, поддерживающая операции вставки и удаления за время O( | '''Теорема 1. Пусть дан ориентированный граф общего вида с n вершинами. Существует структура данных для решения полностью динамической задачи достижимости, поддерживающая операции вставки и удаления за время <math>O(n^{1,575}) \;</math>, а запросы о достижимости – за время <math>O(n^{0,575}) \;</math>. Алгоритм является рандомизированным с односторонней ошибкой.''' | ||
В [ ] была предложена идея поддержки информации о достижимости из вершины-источника s до всех остальных вершин явным образом | В [1] была предложена идея поддержки информации о достижимости из вершины-источника s до всех остальных вершин явным образом за счет поддержки булева массива R размера n, такого, что R[y] = 1 в том и только том случае, если существует ориентированный путь из s в y. Также поддерживается экземпляр D структуры данных для полностью динамической задачи достижимости из Теоремы 1. После каждой операции вставки или удаления можно обновить структуру D за время <math>O(n^{1,575}) \;</math> и затем перестроить R за время <math>O(n \cdot n^{0,575}) = O(n^{1,575}) \;</math>, положив R[y] <— D.''reachable (s, y)'' для каждой вершины y. Это позволяет получить следующие границы для полностью динамической задачи достижимости с единственным источником. | ||
Теорема 2. Пусть дан ориентированный граф общего вида с n вершинами. Существует структура данных для решения полностью динамической задачи достижимости с единственным источником, поддерживающая операции вставки и удаления за время O( | '''Теорема 2. Пусть дан ориентированный граф общего вида с n вершинами. Существует структура данных для решения полностью динамической задачи достижимости с единственным источником, поддерживающая операции вставки и удаления за время <math>O(n^{1,575}) \;</math>, а запросы о достижимости – за время O(1).''' | ||
== Применение == | == Применение == | ||
Задача достижимости в графе особенно актуальна в сфере управления базами данных для поддержки транзитивных запросов на динамических графах отношений [ ]. Она возникает также во множестве других областей – таких как компиляторы, интерактивные системы верификации, сбор мусора и промышленная робототехника. | Задача достижимости в графе особенно актуальна в сфере управления базами данных для поддержки транзитивных запросов на динамических графах отношений [3]. Она возникает также во множестве других областей – таких как компиляторы, интерактивные системы верификации, сбор мусора и промышленная робототехника. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Текущая версия от 11:32, 19 июня 2018
Ключевые слова и синонимы
Полностью динамический алгоритм транзитивного замыкания с единственным источником
Постановка задачи
Динамический алгоритм на графе поддерживает заданное свойство [math]\displaystyle{ \mathcal{P} }[/math] графа, подверженного динамическим изменениям – таким как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен быстро обрабатывать запросы о свойстве [math]\displaystyle{ \mathcal{P} }[/math], а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм является полностью динамическим, если он поддерживает как вставку ребер, так и удаление, и частично динамическим, если поддерживает либо вставку, либо удаление ребер.
Пусть дан граф, имеющий n вершин и m ребер. Задача поиска транзитивного замыкания (или задача достижимости) заключается в построении булевой матрицы M размера n x n, такой, что M[x, y] = 1 в том и только том случае, если существует ориентированный путь в графе из вершины x в вершину y. Полностью динамическую версию этой задачи можно определить следующим образом.
Определение 1 (Полностью динамическая задача достижимости). Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке:
• insert(u, v): вставка дуги (u, v) в граф;
• delete(u, v): удаление дуги (u, v) из графа;
• reachable(x, y): возвращает true, если существует ориентированный путь между вершинами x и y, и false в противном случае.
Далее будет исследована версия полностью динамической задачи достижимости для случая с единственным источником, в которой нас интересуют только запросы с фиксированной вершиной-источником s. Эта версия определяется следующим образом.
Определение 2 (Полностью динамическая задача достижимости с единственным источником). Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке:
• insert(u, v): вставка дуги (u, v) в граф;
• delete(u, v): удаление дуги (u, v) из графа;
• reachable(y): возвращает true, если существует ориентированный путь между вершиной-источником s и вершиной y, и false в противном случае.
Подходы к решению
Простое решение этой задачи заключается в хранении явной информации о достижимости любой вершины из источника и обновлении этой информации при помощи любого алгоритма обхода графа из вершины s после каждой операции вставки или удаления. Такой подход требует O(m + n) времени на операцию, а последующие запросы о достижимости могут быть выполнены за константное время.
Еще одним простым решением является ответ на запросы путем поточечного вычисления достижимости, без необходимости сохранения явной информации о достижимости после каждой вставки или удаления. Это можно выполнить за время O(m + n) при помощи любого алгоритма обхода графа. Подобный подход позволяет давать ответы на запросы за время O(m + n) и выполнять обновления за константное время. Заметим, что при использовании обоих подходов время выполнения самой медленной операции составляет O(m + n), что для плотных графов доходит до [math]\displaystyle{ O(n^2) \; }[/math].
Первым улучшением по сравнению с двумя базовыми решениями стал алгоритм Деметреску и Итальяно, которые показали, как поддерживать операции обновления за время [math]\displaystyle{ O(n^{1,575}) \; }[/math], а запросы о достижимости – за время O(1) [1] в ориентированном ациклическом графе. Их результат основывается на простой редукции решения для задачи с единственным источником до задачи для всех пар. Используя результат Санковски [2], можно расширить вышеприведенные границы для общего случая ориентированных графов.
Основные результаты
Простая редукция, предложенная в [1], позволяет сохранять актуальность информации о достижимости из единственного источника, за время ниже квадратичного на одну операцию в ориентированном графе, при выполнении последовательности операций вставки и удаления ребра в различном порядке. Упомянутые границы были впервые приведены для случая ориентированных ациклических графов, однако их можно распространить на ориентированные графы общего вида при помощи следующей теоремы [2]:
Теорема 1. Пусть дан ориентированный граф общего вида с n вершинами. Существует структура данных для решения полностью динамической задачи достижимости, поддерживающая операции вставки и удаления за время [math]\displaystyle{ O(n^{1,575}) \; }[/math], а запросы о достижимости – за время [math]\displaystyle{ O(n^{0,575}) \; }[/math]. Алгоритм является рандомизированным с односторонней ошибкой.
В [1] была предложена идея поддержки информации о достижимости из вершины-источника s до всех остальных вершин явным образом за счет поддержки булева массива R размера n, такого, что R[y] = 1 в том и только том случае, если существует ориентированный путь из s в y. Также поддерживается экземпляр D структуры данных для полностью динамической задачи достижимости из Теоремы 1. После каждой операции вставки или удаления можно обновить структуру D за время [math]\displaystyle{ O(n^{1,575}) \; }[/math] и затем перестроить R за время [math]\displaystyle{ O(n \cdot n^{0,575}) = O(n^{1,575}) \; }[/math], положив R[y] <— D.reachable (s, y) для каждой вершины y. Это позволяет получить следующие границы для полностью динамической задачи достижимости с единственным источником.
Теорема 2. Пусть дан ориентированный граф общего вида с n вершинами. Существует структура данных для решения полностью динамической задачи достижимости с единственным источником, поддерживающая операции вставки и удаления за время [math]\displaystyle{ O(n^{1,575}) \; }[/math], а запросы о достижимости – за время O(1).
Применение
Задача достижимости в графе особенно актуальна в сфере управления базами данных для поддержки транзитивных запросов на динамических графах отношений [3]. Она возникает также во множестве других областей – таких как компиляторы, интерактивные системы верификации, сбор мусора и промышленная робототехника.
Открытые вопросы
Остается открытым важный вопрос о том, можно ли расширить вышеописанный результат для решения полностью динамической задачи нахождения кратчайших путей с единственным источником с временем выполнения одной операции ниже квадратичного.
См. также
Литература
1. Demetrescu, C., Italiano, G.: Trade-offs for fully dynamic reachability on dags: Breaking through the O(n2) barrier. J. Assoc. Com-put. Machin. (JACM) 52,147-156 (2005)
2. Sankowski, P.: Dynamic transitive closure via dynamic matrix inverse. In: FOCS '04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), pp. 509-517. IEEE Computer Society, Washington DC (2004)
3. 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