418
правок
Изменения
changed names
=== Постановка задачи ===
Дан [[Основные определения теории графов|взвешенный ориентированный граф]] <tex> G(V, E) </tex>. Даны вершины <tex>s_{start}f</tex> и <tex>s_{goal}t</tex>. Требуется после каждого изменения графа <tex>G</tex> уметь вычислять функцию <tex>g(s)</tex> для каждой известной вершины <tex>s \in V</tex>
=== Описание ===
Функция <tex>g(s)</tex> будет возвращать последнее известное (и самое минимальное) значение расстояния от вершины <tex>s_{start}f</tex> до <tex>s</tex>. Её значение будет почти аналогичным значению в [[Алгоритм A* | алгоритме A*]], за исключением того, что в данном алгоритме наc интересуют только <tex>g(s)</tex>-значения известных вершин на данной итерации.
Будем поддерживать для каждой вершины два вида смежных с ней вершин:
{{Определение
|definition=Будем называть '''rhs-значением''' (''right-hand side value'') такую функцию <tex>rhs(s)</tex>, которая будет возвращать потенциальное минимальное расстояние от <tex>s_{start}f</tex> до <tex>s</tex> по следующим правилам:
<tex>rhs(s) =
\begin{cases}
0,& \text{if } s = s_{start} f \\
\min\limits_{s' \in Pred(s)}(g(s') + c(s', s),& \text{otherwise}
\end{cases}
</tex>
Так как rhs-значение использует минимальное значение из минимальных расстояний от <tex>s_{start}f</tex> до вершин, входящих в данную вершину <tex>s</tex>, это будет нам давать информацию об оценочном расстоянии от <tex>s_{start}f</tex> до <tex>s</tex>.
}}
[[Эвристики для поиска кратчайших путей|Эвристическая функция]] <tex>h(s,s')</tex> теперь должна быть неотрицательная и выполнять неравенство треугольника, т.е.
<tex>h(s_{goal}t,s_{goal}t) = 0</tex> и <tex>h(s, s_{goal}t) \leqslant c(s,s') + h(s',s_{goal}t)</tex> для всех <tex>s \in V</tex> и <tex>s' \in Succ(s)</tex>
{{Определение
|definition=Будем называть '''ключом''' вершины такую функцию <tex>key(s)</tex>, которая возвращает вектор из 2-ух значений <tex>k_1(s)</tex>, <tex>k_2(s)</tex>.
* <tex>k_1(s) = \min(g(s), rhs(s)) + h(s, s_{goal}t)</tex>
* <tex>k_2(s) = \min(g(s), rhs(s))</tex>,
где <tex>s</tex> - вершина из множества <tex>V</tex>
}}
Если в конце поиска пути <tex>g(s_{goal}t) = +\infty</tex>, то мы не смогли найти путь от <tex>s_{start}f</tex> до <tex>s_{goal}t</tex> на текущей итерации. Но после следующего изменения графа путь вполне может найтись.
=== Псевдокод ===
while (true)
'''ComputeShortestPath'''();
//В данный момент мы знаем кратчайший путь из <tex>s_{start}f</tex> в <tex>s_{goal}t</tex>.
Ждем каких-либо изменений графа.
for всех ориентированных ребер <tex>(u; v)</tex> с измененными весами:
Теперь опишем составные элементы подробнее
Функция инициализации исходного графа устанавливает для всех вершин кроме стартовой (<tex>s_{start}f</tex>) значения <tex>g(s)</tex> и <tex>rhs(s)</tex> равными бесконечности. Для стартовой <tex>rhs(s_{start}f)=0</tex>. Очевидно, что минимальное расстояние от стартовой вершины до самой себя должно быть равным 0, но <tex>g(s_{start}f)=+\infty</tex>. Это сделано для того, чтобы стартовая вершина была ненасыщенной и имела право попасть в приоритетную очередь.
'''Initialize'''():
//Заведем [[Двоичная куча|приоритетную очередь]] <tex>U</tex>, в которую будем помещать вершины. Сортировка будет производиться по функции <tex>key(s)</tex>.
for <tex>s \in S</tex>
<tex>rhs(s) = g(s) = \infty;</tex>
<tex>rhs(s_{start}f) = 0;</tex> U.Insert(<tex>s_{start}f</tex>; CalcKey(<tex>s_{start}f</tex>));
//Функция <tex>key(s)</tex>. Возвращаемые значения сортируются в лексографическом порядке, т.е. сначала <tex>k_1(s)</tex>, потом <tex>k_2(s)</tex>
'''CalcKey'''(s):
return [<tex>\min(g(s); rhs(s)) + h(s; s_{goal}t)</tex>; <tex>\min(g(s); rhs(s))</tex>];
'''UpdateVertex'''(<tex>u</tex>):
if <tex>u \ne s_{start}f</tex>
<tex>rhs(u) = \min\limits_{s' \in Pred(u)}(g(s') + c(s',u));</tex>
if <tex>u \in U</tex>
U.Insert(<tex>u</tex>; CalcKey(<tex>u</tex>));
// Функция неоднократно несколько раз перерасчитывает значение <tex>g(s)</tex> у ненасыщенных вершин в неубывающем порядке их ключей. Такой перерасчет значения <tex>g(s)</tex> будем называть ''расширением'' вершины.
'''ComputeShortestPath'''():
while (U.TopKey() < CalcKey(<tex>s_{goal}t</tex>) OR rhs(<tex>s_{goal}t</tex>) <tex>\ne</tex> g(<tex>s_{goal}t</tex>))
u = U.Pop();
if g(u) > rhs(u)
UpdateVertex(s);
Таким образом мы описали алгоритм LPA*. Он неоднократно определяет путь между вершинами <tex>s_{start}f</tex> и <tex>s_{goal}t</tex>, используя при этом данные из предыдущих итераций. Очевидно, что в худшем случае (а именно когда все ребра вокруг текущей вершины изменили свой вес) алгоритм будет работать как последовательные вызовы алгоритма А* за <tex>O(n^2 \cdot \log(n))</tex>. Улучшим эту оценку с помощью алгоритма D* lite.
'''Примечание''': на практике же такой подход тоже имеет место на плотных графах (или матрицах), так как в среднем дает оценку <tex>O(n \cdot \log(n))</tex>.
== Алгоритм D* (Первая версия) ==
=== Постановка задачи ===
Дан [[Основные определения теории графов|взвешенный ориентированный граф]] <tex> G(V, E) </tex>. Даны вершины <tex>s_{start}f</tex> и <tex>s_{goal}t</tex>. Требуется в процессе движения по кратчайшему пути в графе <tex>G</tex> обновлять значения функции <tex>g(s)</tex> при поступлении новой информации о графе <tex>G</tex>.
Теперь на основе LPA* опишем алгоритм D*, который способен определять расстояние между текущей вершиной <tex>s_{start}f</tex>, в которой, допустим, находится способный к сканированию местности "робот", и конечной вершиной <tex>s_{goal}t</tex> при каждом изменении графа в то время, как наш "робот" движется вдоль найденного пути.
[[Файл:Схема_движения_робота_Dstar.png|350px|thumb|right|Схема движения "робота" в процессе работы алгоритма D*. Информация о серых клетках ему неизвестна до определенной итерации.]]
Для начала мы поменяем направление поиска в графе.
Теперь функция g(s) хранит минимальное известное расстояние от <tex>s_{goal}t</tex> до <tex>s</tex>. Свойства остаются прежними.
[[Эвристики для поиска кратчайших путей|Эвристическая функция]] <tex>h(s,s')</tex> теперь должна быть неотрицательная и обратно-устойчивая, т.е.
<tex>h(s_{start}f,s_{start}f) = 0</tex> и <tex>h(s_{start}f, s) \leqslant h(s_{start}f,s') + c(s',s)</tex> для всех <tex>s \in S</tex> и <tex>s' \in Pred(s)</tex>. Очевидно, что при движении робота <tex>s_{start}f</tex> изменяется, поэтому данные свойства должны выполняться для всех <tex>s_{start} f \in V</tex>.
Дополнительное условие выхода также меняется, т.е. при <tex>g(s_{start}f) = +\infty</tex> путь не найден на данной итерации. Иначе путь найден и "робот" может проследовать по нему.
'''Примечание''': Так же следует отметить, что функция '''Initialize''' не обязана инициализировать абсолютно все вершины перед стартом алгоритма. Это важно, так как на практике число вершин может быть огромным, и только немногие будут пройдены роботом в процессе движения. Так же это дает возможность добавления/удаления ребер без потери устойчивости всех подграфов данного графа.
'''CalcKey'''(s):
return [<tex>\min(g(s);rhs(s)) + h(s_{start}f;s)</tex>;<tex>\min(g(s); rhs(s))</tex>];
'''Initialize'''():
for <tex>s \in S</tex>
<tex>rhs(s) = g(s) = +\infty</tex>
<tex>rhs(s_{goal}t) = 0</tex> U.Insert(<tex>s_{goal}t</tex>; CalcKey(<tex>s_{goal}t</tex>));
'''UpdateVertex'''(u):
if (<tex>u \ne s_{goal}t</tex>)
rhs(u) = <tex>\min\limits_{s' \in Succ(u)}(c(u,s')+g(s'));</tex>
if (<tex>u \in U</tex>)
'''ComputeShortestPath'''():
while (U.TopKey() < CalcKey(<tex>s_{start}f</tex>) OR <tex>rhs(s_{start}f) \ne g(s_{start}f)</tex>)
u = U.Pop();
if (g(u) > rhs(u))
'''Initialize'''();
'''ComputeShortestPath'''();
while (<tex>s_{start} f \ne s_{goal}t</tex>) // if (<tex>g(s_{start}f) = \infty</tex>) тогда путь на данной итерации не найден. <tex>s_{start}f</tex> = такая вершина s', что <tex>\min\limits_{s' \in Succ(s_{start}f)}(c(s_{start}f, s') + g(s'))</tex> Передвинулись вдоль найденного пути и изменили вершину <tex>s_{start}f</tex>;
Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним.
if (граф изменился)
=== Описание ===
В первой версии алгоритма была серьезная проблема в том, что для каждой вершины в приоритетной очереди нужно было обновлять ключ суммарно за <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> не должны быть обязательно смежными. Такие свойства не противоречат свойствами из первой версии, а лишь усиливают их.
'''CalcKey'''(s):
return [<tex>\min(g(s);rhs(s)) + h(s_{start}f;s) + K_m</tex>;<tex>\min(g(s); rhs(s))</tex>];
'''Initialize'''():
for <tex>s \in S</tex>
<tex>rhs(s) = g(s) = +\infty</tex>
<tex>rhs(s_{goal}t) = 0</tex> U.Insert(<tex>s_{goal}t</tex>; CalcKey(<tex>s_{goal}t</tex>));
'''UpdateVertex'''(u):
if (<tex>u \ne s_{goal}t</tex>)
rhs(u) = <tex>\min\limits_{s' \in Succ(u)}(c(u,s')+g(s'));</tex>
if (<tex>u \in U</tex>)
'''ComputeShortestPath'''():
while (U.TopKey() < CalcKey(<tex>s_{start}f</tex>) OR <tex>rhs(s_{start}f) \ne g(s_{start}f)</tex>)
<tex>K_{old} = U.TopKey()</tex>;
u = U.Pop();
'''Main'''():
<tex>s_{last} = s_{start}f</tex>
'''Initialize'''();
'''ComputeShortestPath'''();
while (<tex>s_{start} f \ne s_{goal}t</tex>) // if (<tex>g(s_{start}f) = \infty</tex>) тогда путь на данной итерации не найден. <tex>s_{start}f</tex> = такая вершина s', что <tex>\min\limits_{s' \in Succ(s_{start}f)}(c(s_{start}f, s') + g(s'))</tex> Передвинулись вдоль найденного пути и изменили вершину <tex>s_{start}f</tex>;
Сканируем роботом какие-либо изменения в графе или убеждаемся, что граф остается прежним.
if (граф изменился)
<tex>K_m = K_m + h(s_{last}, h_{start})</tex>;
<tex>s_{last} = s_{start}f</tex>;
for всех ориентированных ребер <tex>(u; v)</tex> с измененными весами:
Обновляем результат функции <tex>c(u; v)</tex>;
{| class="wikitable"
|-
| style="width:50%;text-align:center;" | [[Файл:Схема_движения_робота_Dstarv2_1.png|350px400px]] || style="width:50%;text-align:center;" | [[Файл:Схема_движения_робота_Dstarv2_2.png|350px400px]]
|-
| style="width:50%;text-align:center;" | Итерации в функции '''ComputeShortestPath''' на исходном графе. || style="width:50%;text-align:center;" | Итерации в функции '''ComputeShortestPath''' после изменения графа. (Второй вызов функции)
