Користувач:Marynakis/Пошук шляху (1)

Однакові шляхи між A та B в 2D середовищі

Пошук шляху - це побудова найкращого й найкоротшого шляху між двома точками (пунктами) за допомогою компьютерних програм. Ця система найбільш використовується при розвязуванні лабіринтів. Галузь пошуку шляхів базується на алгоритмі Дейкстри - алгоритмі пошуку шляхів на зваженому графі.

Пошук шляху тісно пов'язаний з проблемою найкоротшого шляху в теорії графів, яка вивчає, як обрати  шлях, за певними критеріям (довжина, ціна, швидкість та ін..) між двома точками у великій мережі.

Алгоритми

Взагалі, метод пошуку шляху досліджує граф починаючи з однієї вершини, а потім переходячи до сусідніх вузлів і так доки не досягне бажаної точпоки. Це відбувається з наміром знайти найдешевший маршрут (шлях).  Хоча методи пошуку по графу будуть знаходити шлях, на це знадобиться деякий час інші методи будуть знаходити цей шлях швидше.  Як аналогія  - людина, котра йде по кімнаті. Замість того щоб виявити та проаналізувати всі можливі шляхи, вона просто йде до цілі роблячи деякі відхилиння лише заради уникнення перешкод. Зазвичай ці відхилення є мінімальними. 

Двома проблемами пошуку шляху є: пошук шляху між твома точками; обрання оптимального з них. Основні алгоритми, такі як пошук по широті та глибині орінтовані на першу проблему і використовують всі ресурми для її розв'язання; починаючи з певного вузла вони досліджують всі можливі вузли і шляхи до необхідної точки. Ці алгоритми використовуються в О(|V|+|E|), або в лінійному часі, де V -кількість вершин, а Е - кількість ребер міє ними.

Більш складним завданням є пошук оптимального шляху. У цьому випадку використовується алгоритм Беллмана-Форда, який характеризується  часовою  складністю O(| V || E |), або квадратичним часом. Проте цей алгоритм не вивчає всі можливі шляхи для виявлення оптимального. Такі алгоритми як А*,  або алгоритм Дейкстри виключають непотрібні шляхи за допомогою динамічного програмування або евстрики. За допомогою усування непотрібних шляхів, ці агоритми можуть досягати такої ж низької часової складності , як і O (| E | log (| V |)).

Ці алгоритми є найкращими з тих які працюють на графіку без попередньої обробки. Проте, в системах маршруту проїзду, краща обчилювальна складність може бути досягнута за допомогою алгоритмів, які можуть попередньо обробляти графік заради досягнення кращої продуктивності. Одним з таких є алгоритм скорочення ієрархій.

Алгоритм Дейкстри 

Загальним прикладом алгоритму пошуку шляху базованого на графі є алгоритм Дейкстри. Цей алгоритм розпочинає роботу з початкового вузла й прямує до "відкритих вузлів" - кандидатів. На кожному наступному кроці обирається відкритий вузок з найменшою відстанню від початкового. Усі вузли, позначені як "закриті" та всі прилеглі до них вузли додаються до відкритого набору, якщо вони ще не були перевірені. Цей процес повторюється доки не буде знайдено шлях до потрібного вузла. Оскільки, цей алгоритм обирає наступні вузли з найменшою відстанню від початкового, то перший шлях який буде знайдено буде найкоротшим. 

Алгоритм Дейкстри не працює, якщо є показники від'ємної ваги. У гіпотетичній ситуації коли вузли А, В і С створюють зв'язаний неорієнтований граф до ребер  АВ = 3, АС = 4, та ВС =-2, оптимальний шлях від А до С коштує 1 та оптимальний шлях від А до В - 2. Алгоритм Дейкстри починає з А, а потім  спочатку розглядає  вузол B, оскільки він розташований найближче. Цей шлях буде коштувати  3  і буде позначеним, як "зактирий", а значить, його вартість ніколи не буде переоцінена. Тому алгоритм Дейкстри не може оцінити показники від'ємної ваги. Проте, оскільки в багатьох практичних цілях ніколи не буде від'ємних значень, то алгоритм Дейкстри підходить для пошуку шляхів. 

