Алгоритм D* — различия между версиями
Kabanov (обсуждение | вклад) |
Shersh (обсуждение | вклад) м (→Ссылки) |
||
(не показаны 34 промежуточные версии 2 участников) | |||
Строка 1: | Строка 1: | ||
− | '''Алгоритм D*''' {{---}} алгоритм поиска кратчайшего пути во взвешенном ориентированном графе, где структура графа неизвестна заранее или постоянно подвергается изменению. Разработан Свеном Кёнигом и Максимом Лихачевым в 2002 году. | + | '''Алгоритм D*''' {{---}} алгоритм поиска кратчайшего пути во [[Основные определения теории графов|взвешенном ориентированном графе]], где структура графа неизвестна заранее или постоянно подвергается изменению. Разработан Свеном Кёнигом и Максимом Лихачевым в 2002 году. |
== Алгоритм LPA* == | == Алгоритм LPA* == | ||
=== Постановка задачи === | === Постановка задачи === | ||
− | Дан [[Основные определения теории графов|взвешенный ориентированный граф]] <tex> G(V, E) </tex>. Даны вершины <tex> | + | Дан [[Основные определения теории графов|взвешенный ориентированный граф]] <tex> G(V, E) </tex>. Даны вершины: стартовая вершина <tex>f</tex> и конечная вершина <tex>t</tex>. Требуется после каждого изменения графа <tex>G</tex> уметь вычислять функцию <tex>g(s)</tex> для каждой известной вершины <tex>s \in V</tex> |
=== Описание === | === Описание === | ||
− | Функция <tex>g(s)</tex> будет возвращать | + | Функция <tex>g(s)</tex> будет возвращать наименьшую стоимость пути из вершины <tex>f</tex> в <tex>s</tex>. Её значение для алгоритма будет почти аналогичным значению в [[Алгоритм A* | алгоритме A*]], за исключением того, что в данном алгоритме наc интересуют только <tex>g(s)</tex>-значения известных вершин на данной итерации. |
Будем поддерживать для каждой вершины два вида смежных с ней вершин: | Будем поддерживать для каждой вершины два вида смежных с ней вершин: | ||
− | * Обозначим множество <tex>Succ(s) \ | + | * Обозначим множество <tex>Succ(s) \subseteq V</tex> как множество вершин, исходящих из вершины <tex>s</tex>. |
− | * Обозначим множество <tex>Pred(s) \ | + | * Обозначим множество <tex>Pred(s) \subseteq V</tex> как множество вершин, входящих в вершину <tex>s</tex>. |
− | |||
− | Функция <tex>0 \leqslant c(s, s') \leqslant +\infty</tex> будет возвращать стоимость | + | Функция <tex>0 \leqslant c(s, s') \leqslant +\infty</tex> будет возвращать стоимость ребра <tex>(s, s')</tex>. При этом <tex>c(s, s') = +\infty</tex> будет тогда и только тогда, когда ребра <tex>(s, s')</tex> не существует. |
− | + | {{Определение | |
+ | |definition=Будем называть '''rhs-значением''' (англ. ''right-hand side value'') такую функцию <tex>rhs(s)</tex>, которая будет возвращать потенциальное минимальное расстояние от <tex>f</tex> до <tex>s</tex> по следующим правилам: | ||
<tex>rhs(s) = | <tex>rhs(s) = | ||
\begin{cases} | \begin{cases} | ||
− | 0,& \text{if } s = | + | 0,& \text{if } s = f \\ |
− | + | \min\limits_{s' \in Pred(s)}(g(s') + c(s', s),& \text{otherwise} | |
\end{cases} | \end{cases} | ||
</tex> | </tex> | ||
+ | Так как rhs-значение использует минимальное значение из минимальных расстояний от <tex>f</tex> до вершин, входящих в данную вершину <tex>s</tex>, это будет нам давать информацию об оценочном расстоянии от <tex>f</tex> до <tex>s</tex>. | ||
+ | }} | ||
+ | |||
+ | {{Определение | ||
+ | |definition=Вершина <tex>s</tex> называется '''насыщенной''' (англ. ''locally consistent''), если <tex>g(s) = rhs(s)</tex> | ||
+ | }} | ||
+ | |||
+ | {{Определение | ||
+ | |definition=Вершина <tex>s</tex> называется '''переполненной''' (англ. ''locally overconsistent''), если <tex>g(s) > rhs(s)</tex> | ||
+ | }} | ||
− | Вершина <tex>s</tex> | + | {{Определение |
− | + | |definition=Вершина <tex>s</tex> называется '''ненасыщенной''' (англ. ''locally underconsistent''), если <tex>g(s) < rhs(s)</tex> | |
− | + | }} | |
− | |||
Очевидно, что если все вершины насыщены, то мы можем найти расстояние от стартовой вершины до любой. Такой граф будем называть устойчивым (насыщенным). | Очевидно, что если все вершины насыщены, то мы можем найти расстояние от стартовой вершины до любой. Такой граф будем называть устойчивым (насыщенным). | ||
[[Эвристики для поиска кратчайших путей|Эвристическая функция]] <tex>h(s,s')</tex> теперь должна быть неотрицательная и выполнять неравенство треугольника, т.е. | [[Эвристики для поиска кратчайших путей|Эвристическая функция]] <tex>h(s,s')</tex> теперь должна быть неотрицательная и выполнять неравенство треугольника, т.е. | ||
− | <tex>h( | + | <tex>h(t,t) = 0</tex> и <tex>h(s, t) \leqslant c(s,s') + h(s',t)</tex> для всех <tex>s \in V</tex> и <tex>s' \in Succ(s)</tex> |
− | + | {{Определение | |
− | * <tex>k_1(s) = \min(g(s), rhs(s)) + h(s, | + | |definition=Будем называть '''ключом''' вершины такую функцию <tex>key(s)</tex>, которая возвращает вектор из 2-ух значений <tex>k_1(s)</tex>, <tex>k_2(s)</tex>. |
− | * <tex>k_2(s) = \min(g(s), rhs(s))</tex> | + | * <tex>k_1(s) = \min(g(s), rhs(s)) + h(s, t)</tex> |
− | + | * <tex>k_2(s) = \min(g(s), rhs(s))</tex>, | |
− | Если в конце поиска пути <tex>g( | + | где <tex>s</tex> - вершина из множества <tex>V</tex> |
+ | }} | ||
+ | Если в конце поиска пути <tex>g(t) = +\infty</tex>, то мы не смогли найти путь от <tex>f</tex> до <tex>t</tex> на текущей итерации. Но после следующего изменения графа путь вполне может найтись. | ||
=== Псевдокод === | === Псевдокод === | ||
Основная функция, описывающая алгоритм | Основная функция, описывающая алгоритм | ||
− | ''' | + | '''function''' main(): |
− | + | initialize() | |
− | ''' | + | '''while''' ''true'' |
− | + | computeShortestPath() | |
− | + | <font color="green">// В данный момент мы знаем кратчайший путь из f в t.</font> | |
− | |||
− | В данный момент мы знаем кратчайший путь из | ||
Ждем каких-либо изменений графа. | Ждем каких-либо изменений графа. | ||
− | for всех ориентированных ребер | + | '''for''' всех ориентированных ребер (u, v) с измененными весами: |
− | + | Обновляем результат функции c(u, v) | |
− | Обновляем результат функции | + | updateVertex(v) |
− | |||
− | |||
− | |||
− | |||
− | + | Функция инициализации исходного графа устанавливает для всех вершин кроме стартовой вершины <tex>f</tex> значения <tex>g(s)</tex> и <tex>rhs(s)</tex> равными бесконечности. Для стартовой <tex>rhs(f)=0</tex>. Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но <tex>g(f)=+\infty</tex>. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь. | |
− | Функция инициализации исходного графа устанавливает для всех вершин кроме стартовой | + | '''function''' initialize(): |
− | ''' | + | <font color="green">// Заведем [[Двоичная куча|приоритетную очередь]] U, в которую будем помещать вершины.</font> |
− | + | <font color="green">// Сортировка будет производиться по функции key(s).</font> | |
− | //Заведем приоритетную очередь | + | U = <tex>\varnothing</tex> |
− | <tex> | + | '''for''' s <tex>\in</tex> V |
− | for <tex> | + | rhs(s) = g(s) = <tex>+\infty</tex> |
− | + | rhs(f) = 0 | |
− | + | U.insert(f, calcKey(f)) | |
− | U. | ||
− | |||
+ | Функция <tex>key(s)</tex>. Возвращаемые значения сортируются в лексографическом порядке, то есть сначала сортируется по <tex>k_1(s)</tex>, потом по <tex>k_2(s)</tex> | ||
+ | '''function''' calcKey(s): | ||
+ | '''return''' [min(g(s), rhs(s)) + h(s, t), min(g(s), rhs(s))] | ||
− | + | Обновляет данные вершины в соответствие с данными выше определениями. Также поддерживает инвариант того, что в очереди U лежат только ненасыщенные вершины. | |
− | + | '''function''' updateVertex(u): | |
− | + | '''if''' u <tex>\ne</tex> f | |
− | + | <tex>rhs(u) = \min\limits_{s' \in Pred(u)}(g(s') + c(s',u))</tex> | |
− | + | '''if''' u <tex>\in</tex> U | |
+ | U.remove(u) | ||
+ | '''if''' g(u) <tex>\ne</tex> rhs(u) | ||
+ | U.insert(u, calcKey(u)) | ||
− | ''' | + | Функция несколько раз перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин в неубывающем порядке их ключей. Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины. |
− | + | '''function''' computeShortestPath(): | |
− | + | '''while''' U.topKey() < calcKey(t) '''or''' rhs(t) <tex>\ne</tex> g(t) | |
− | + | u = U.pop() | |
− | + | '''if''' g(u) > rhs(u) | |
− | + | g(u) = rhs(u) | |
− | + | '''for''' <tex>s</tex> <tex>\in</tex> Succ(u) | |
− | + | UpdateVertex(s) | |
− | + | '''else''' | |
+ | g(u) = <tex>+\infty</tex> | ||
+ | '''for''' s <tex>\in</tex> Succ(u) <tex>\cup</tex> <tex>\{u\}</tex> | ||
+ | updateVertex(s) | ||
− | + | === Асимптотика === | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | {{Теорема | |
+ | |about=О монотонности изменения ключей | ||
+ | |statement=В течение выполнения функции '''ComputeShortestPath''' вершины, взятые из очереди, монотонно не убывают. | ||
+ | |proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf] | ||
+ | }} | ||
− | ''' | + | {{Теорема |
+ | |about=О необратимой насыщенности | ||
+ | |statement=Если в функции '''ComputeShortestPath''' была взята переполненная вершина, то на следующей итерации она станет насыщенной. | ||
+ | |proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf] | ||
+ | }} | ||
− | == Алгоритм D* == | + | {{Теорема |
− | Пока что был описан только алгоритм LPA*. Он | + | |statement=После выполнения функции '''ComputeShortestPath''' можно восстановить путь из <tex>f</tex> в <tex>t</tex>. Для этого, начиная с вершины <tex>t</tex>, нужно постоянно передвигаться к такой вершине <tex>s'</tex>, входящей в <tex>t</tex>, чтобы <tex>g(s') + c(s',s)</tex> было минимальным, до тех пора, пока не будет достигнута вершина <tex>f</tex>. |
+ | |proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf] | ||
+ | }} | ||
+ | |||
+ | Таким образом мы описали алгоритм LPA*. Он вычисляет длину кратчайшего пути между вершинами <tex>f</tex> и <tex>t</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n \cdot m \cdot \log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite. | ||
+ | |||
+ | '''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку <tex>O(n \cdot \log(n))</tex>. | ||
+ | |||
+ | == Алгоритм D* (Первая версия) == | ||
+ | Пока что был описан только алгоритм LPA*. Он находит кратчайшее расстояние между начальной и конечной вершинами при любом изменении данного графа. Его первоначальный поиск полностью совпадает с алгоритмом A*, но последующие итерации способны использовать информацию из предыдущих поисков. | ||
=== Постановка задачи === | === Постановка задачи === | ||
− | Теперь на основе LPA* опишем алгоритм D*, который способен определять расстояние между текущей вершиной <tex> | + | Дан [[Основные определения теории графов|взвешенный ориентированный граф]] <tex> G(V, E) </tex>. Даны вершины <tex>f</tex> и <tex>t</tex>. Требуется в процессе движения по кратчайшему пути в графе <tex>G</tex> обновлять значения функции <tex>g(s)</tex> при поступлении новой информации о графе <tex>G</tex>. |
+ | |||
+ | Теперь на основе LPA* опишем алгоритм D*, который способен определять расстояние между текущей вершиной <tex>f</tex>, в которой, допустим, находится способный к сканированию местности "робот", и конечной вершиной <tex>t</tex> при каждом изменении графа в то время, как наш "робот" движется вдоль найденного пути. | ||
− | [[Файл:Схема_движения_робота_Dstar.png|350px|thumb|right|Схема движения | + | [[Файл:Схема_движения_робота_Dstar.png|350px|thumb|right|Схема движения "робота" в процессе работы алгоритма D*. Информация о серых клетках ему неизвестна до тех пор, пока они не попадут в его зону обзора. В данном примере зона обзора составляет 1 клетку в 8-ми направлениях.]] |
=== Описание === | === Описание === | ||
− | Опишем первую версию алгоритма D*. | + | Опишем первую версию алгоритма D*. Так как при движении по кратчайшему пути путь может только сокращаться и происходит изменение только стартовой вершины, то можно применить идею из алгоритма LPA*. |
'''Примечание''': Большинство функций переходят в данный алгоритм без изменений, поэтому опишем только измененные части. | '''Примечание''': Большинство функций переходят в данный алгоритм без изменений, поэтому опишем только измененные части. | ||
Строка 122: | Строка 140: | ||
Для начала мы поменяем направление поиска в графе. | Для начала мы поменяем направление поиска в графе. | ||
− | Теперь функция g(s) хранит минимальное известное расстояние от <tex> | + | Теперь функция g(s) хранит минимальное известное расстояние от <tex>t</tex> до <tex>s</tex>. Свойства остаются прежними. |
[[Эвристики для поиска кратчайших путей|Эвристическая функция]] <tex>h(s,s')</tex> теперь должна быть неотрицательная и обратно-устойчивая, т.е. | [[Эвристики для поиска кратчайших путей|Эвристическая функция]] <tex>h(s,s')</tex> теперь должна быть неотрицательная и обратно-устойчивая, т.е. | ||
− | <tex>h( | + | <tex>h(f,f) = 0</tex> и <tex>h(f, s) \leqslant h(f,s') + c(s',s)</tex> для всех <tex>s \in S</tex> и <tex>s' \in Pred(s)</tex>. Очевидно, что при движении робота <tex>f</tex> изменяется, поэтому данные свойства должны выполняться для всех <tex>f \in V</tex>. |
− | Дополнительное условие выхода также меняется, т.е. при <tex>g( | + | Дополнительное условие выхода также меняется, т.е. при <tex>g(f) = +\infty</tex> путь не найден на данной итерации. Иначе путь найден и "робот" может проследовать по нему. |
− | '''Примечание''': Так же следует отметить, что функция '''Initialize''' не обязана инициализировать абсолютно все вершины перед стартом алгоритма. Это важно, так как | + | '''Примечание''': Так же следует отметить, что функция '''Initialize''' не обязана инициализировать абсолютно все вершины перед стартом алгоритма. Это важно, так как на практике число вершин может быть огромным, и только немногие будут пройдены роботом в процессе движения. Так же это дает возможность добавления/удаления ребер без потери устойчивости всех подграфов данного графа. |
− | === Псевдокод | + | === Псевдокод === |
− | При такой постановке задачи псевдокод не сильно меняется | + | При такой постановке задачи псевдокод не сильно меняется, но функция '''Main''' все-таки претерпевает значительные изменения. |
− | ''' | + | '''function''' calcKey(s): |
− | return [ | + | '''return''' [min(g(s), rhs(s)) + h(f,s), min(g(s), rhs(s))] |
− | ''' | + | '''function''' initialize(): |
− | U = <tex>\varnothing</tex> | + | U = <tex>\varnothing</tex> |
− | for <tex> | + | '''for''' s <tex>\in</tex> V |
− | + | rhs(s) = g(s) = <tex>+\infty</tex> | |
− | + | rhs(t) = 0 | |
− | U. | + | U.insert(t, calcKey(t)) |
− | ''' | + | '''function''' UpdateVertex(u): |
− | if | + | '''if''' u <tex>\ne</tex> t |
− | rhs(u) = <tex> | + | rhs(u) = <tex>\min\limits_{s' \in Succ(u)}(c(u,s')+g(s'))</tex> |
− | if | + | '''if''' u <tex>\in</tex> U |
− | U. | + | U.remove(u) |
− | if (<tex> | + | '''if''' g(u) <tex>\ne</tex> rhs(u) |
− | U. | + | U.insert(u, calcKey(u)) |
− | ''' | + | '''function''' ComputeShortestPath(): |
− | while | + | '''while''' U.topKey() < calcKey(f) or rhs(f) <tex>\ne</tex> g(f) |
− | u = U. | + | u = U.pop() |
− | if (g(u) > rhs(u)) | + | '''if''' (g(u) > rhs(u)) |
− | g(u) = rhs(u) | + | g(u) = rhs(u) |
− | for <tex> | + | '''for''' s <tex>\in</tex> Pred(u) |
− | + | updateVertex(s) | |
− | else | + | '''else''' |
− | g(u) = <tex>+\infty</tex> | + | g(u) = <tex>+\infty</tex> |
− | for <tex>s \in Pred(u) \cup | + | '''for''' <tex>s</tex> <tex>\in</tex> Pred(u) <tex>\cup</tex> {u} |
− | + | updateVertex(s) | |
− | ''' | + | '''function''' main(): |
− | + | initialize() | |
− | ''' | + | computeShortestPath() |
− | + | '''while''' <tex>f \ne t</tex> | |
− | // if ( | + | <font color="green">// '''if''' (g(f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font> |
− | <tex> | + | |
− | Передвинулись вдоль найденного пути и изменили вершину <tex> | + | <tex>f</tex> = такая вершина s', что <tex>\min\limits_{s' \in Succ(f)}(c(f, s') + g(s'))</tex> |
+ | |||
+ | Передвинулись вдоль найденного пути и изменили вершину <tex>f</tex> | ||
Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним. | Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним. | ||
− | if | + | '''if''' граф изменился |
− | for всех ориентированных ребер <tex>(u | + | '''for''' всех ориентированных ребер <tex>(u, v)</tex> с измененными весами: |
− | Обновляем результат функции <tex>c(u | + | Обновляем результат функции <tex>c(u, v)</tex> |
− | ''' | + | updateVertex(u) |
− | + | '''for''' <tex>s</tex> <tex>\in</tex> U | |
− | U. | + | U.update(s, CalcKey(s)) |
− | + | computeShortestPath() | |
+ | |||
+ | === Асимптотика === | ||
{{Теорема | {{Теорема | ||
Строка 184: | Строка 206: | ||
|about=Об устойчивой насыщенности вершин | |about=Об устойчивой насыщенности вершин | ||
|statement=Функция '''ComputeShortestPath''' в данной версии алгоритма ''расширяет'' вершину максимум 2 раза, а именно 1 раз, если вершина ненасыщена, и максимум 1 раз, если она переполнена. | |statement=Функция '''ComputeShortestPath''' в данной версии алгоритма ''расширяет'' вершину максимум 2 раза, а именно 1 раз, если вершина ненасыщена, и максимум 1 раз, если она переполнена. | ||
+ | |proof=Доказательство [http://www.cs.cmu.edu/~maxim/files/aij04.pdf] | ||
}} | }} | ||
− | == | + | == Алгоритм D* (Вторая версия) == |
+ | |||
+ | === Описание === | ||
+ | В первой версии алгоритма была серьезная проблема в том, что для каждой вершины в приоритетной очереди нужно было обновлять ключ суммарно за <tex>O(n \cdot \log(n))</tex>. Это дорогая операция, так как очередь может содержать огромное число вершин. Воспользуемся оригинальным методом поиска и изменим основной цикл, чтобы избежать постоянного перестроения очереди <tex>U</tex>. | ||
+ | |||
+ | Теперь эвристическая функция должна поддерживать неравенство треугольника для всех вершин <tex>s,s',s'' \in V</tex>, т.е. <tex>h(s,s'') \leqslant h(s, s') + h(s',s'')</tex>. Так же должно выполняться свойство <tex>h(s,s') \leqslant c^*(s,s')</tex>, где <tex>c^*(s,s')</tex> - стоимость перехода по кратчайшему пути из <tex>s</tex> в <tex>s'</tex>, при этом <tex>s</tex> и <tex>s'</tex> не должны быть обязательно смежными. Такие свойства не противоречат свойствами из первой версии, а лишь усиливают их. | ||
+ | |||
+ | Допустим, что после того, как робот продвинется вдоль найденного пути на предыдущих итерациях, из вершины <tex>s</tex> в <tex>s'</tex>, он обнаружит изменения в графе. Первая компонента ключей <tex>k_1(s')</tex> может уменьшится максимум на <tex>h(s,s')</tex> (по определению ключа). Вторая компонента не зависит от функции h. Аналогично первой версии алгоритма, мы должны уменьшить первую компоненту ключа у всех вершин в очереди U. Очевидно, что <tex>h(s,s')</tex> будет одинаковым для всех вершин из U. Порядок в очереди не изменится, если произвести уменьшение. Следовательно уменьшение можно отложить, тем самым очередь не придется перестраивать на каждой итерации. Так же исходя из нового определения функции <tex>h</tex>, её значение будет всегда меньше, чем разность первых компонент ключей у соседних по приоритету вершин. Таким образом мы можем добавлять h(s,s') ко всем <tex>k_1(s')</tex> у ключей вершин из U. | ||
+ | |||
+ | Будем называть <tex>K_m</tex> ключевым модификатором. В нем мы и будет хранить сумму <tex>h(s,s')</tex>, которые нужно добавить ко всем вершинам из U. | ||
+ | |||
+ | === Псевдокод === | ||
+ | |||
+ | '''function''' calcKey(s): | ||
+ | '''return''' [min(g(s), rhs(s)) + h(f, s) + <tex>K_m</tex>, min(g(s), rhs(s))] | ||
+ | |||
+ | '''function''' initialize(): | ||
+ | U = <tex>\varnothing</tex> | ||
+ | <tex>K_m = 0</tex> | ||
+ | '''for''' s <tex>\in</tex> V | ||
+ | rhs(s) = g(s) = <tex>+\infty</tex> | ||
+ | rhs(t) = 0 | ||
+ | U.insert(t, CalcKey(t)) | ||
+ | |||
+ | '''function''' updateVertex(u): | ||
+ | '''if''' u <tex>\ne</tex> t | ||
+ | rhs(u) = <tex>\min\limits_{s' \in Succ(u)}(c(u,s')+g(s'))</tex> | ||
+ | '''if''' u <tex>\in</tex> U | ||
+ | U.remove(u) | ||
+ | '''if''' g(u) <tex>\ne</tex> rhs(u) | ||
+ | U.insert(u, calcKey(u)) | ||
+ | |||
+ | '''function''' computeShortestPath(): | ||
+ | '''while''' U.topKey() < calcKey(f) '''or''' rhs(f) <tex>\ne</tex> g(f) | ||
+ | <tex>K_{old}</tex> = U.topKey() | ||
+ | u = U.pop() | ||
+ | |||
+ | '''if''' <tex>K_{old}</tex> < calcKey(u) | ||
+ | U.insert(u, calcKey(u)) | ||
+ | |||
+ | '''if''' (g(u) > rhs(u)) | ||
+ | g(u) = rhs(u) | ||
+ | '''for''' <tex>s</tex> <tex>\in</tex> Pred(u) | ||
+ | updateVertex(s) | ||
+ | '''else''' | ||
+ | g(u) = <tex>+\infty</tex> | ||
+ | '''for''' <tex>s</tex> <tex>\in</tex> Pred(u) <tex>\cup</tex> <tex>\{u\}</tex> | ||
+ | updateVertex(s) | ||
+ | |||
+ | '''function''' main(): | ||
+ | <tex>s_{last} = f</tex> | ||
+ | initialize() | ||
+ | computeShortestPath() | ||
+ | '''while''' f <tex>\ne</tex> t | ||
+ | <font color="green">// if (g(f) = <tex>+\infty</tex>) тогда путь на данной итерации не найден.</font> | ||
+ | <tex>f</tex> = такая вершина s', что <tex>\min\limits_{s' \in Succ(f)}(c(f, s') + g(s'))</tex> | ||
+ | Передвинулись вдоль найденного пути и изменили вершину <tex>f</tex>. | ||
+ | Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним. | ||
+ | '''if''' граф изменился | ||
+ | <tex>K_m = K_m + h(s_{last}, h_{start})</tex> | ||
+ | <tex>s_{last} = f</tex> | ||
+ | '''for''' всех ориентированных ребер (u, v) с измененными весами: | ||
+ | Обновляем результат функции c(u, v) | ||
+ | updateVertex(u) | ||
+ | computeShortestPath() | ||
+ | |||
+ | === Асимптотика === | ||
+ | |||
+ | С помощью введения ключевого модификатора <tex>K_m</tex> и отложенного обновления ключей вершин получилось убрать из итерации алгоритма <tex>O(n \cdot \log(n))</tex> операций, которые тратились на обновление очереди <tex>U</tex>. Очевидно, что на основе теорем, приведенных выше, алгоритм использовал <tex>O(2 \cdot n \cdot \log(n))</tex> операций. Итак, нам удалось уменьшить константу в 2 раза, что дает существенный рост производительности на практических задачах. | ||
+ | |||
+ | === Пример работы === | ||
+ | {| class="wikitable" | ||
+ | |- | ||
+ | | style="width:50%;text-align:center;" | [[Файл:Схема_движения_робота_Dstarv2_1.png|400px]] || style="width:50%;text-align:center;" | [[Файл:Схема_движения_робота_Dstarv2_2.png|400px]] | ||
+ | |- | ||
+ | | style="width:50%;text-align:center;" | Итерации в функции '''ComputeShortestPath''' на исходном графе. || style="width:50%;text-align:center;" | Итерации в функции '''ComputeShortestPath''' после изменения графа. (Второй вызов функции) | ||
+ | |} | ||
+ | |||
+ | ==Источники информации== | ||
* [http://en.wikipedia.org/wiki/D* Wikipedia:D*] | * [http://en.wikipedia.org/wiki/D* Wikipedia:D*] | ||
* [http://idm-lab.org/project-a.html Sven Koenig` web page] | * [http://idm-lab.org/project-a.html Sven Koenig` web page] |
Текущая версия на 17:54, 16 сентября 2015
Алгоритм D* — алгоритм поиска кратчайшего пути во взвешенном ориентированном графе, где структура графа неизвестна заранее или постоянно подвергается изменению. Разработан Свеном Кёнигом и Максимом Лихачевым в 2002 году.
Содержание
Алгоритм LPA*
Постановка задачи
Дан взвешенный ориентированный граф . Даны вершины: стартовая вершина и конечная вершина . Требуется после каждого изменения графа уметь вычислять функцию для каждой известной вершины
Описание
Функция алгоритме A*, за исключением того, что в данном алгоритме наc интересуют только -значения известных вершин на данной итерации.
будет возвращать наименьшую стоимость пути из вершины в . Её значение для алгоритма будет почти аналогичным значению вБудем поддерживать для каждой вершины два вида смежных с ней вершин:
- Обозначим множество как множество вершин, исходящих из вершины .
- Обозначим множество как множество вершин, входящих в вершину .
Функция
будет возвращать стоимость ребра . При этом будет тогда и только тогда, когда ребра не существует.
Определение: |
Будем называть rhs-значением (англ. right-hand side value) такую функцию Так как rhs-значение использует минимальное значение из минимальных расстояний от до вершин, входящих в данную вершину , это будет нам давать информацию об оценочном расстоянии от до . | , которая будет возвращать потенциальное минимальное расстояние от до по следующим правилам:
Определение: |
Вершина | называется насыщенной (англ. locally consistent), если
Определение: |
Вершина | называется переполненной (англ. locally overconsistent), если
Определение: |
Вершина | называется ненасыщенной (англ. locally underconsistent), если
Очевидно, что если все вершины насыщены, то мы можем найти расстояние от стартовой вершины до любой. Такой граф будем называть устойчивым (насыщенным).
Эвристическая функция теперь должна быть неотрицательная и выполнять неравенство треугольника, т.е. и для всех и
Определение: |
Будем называть ключом вершины такую функцию
| , которая возвращает вектор из 2-ух значений , .
Если в конце поиска пути
, то мы не смогли найти путь от до на текущей итерации. Но после следующего изменения графа путь вполне может найтись.Псевдокод
Основная функция, описывающая алгоритм
function main(): initialize() while true computeShortestPath() // В данный момент мы знаем кратчайший путь из f в t. Ждем каких-либо изменений графа. for всех ориентированных ребер (u, v) с измененными весами: Обновляем результат функции c(u, v) updateVertex(v)
Функция инициализации исходного графа устанавливает для всех вершин кроме стартовой вершины
значения и равными бесконечности. Для стартовой . Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но . Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь.function initialize(): // Заведем приоритетную очередь U, в которую будем помещать вершины. // Сортировка будет производиться по функции key(s). U = for s V rhs(s) = g(s) = rhs(f) = 0 U.insert(f, calcKey(f))
Функция
. Возвращаемые значения сортируются в лексографическом порядке, то есть сначала сортируется по , потом поfunction calcKey(s): return [min(g(s), rhs(s)) + h(s, t), min(g(s), rhs(s))]
Обновляет данные вершины в соответствие с данными выше определениями. Также поддерживает инвариант того, что в очереди U лежат только ненасыщенные вершины.
function updateVertex(u): if uf if u U U.remove(u) if g(u) rhs(u) U.insert(u, calcKey(u))
Функция несколько раз перерасчитывает значение
у ненасыщенных вершин в неубывающем порядке их ключей. Такой перерасчет значения будем называть расширением вершины.function computeShortestPath(): while U.topKey() < calcKey(t) or rhs(t)g(t) u = U.pop() if g(u) > rhs(u) g(u) = rhs(u) for Succ(u) UpdateVertex(s) else g(u) = for s Succ(u) updateVertex(s)
Асимптотика
Теорема (О монотонности изменения ключей): |
В течение выполнения функции ComputeShortestPath вершины, взятые из очереди, монотонно не убывают. |
Доказательство: |
Доказательство [1] |
Теорема (О необратимой насыщенности): |
Если в функции ComputeShortestPath была взята переполненная вершина, то на следующей итерации она станет насыщенной. |
Доказательство: |
Доказательство [2] |
Теорема: |
После выполнения функции ComputeShortestPath можно восстановить путь из в . Для этого, начиная с вершины , нужно постоянно передвигаться к такой вершине , входящей в , чтобы было минимальным, до тех пора, пока не будет достигнута вершина . |
Доказательство: |
Доказательство [3] |
Таким образом мы описали алгоритм LPA*. Он вычисляет длину кратчайшего пути между вершинами
и , используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за . Улучшим эту оценку с помощью алгоритма D* lite.Примечание: на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку
.Алгоритм D* (Первая версия)
Пока что был описан только алгоритм LPA*. Он находит кратчайшее расстояние между начальной и конечной вершинами при любом изменении данного графа. Его первоначальный поиск полностью совпадает с алгоритмом A*, но последующие итерации способны использовать информацию из предыдущих поисков.
Постановка задачи
Дан взвешенный ориентированный граф . Даны вершины и . Требуется в процессе движения по кратчайшему пути в графе обновлять значения функции при поступлении новой информации о графе .
Теперь на основе LPA* опишем алгоритм D*, который способен определять расстояние между текущей вершиной
, в которой, допустим, находится способный к сканированию местности "робот", и конечной вершиной при каждом изменении графа в то время, как наш "робот" движется вдоль найденного пути.Описание
Опишем первую версию алгоритма D*. Так как при движении по кратчайшему пути путь может только сокращаться и происходит изменение только стартовой вершины, то можно применить идею из алгоритма LPA*.
Примечание: Большинство функций переходят в данный алгоритм без изменений, поэтому опишем только измененные части.
Для начала мы поменяем направление поиска в графе.
Теперь функция g(s) хранит минимальное известное расстояние от
до . Свойства остаются прежними.Эвристическая функция теперь должна быть неотрицательная и обратно-устойчивая, т.е. и для всех и . Очевидно, что при движении робота изменяется, поэтому данные свойства должны выполняться для всех .
Дополнительное условие выхода также меняется, т.е. при
путь не найден на данной итерации. Иначе путь найден и "робот" может проследовать по нему.Примечание: Так же следует отметить, что функция Initialize не обязана инициализировать абсолютно все вершины перед стартом алгоритма. Это важно, так как на практике число вершин может быть огромным, и только немногие будут пройдены роботом в процессе движения. Так же это дает возможность добавления/удаления ребер без потери устойчивости всех подграфов данного графа.
Псевдокод
При такой постановке задачи псевдокод не сильно меняется, но функция Main все-таки претерпевает значительные изменения.
function calcKey(s): return [min(g(s), rhs(s)) + h(f,s), min(g(s), rhs(s))]
function initialize(): U =for s V rhs(s) = g(s) = rhs(t) = 0 U.insert(t, calcKey(t))
function UpdateVertex(u): if ut rhs(u) = if u U U.remove(u) if g(u) rhs(u) U.insert(u, calcKey(u))
function ComputeShortestPath(): while U.topKey() < calcKey(f) or rhs(f)g(f) u = U.pop() if (g(u) > rhs(u)) g(u) = rhs(u) for s Pred(u) updateVertex(s) else g(u) = for Pred(u) {u} updateVertex(s)
function main(): initialize() computeShortestPath() while// if (g(f) = ) тогда путь на данной итерации не найден. = такая вершина s', что Передвинулись вдоль найденного пути и изменили вершину Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним. if граф изменился for всех ориентированных ребер с измененными весами: Обновляем результат функции updateVertex(u) for U U.update(s, CalcKey(s)) computeShortestPath()
Асимптотика
Теорема (Свен Кёниг, Об устойчивой насыщенности вершин): |
Функция ComputeShortestPath в данной версии алгоритма расширяет вершину максимум 2 раза, а именно 1 раз, если вершина ненасыщена, и максимум 1 раз, если она переполнена. |
Доказательство: |
Доказательство [4] |
Алгоритм D* (Вторая версия)
Описание
В первой версии алгоритма была серьезная проблема в том, что для каждой вершины в приоритетной очереди нужно было обновлять ключ суммарно за
. Это дорогая операция, так как очередь может содержать огромное число вершин. Воспользуемся оригинальным методом поиска и изменим основной цикл, чтобы избежать постоянного перестроения очереди .Теперь эвристическая функция должна поддерживать неравенство треугольника для всех вершин
, т.е. . Так же должно выполняться свойство , где - стоимость перехода по кратчайшему пути из в , при этом и не должны быть обязательно смежными. Такие свойства не противоречат свойствами из первой версии, а лишь усиливают их.Допустим, что после того, как робот продвинется вдоль найденного пути на предыдущих итерациях, из вершины
в , он обнаружит изменения в графе. Первая компонента ключей может уменьшится максимум на (по определению ключа). Вторая компонента не зависит от функции h. Аналогично первой версии алгоритма, мы должны уменьшить первую компоненту ключа у всех вершин в очереди U. Очевидно, что будет одинаковым для всех вершин из U. Порядок в очереди не изменится, если произвести уменьшение. Следовательно уменьшение можно отложить, тем самым очередь не придется перестраивать на каждой итерации. Так же исходя из нового определения функции , её значение будет всегда меньше, чем разность первых компонент ключей у соседних по приоритету вершин. Таким образом мы можем добавлять h(s,s') ко всем у ключей вершин из U.Будем называть
ключевым модификатором. В нем мы и будет хранить сумму , которые нужно добавить ко всем вершинам из U.Псевдокод
function calcKey(s):
return [min(g(s), rhs(s)) + h(f, s) +
, min(g(s), rhs(s))]
function initialize(): U =for s V rhs(s) = g(s) = rhs(t) = 0 U.insert(t, CalcKey(t))
function updateVertex(u): if ut rhs(u) = if u U U.remove(u) if g(u) rhs(u) U.insert(u, calcKey(u))
function computeShortestPath(): while U.topKey() < calcKey(f) or rhs(f)g(f) = U.topKey() u = U.pop() if < calcKey(u) U.insert(u, calcKey(u)) if (g(u) > rhs(u)) g(u) = rhs(u) for Pred(u) updateVertex(s) else g(u) = for Pred(u) updateVertex(s)
function main():initialize() computeShortestPath() while f t // if (g(f) = ) тогда путь на данной итерации не найден. = такая вершина s', что Передвинулись вдоль найденного пути и изменили вершину . Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним. if граф изменился for всех ориентированных ребер (u, v) с измененными весами: Обновляем результат функции c(u, v) updateVertex(u) computeShortestPath()
Асимптотика
С помощью введения ключевого модификатора
и отложенного обновления ключей вершин получилось убрать из итерации алгоритма операций, которые тратились на обновление очереди . Очевидно, что на основе теорем, приведенных выше, алгоритм использовал операций. Итак, нам удалось уменьшить константу в 2 раза, что дает существенный рост производительности на практических задачах.Пример работы
![]() |
![]() |
Итерации в функции ComputeShortestPath на исходном графе. | Итерации в функции ComputeShortestPath после изменения графа. (Второй вызов функции) |