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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 6: Строка 6:




Определение 1 (Динамический алгоритм на графе). Пусть дан граф и свойство графа P. Динамический алгоритм на графе представляет собой структуру данных, поддерживающую выполнение последовательности следующих операций в различном порядке:
'''Определение 1 (Динамический алгоритм на графе)'''. Пусть дан граф и свойство графа P. Динамический алгоритм на графе представляет собой структуру данных, поддерживающую выполнение последовательности следующих операций в различном порядке:


insert(u, v): вставка дуги (u, v) в граф;
insert(u, v): вставка дуги (u, v) в граф;
Строка 15: Строка 15:




Алгоритм на графе является полностью динамическим, если он поддерживает как вставку ребер, так и удаление, и частично динамическим, если поддерживает либо вставку, либо удаление ребер; инкрементный алгоритм поддерживает только вставку ребер, декрементный – только удаление. В некоторых работах исследуются варианты этой задачи, допускающие вставку или удаление более чем одного ребра за один раз либо позволяющие изменять веса ребер. В некоторых случаях обновление может заключаться во вставке или удалении вершины вместе со всеми инцидентными ей ребрами. В других исследованиях рассматриваются только определенные классы графов - например, планарные графы или ориентированные ациклические графы.
Алгоритм на графе является ''полностью динамическим'', если он поддерживает как вставку ребер, так и удаление, и ''частично динамическим'', если поддерживает либо вставку, либо удаление ребер; ''инкрементный алгоритм'' поддерживает только вставку ребер, ''декрементный'' – только удаление. В некоторых работах исследуются варианты этой задачи, допускающие вставку или удаление более чем одного ребра за один раз либо позволяющие изменять веса ребер. В некоторых случаях обновление может заключаться во вставке или удалении вершины вместе со всеми инцидентными ей ребрами. В других исследованиях рассматриваются только определенные классы графов - например, планарные графы или ориентированные ациклические графы.




Динамическим алгоритмам на графе посвящено множество работ. В числе графовых задач, для которых разработаны эффективные динамические алгоритмы, можно упомянуть задачи о [[Связность|связности графа]], о минимальном [[Разрез|разрезе]], [[Минимальное остовное дерево|минимальном остовном дереве]], [[Полностью динамическое транзитивное замыкание|транзитивном замыкании]] и [[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами|нахождении кратчайших путей]] (см., например, [3] и ссылки в этой работе). Многие из них выполняют явное обновление свойства P после каждого обновления графа, чтобы отвечать на запросы за оптимальное время. Этот вариант подходит для случаев, когда обновлений мало, а запросов – много. В приложениях со сравнимым числом обновлений и запросов более эффективным подходом будет попытка уменьшить время обновления – возможно, ценой увеличения времени выполнения запроса. Это обычно достигается при помощи ослабления предположения о том, что свойство P следует поддерживать явным образом.
Динамическим алгоритмам на графе посвящено множество работ. В числе графовых задач, для которых разработаны эффективные динамические алгоритмы, можно упомянуть задачи о [[связность|связности графа]], о минимальном [[разрез|разрезе]], [[минимальное остовное дерево|минимальном остовном дереве]], [[полностью динамическое транзитивное замыкание|транзитивном замыкании]] и [[полностью динамический алгоритм нахождения кратчайших путей между всеми парами|нахождении кратчайших путей]] (см., например, [3] и ссылки в этой работе). Многие из них выполняют явное обновление свойства P после каждого обновления графа, чтобы отвечать на запросы за оптимальное время. Этот вариант подходит для случаев, когда обновлений мало, а запросов – много. В приложениях со сравнимым числом обновлений и запросов более эффективным подходом будет попытка уменьшить время обновления – возможно, ценой увеличения времени выполнения запроса. Это обычно достигается при помощи ослабления предположения о том, что свойство P следует поддерживать явным образом.




Строка 24: Строка 24:
   
   


Определение 2 (Полностью динамическая задача о транзитивном замыкании). Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке:
'''Определение 2 (Полностью динамическая задача о транзитивном замыкании)'''. Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке:


insert(u, v): вставка дуги (u, v) в граф;
insert(u, v): вставка дуги (u, v) в граф;
Строка 33: Строка 33:




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