А* алгоритм

А* - це різновид алгоритму Дейкстри, який досить часто використовується в іграх. А* присвоює вагу кожному відкритому вузлу, вага якого дорівнює вазі ребра та додає приблизну відстань від ребра до фінішу. Ця приблизна відстань знайдена за допомогою евристики, та  являє собою мінімально можливу відстань між ребром та кінцем.  на відстань знайдена за допомогою евристичного алгоритму, та являє собою мінімально можливу відстань між ребром та кінцем. на відстань знайдена за допомогою евристики, та являє собою мінімально можливу відстань між ребром та кінцем. Це дозволяє алгоритму усунути довгі шляхи при виявленні первого. Це пряцює за наступним принципом: якщо між початком та кінцем є шлях, який дорівнює Х, а мінімальна відстань між вузлом та кінцем перевищує Х, то цей шлях не потрібно перевіряти далі. 

А* використовує цей евристичний метод для покращення поведінки алгоритму Дейкстри. Коли евристика дорівнює нулю, то А* є алгоритмом Дейкстри. Оскільки евристична оцінка збільшується і наближуеться до справжньої відстані, А* продовжує знаходити оптимальні шляхи, але працює швидше (за рахунок перевірки меншої кількості вузлів). Коли значення евристики дорівнює справжній відстані, А* досліджує найменші вузли. (Проте, взагалі не можливо написати евристичні програму, які б обчислювала правильну відстань.) Коли значення евристики зростає, А* досліджує менше вузлів, але більше не гарантує виявлення оптимального шляху. у багатьох програмах (таких як відео ігри) це прийнято і навіть бажано, аби тільки аолгоритм швидко працював. 

Алгоритм вибірки

Це досить простий та зрозумілий алгоритм пошуку шляху для мап на основі черепиці. Перед початком у вас є мапа, початкова координата та координата місця призначення. Карта буде виглядати так: Х - це стіни, S - це початок, O - фініш, _ - відкриті простори, цифри вздовж верхніх і правих країв це номери стоппців та рядків:  

1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X _ X _ _ X _ _ _ X 4
X _ _ _ X X _ X _ X 5
X _ X _ _ X _ X _ X 6
X _ X X _ _ _ X _ X 7
X _ _ O _ X _ _ _ X 8
X X X X X X X X X X

Спочатку, створіть  список координат, який ми будемо використовувати як чергу. Черга буде ініціалізована однією координатою, останньою координатою. Кожна координата також матиме змінний лічильник (мета цього скоро буде очевидною). таким чином, Черга починається з ((3,8,0)).

Потім перейдіть до кожного наступного елемента в черзі , включаючи елементи додані по ходу алгоритма, і для кожного з них виконайте наступне: 

1. Створіть список із чотирьох сусідніх комірок зі змінним лічильником напрямку елемент змінного лічильника +1 (у нашому прикладі мимаємо 4 комірки ((2,8,1),(3,7,1),(4,8,1),(3,9,1)))
   
2. Перевірте всі комірки у кожному списку за двома умовами:  а) якщо, комірка є стінкою - видаліть її; б) якщо в головному списку є елемент з такою з координатою та значення лічильника менше чи рівне - видаліть його зі списку комірок
3. Додайте всі інші комірки в кінець головного списку
4. Перейдіть до наступного елементу списку

Таким чином, після первого повороту, список елементів є таким: ((3,8,0),(2,8,1),(4,8,1))

