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

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

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

Алгоритми

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

Двома проблемами пошуку шляху є:

знахождення шляху між двома точками на графі;
обрання найкоротшого, найкращого шляху з них.

Основні алгоритми, такі як: пошук по широті та глибині звуртають свою увагу на першу проблему й використовують всі ресурси на її вирішення. Починаючи з певного вузла, ці алгоримти досліджують всі інші вузли й можливі шляхи доки не досягають необхідної точки.
Ці алгоритми виконуються в (О(|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

Спочатку, створіть список координат, який ми будемо використовувати як чергу. Черга буде ініціалізована

Now, map the counters onto the map, getting this:

  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

У відео іграх

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

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

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

Motion planning
Any-angle path planning

Список використаної літератури

Посилання

http://sourceforge.net/projects/argorha
http://qiao.github.com/PathFinding.js/visual/
StraightEdge Open Source Java 2D path finding (using A*) and lighting project. Includes applet demos.
python-pathfinding Open Source Python 2D path finding (using Dijkstra's Algorithm) and lighting project.
Daedalus Lib Open Source. Daedalus Lib manages fully dynamic triangulated 2D environment modeling and pathfinding through A* and funnel algorithms.