Алгоритм D
Алгоритм D*— алгоритм пошуку найкоротшого шляху у зваженому орієнтованому графі, де структура графа невідома заздалегідь чи постійно змінюється. Розроблено Свеном Кенігом та Максимом Лихачовим у 2002 році.
Зміст
Алгоритм LPA* [ред.]
Постановка завдання [ред.]
Дано зважений орієнтований граф [math] G(V, E) [/math] . Дані вершини: стартова вершина [math] f [/ math] і кінцева вершина [ math] t [/ math]. Потрібно після кожної зміни графа [math]G[/math] вміти обчислювати функцію [math]g(s)[/math] для кожної відомої вершини [math]s \in V[/math]
Опис [ред.]
Функція [math]g(s)[/math] повертатиме найменшу вартість шляху з вершини [math]f[/math] до [math]s[/math] . Її значення для алгоритму буде майже аналогічним значенню в алгоритмі A *, за винятком того, що в даному алгоритмі цікавлять наc тільки [math]g(s)[/math] -значення відомих вершин на даній ітерації.
Підтримуватимемо для кожної вершини два види суміжних з нею вершин:
- Позначимо безліч [math]Succ(s) \subseteq V[/math] як безліч вершин, що виходять з вершини [math]s[/math].
- Позначимо безліч [math]Pred(s) \subseteq V[/math] як безліч вершин, що входять до вершини [math]s[/math] .
Функція [math]0 \leqslant c(s, s') \leqslant +\infty[/math] повертатиме вартість ребра [math](s, s')[/math] . У цьому [math]c(s, s') = +\infty[/math] буде і тоді, коли ребра [math](s, s')[/math] немає.
| Визначення: |
| Будемо називатиrhs-значенням(англ.right-hand s &[[math]rhs(s)[/math] , яка повертатиме потенційну мінімальну відстань від[math]f[/math] до [math]s[/math] за такими правилами: |
Так як rhs-значення використовує мінімальне значення з мінімальних відстаней від [math]f[/math] до вершин, що входять до цієї вершини [math]s[/math] , це буде нам давати інформацію про оцінну відстань від [math]f[ /math] до [math]s[/math] .
| Визначення: |
| Вершина [math]s[/math] називаєтьсянасиченою(англ.locally consistent), якщо [math]g(s) = rhs(s)[/math] |
| Визначення: |
| Вершина [math]s[/math] називаєтьсяпереповненою(англ.locally overconsistent), якщо [math]g(s) \gt rhs(s)[/math] |
| Визначення: |
| Вершина [math]s[/math] називаєтьсяненасиченою(англ.locally underconsistent), якщо [math]g(s) \lt rhs(s)[/math] |
Очевидно, якщо всі вершини насичені, ми можемо знайти відстань від стартової вершини до будь-якої. Такий граф називатимемо стійким (насиченим).
Евристична функція [math]h(s,s')[/math] тепер має бути неотрицательна і виконувати нерівність трикутника, тобто. [math]h(t,t) = 0[/math] і [math]h(s, t) \leqslant c(s,s') + h(s',t)[/math] для всіх [math ]s \in V[/math] і [math]s' \in Succ(s)[/math]
| Визначення: |
Будемо називатиключомвершини таку функцію [math]key(s)[/math] , яка повертає вектор із двох значень [math]k_1(s)[/math] , [math]k_2(s )[/math] .
|
Якщо вНаприкінці пошуку шляху [math]g(t) = +\infty[/math] , ми не змогли знайти шлях від [math]f[/math] до [math]t[/math] на поточної ітерації. Але після наступної зміни графа шлях цілком може знайтись.
Псевдокод [ред.]
Основна функція, що описує алгоритм
Функція ініціалізації вихідного графа встановлює всім вершин крім стартової вершини [math]f[/math] значення [math]g(s)[/math] і [math]rhs(s)[/math] рівними нескінченності. Для стартової [math] rhs (f) = 0 [/ math] . Очевидно, що мінімальна відстань від стартової вершини до самої себе має дорівнювати 0, але [math]g(f)=+\infty[/math] . Це зроблено для того, щоб стартова вершина була ненасиченою та мала право потрапити у пріоритетну чергу.
Функція [math]key(s)[/math] . Значення, що повертаються, сортуються в лексографічному порядку, тобто спочатку сортується по [math]k_1(s)[/math] , потім по [math]k_2(s)[/math]
Оновлює дані вершини у відповідність до даних вище визначеннями. Також підтримує інваріант того, що у черзі U лежать лише ненасичені вершини.
Функція кілька разів перераховує значення [math]g(s)[/math] у ненасичених вершин у порядку їх ключів. Такий перерахунок значення [math]g(s)[/math] називатимеморозширеннямвершини.
Асимптотика [ред.]
| Теорема (Про монотонність зміни ключів): |
| Доказ: |
| [math]\triangleright[/math] |
| Доказ [1] |
| [math]\triangleleft[/math] |
| Теорема (Про необоротну насиченість): |
| Доказ: |
| [math]\triangleright[/math] |
| Доведення[2] |
| [math]\triangleleft[/math] |
| Теорема: |
| Доказ: |
| [math]\triangleright[/math] |
| Доказ [3] |
| [math]\triangleleft[/math] |
Таким чином, ми описали алгоритм LPA*. Він обчислює довжину найкоротшого шляху між вершинами [math]f[/math] та [math]t[/math], використовуючи при цьому дані з попередніх ітерацій. Очевидно, що у гіршому випадку (а саме коли всі ребра навколо поточної вершини змінили свою вагу) алгоритм працюватиме як послідовні виклики алгоритму А* за [math]O(n \cdot m \cdot \log(n))[/math] . Покращимо цю оцінку за допомогою алгоритму D * lite.
Примітка: практично ж такий підхід теж має місце на щільних графах (чи матрицях), оскільки у середньому оцінює [math]O(n \cdot \log(n))[/math] .
Алгоритм D* (Перша версія) [ред.]
Поки що було описано лише алгоритм LPA*. Він знаходить найкоротшу відстань між початковою і кінцевою вершинами за будь-якої зміни даного графа. Його початковий пошук повністю збігається з алгоритмом A*, але наступні ітерації можуть використовувати інформацію з попередніх пошуків.
Постановка завдання [ред.]
Дано зважений орієнтований граф [math] G(V, E) [/math] . Дано вершини [math]f[/math] і [math]t[/math]. Потрібно в процесі руху найкоротшим шляхом у графі [math]G[/math] оновлювати значення функції [math]g(s)[/math] при надходженні нової інформації про графу [math]G[/math] .
Тепер на основі LPA* опишемо алгоритм D*, який здатний визначати відстань між поточною вершиною [math]f[/math] , в якій, скажімо, знаходиться здатний до сканування місцевості "робот", ікінцевою вершиною [math]t[/math] при кожній зміні графа в той час, як наш "робот" рухається вздовж знайденого шляху.
Опис [ред.]
Опишемо першу версію алгоритму D*. Так як при русі найкоротшим шляхом шлях може тільки скорочуватися і відбувається зміна тільки стартової вершини, то можна застосувати ідею з алгоритму LPA *.
Примітка: Більшість функцій переходять у даний алгоритм без змін, тому опишемо лише змінені частини.
Для початку ми змінимо напрямок пошуку у графі.
Тепер функція g(s) зберігає мінімальну відому відстань від [math]t[/math] до [math]s[/math] . Властивості залишаються незмінними.
Евристична функція [math]h(s,s')[/math] тепер має бути неотрицательная і обратно-устойчивая, тобто. [math]h(f,f) = 0[/math] і [math]h(f, s) \leqslant h(f,s') + c(s',s)[/math] для всіх [math ]s \in S[/math] і [math]s' \in Pred(s)[/math] . Вочевидь, що з русі робота [math]f[/math] змінюється, тому дані властивості повинні виконуватися всім [math]f \in V[/math] .
Додаткова умова виходу змінюється, тобто. при [math]g(f) = +\infty[/math] шлях не знайдено на даній ітерації. Інакше шлях знайдено і "робот" може пройти ним.
Примітка: Так само слід зазначити, що функціяInitializeне повинна ініціалізувати всі вершини перед стартом алгоритму. Це важливо, тому що на практиці число вершин може бути величезним, і лише деякі будуть пройдені роботом у процесі руху. Також це дає можливість додавання/видалення ребер без втрати стійкості всіх підграф даного графа.
Псевдокод [ред.]
При такій постановці завдання псевдокод не сильно змінюється, але функціяMainвсе-таки зазнає значнихзміни.
Асимптотика [ред.]
| Теорема (Свен Кеніг, Про стійку насиченість вершин): |
| Доказ: |
| [math]\triangleright[/math] |
| Доказ [4] |
| [math]\triangleleft[/math] |
Алгоритм D* (Друга версія) [ред.]
Опис [ред.]
У першій версії алгоритму була серйозна проблема в тому, що для кожної вершини в пріоритетній черзі потрібно було оновлювати ключ сумарно за [math] O (n \ cdot \ log (n)) [/ math]. Це дорога операція, оскільки черга може містити величезну кількість вершин. Скористаємося оригінальним методом пошуку та змінимо основний цикл, щоб уникнути постійного перестроювання черги [math]U[/math].
Тепер евристична функція повинна підтримувати нерівність трикутника всім вершин [math]s,s',s'' in V[/math] , тобто. [math]h(s,s'') \leqslant h(s,s') + h(s',s'')[/math] . Також має виконуватися властивість [math]h(s,s') \leqslant c^*(s,s')[/math] , де [math]c^*(s,s')[/math] - вартість переходу найкоротшим шляхом з [math]s[/math] в [math]s'[/math] , при цьому [math]s[/math] і [math]s'[/math] не повинні бути обов'язково суміжними. Такі властивості не суперечать властивостями першої версії, а лише посилюють їх.
Припустимо, що після того, як робот просунеться вздовж знайденого шляху на попередніх ітераціях, з вершини [math]s[/math] до [math]s'[/math], він виявить зміни у графі. Перший компонент ключів [math]k_1(s')[/math] може зменшитися максимум на [math]h(s,s')[/math] (за визначенням ключа). Другий компонент не залежить від функції h. Аналогічно першій версії алгоритму, ми повинні зменшити першу компоненту ключа у всіх вершин у черзі U. Очевидно, що[math]h(s,s')[/math] буде однаковим для всіх вершин з U. Порядок у черзі не зміниться, якщо зробити зменшення. Отже, зменшення можна відкласти, тим самим чергу не доведеться перебудовувати на кожній ітерації. Також виходячи з нового визначення функції [math]h[/math] , її значення буде завжди менше, ніж різницю перших компонент ключів у сусідніх за пріоритетом вершин. Таким чином, ми можемо додавати h(s,s') до всіх [math]k_1(s')[/math] у ключів вершин з U.
Будемо називати [math]K_m[/math] ключовим модифікатором. У ньому ми і будемо зберігати суму [math]h(s,s')[/math] , які потрібно додати до всіх вершин з U.
Псевдокод [ред.]
Асимптотика [ред.]
За допомогою введення ключового модифікатора [math]K_m[/math] та відкладеного оновлення ключів вершин вдалося прибрати з ітерації алгоритму [math]O(n \cdot \log(n))[/math] операцій, що витрачалися на оновлення черги [math] ]U[/math] . Очевидно, що на основі теорем, наведених вище, алгоритм використовував [math]O(2 \cdot n \cdot \log(n))[/math] операцій. Отже, нам вдалося зменшити константу вдвічі, що дає істотне зростання продуктивності на практичних завданнях.