• Після 2 поворотів : ((3,8,0),(2,8,1),(4,8,1),(1,8,2),(4,7,2))
• Після 3 поворотів: (...(1,7,3),(4,6,3),(5,7,3))
• Після 4 поворотів: (...(1,6,4),(3,6,4),(6,7,4))
• Після 5 поворотів: (...(1,5,5),(3,5,5),(6,6,5),(6,8,5))
• Після 6 поворотів: (...(1,4,6),(2,5,6),(3,4,6),(6,5,6),(7,8,6))
• Після 7 поворотів: ((1,3,7)) – проблема розв'язана, закінчіть цей етап алгоритму - зверніть вашу увагу, що якщо у вас є декілька одиниць, що переслідують одну й ту ж саму ціль (як і в багатьох іграх, то закінчення, щоб почати підхід алгоритму, призначено зробити це простіше), ви можете продовжувати, поки вся мапа не буде заповнена, досягнуті всі одиниці або досягнута ліміт на лічильнику. 

Тепер,  зіставте лічильники на мапі та отримайте наступне:

  1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X 6 X 6 _ X _ _ _ X 4
X 5 6 5 X X 6 X _ X 5
X 4 X 4 3 X 5 X _ X 6
X 3 X X 2 3 4 X _ X 7
X 2 1 0 1 X 5 6 _ X 8
X X X X X X X X X X

Теперь розпочніть з S (7), та перейдіть до найближчої клітинки з найменшим числом (не можна переходити в неперевірені клитинки). Ми отримуємо шлях (1,3,7) -> (1,4,6) -> (1,5,5) -> (1,6,4) -> (1,7,3) -> (1,8,2) -> (2,8,1) -> (3,8,0). В разі якщо два числа маюсть однакове найменше значення ( наприклад, якщо S знаходилося на (2,5)), то необхідно обрати випадковий напрямок -однакової довжини. Тепер алгоритм завершено.

Алгоритмі, які використовуються для пошуку шляхів

• А* алгоритм пошуку
• Алгоритм Дейкстри - особливий випадок в алгоритмі пошуку А*
• D*  - сімейство додаткових алгоритмів евристичного пошуку для проблем в яких існують певні обмеження, які змінюються з плином часу або є змінні, які повністю не відомі, коли середовище вперше планує шлях.
• Алгоритми будування шляху в будь-якому куточку середовища, це сімейство алгоритмів для планування шляху, які не обмежені рухом вздовж країв у пошуковому графі. Вони розроблені таким чином, для того, щоб  мати можливість обирати будь-яку точку і шукати найкоротший та прямий шлях. 
  

Багатоагентний пошук шляху

Багатоагентний пошук шляху - це пошук шляху для багатьох агентів з поточного місця до їх бажанього місця розташування, які не будут перетинатися один з одним, одночасно оптимізуючи функцію витрат, таку як сума довжини шляху всіх агентів. Це узагальнення пошуку шляху. Багато алгоритмів мультиагентного пошкуку шляхув генеровані з А*, або базуються на сокроченні до інших добре вивчених проблем, таких як спрямоване лінійне програмування.  Однак, такі алгоритми є неповними; іншими словами,  не доведено, що вони дають розв'язок протягом поліноміального часу. Інша категорія алгоритмів жертвує оптимальністю заради продуктивності за рахунок використання відомих навігаційних систем (таких як, потік трафіку) або топологією проблемного простору. 

Дивіться також 

• Планування руху

• Планування маршруту в будь-якій точці

Посилання

• http://sourceforge.net/projects/argorha
• http://qiao.github.com/PathFinding.js/visual/
• StraightEdge Відкриття вихідного Java 2D шляху пошуку (використовуючи A *) та проектування освітлення. Включає демонстрацію аплетів.
• python-pathfinding Відкритий вихідний шлях Python 2D (використовуючи алгоритм Дейкстри) та проект освітлення.
• Daedalus Lib Відкрите джерело. Daedalus Lib керує повністю динамічним триангульованим моделюванням 2D середовища та розробкою шляхів через алгоритм A * і послідовності.