insert(u, v, w): вставка дуги (u, v) с весом w в граф;
insert(u, v, w): вставка дуги (u, v) с весом w в граф;

Версия от 12:12, 15 июня 2018

Ключевые слова и синонимы

Поиск оптимального соотношения между временем обновления и временем выполнения запроса при решении динамических графовых задач

Постановка задачи

Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Приведем типичное определение.


Определение 1 (Динамический алгоритм на графе). Пусть дан граф и свойство графа P. Динамический алгоритм на графе представляет собой структуру данных, поддерживающую выполнение последовательности следующих операций в различном порядке:

insert(u, v): вставка дуги (u, v) в граф;

delete(u, v): удаление дуги (u ,v) из графа;

query(..): ответ на запрос о выполнении свойства P графа.


Алгоритм на графе является полностью динамическим, если он поддерживает как вставку ребер, так и удаление, и частично динамическим, если поддерживает либо вставку, либо удаление ребер; инкрементный алгоритм поддерживает только вставку ребер, декрементный – только удаление. В некоторых работах исследуются варианты этой задачи, допускающие вставку или удаление более чем одного ребра за один раз либо позволяющие изменять веса ребер. В некоторых случаях обновление может заключаться во вставке или удалении вершины вместе со всеми инцидентными ей ребрами. В других исследованиях рассматриваются только определенные классы графов - например, планарные графы или ориентированные ациклические графы.


Динамическим алгоритмам на графе посвящено множество работ. В числе графовых задач, для которых разработаны эффективные динамические алгоритмы, можно упомянуть задачи о связности графа, о минимальном разрезе, минимальном остовном дереве, транзитивном замыкании и нахождении кратчайших путей (см., например, [3] и ссылки в этой работе). Многие из них выполняют явное обновление свойства P после каждого обновления графа, чтобы отвечать на запросы за оптимальное время. Этот вариант подходит для случаев, когда обновлений мало, а запросов – много. В приложениях со сравнимым числом обновлений и запросов более эффективным подходом будет попытка уменьшить время обновления – возможно, ценой увеличения времени выполнения запроса. Это обычно достигается при помощи ослабления предположения о том, что свойство P следует поддерживать явным образом.


Далее будут рассмотрены алгоритмы для решения динамических графовых задач, неявно поддерживающие свойство графа и потому требующие неконстантного времени на выполнение запроса при более высокой скорости обновлений. В частности, будут рассмотрены две задачи: о динамическом транзитивном замыкании (также называемая динамической задачей достижимости) и динамическая задача нахождения кратчайших путей между всеми парами, определенная ниже.


Определение 2 (Полностью динамическая задача о транзитивном замыкании). Задача заключается в поддержке ориентированного графа и выполнении последовательности следующих операций в различном порядке:

insert(u, v): вставка дуги (u, v) в граф;

delete(u, v): удаление дуги (u ,v) из графа;

query(x, y): возвращает true, если существует ориентированный путь между вершинами x и y, и false в противном случае.


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

insert(u, v, w): вставка дуги (u, v) с весом w в граф;

delete(u, v): удаление дуги (u ,v) из графа;

query(x, y): возвращает расстояние между x и y в графе либо значение +1 в случае, если не существует ориентированного пути из x в y.


Вспомним, что расстояние между вершинами x и y равно весу пути из x в y с минимальным весом, где вес пути определяется как сумма весов входящих в него ребер.

Основные результаты

В данной главе представлен обзор соотношений времени выполнения запросов и обновлений для динамических алгоритмов транзитивного замыкания и нахождения кратчайших путей между всеми парами.


Полностью динамический алгоритм транзитивного замыкания

Первое соотношение времени выполнения запросов и обновлений для этой задачи предложили Хензингер и Кинг [6], доказавшие следующий результат:


Теорема 1 (Хензингер и Кинг [6], 1995). Пусть дан ориентированный граф общего вида. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время O(n/ log n) в наихудшем случае и операции обновления – за амортизированное время O(m p n log2 n).


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


Теорема 2 (Деметреску и Итальяно [4, 5], 2000). Пусть дан ориентированный ациклический граф с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции запроса за время O(n€) и операции вставки и удаления – за время о(и'°'1'е'1' е + n1+€) для любого e 2 [0;1], где <w(l,e, 1) – показатель степени при умножении матрицы n x n€ на матрицу n€ x n.