Пошук шляху

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

Двома основними задачами пошуку шляху є:

1. пошук шляху між двома вузлами на графі;
2. задача про найкоротший шлях — знайти оптимальний найкоротший шлях.

Основні алгоритми, такі як пошук у ширину і пошук у глибину, спрямовані на першу проблему, вичерпуючи всі можливості за допомогою грубого перебору; починаючи з даного вузла, вони ітераційно досліджують усі потенційні шляхи, доки не досягають цільового вузла. Ці алгоритми використовуються за час ${\displaystyle O\left(\left|V\right|+\left|E\right|\right)}$ або лінійний час, де V — кількість вершин, а E — кількість ребер між вершинами.

Більш складною проблемою є пошук оптимального шляху. Вичерпний підхід у даному випадку відомий як алгоритм Беллмана-Форда має часову складність ${\displaystyle O(|V||E|)}$, або квадратичний час. Однак не потрібно вивчати всі можливі шляхи, щоб знайти оптимальний. Алгоритми, такі як алгоритм A* та алгоритм Дейкстри стратегічно виключають шляхи, як за допомогою евристичного алгоритму, так і за допомогою динамічного програмування. Усунувши неможливі шляхи, ці алгоритми можуть досягати низької складності часу, як ${\displaystyle O(|E|\log(|V|))}$.[1]

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

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

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

  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

  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

Кріс Крофорд в 1982 році описав, як він «витратив багато часу», намагаючись вирішити проблему з пошуком шляхів у Tanktics (комп'ютерна гра), в якій комп'ютерні танки потрапили в пастку на суші в U-образних озерах. «Після довгих витрачених зусиль я виявив краще рішення: видалити U-образні озера з карти», сказав він.[5]

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

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

• Планування руху
• Планування шляху з довільними кутами

• 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 * алгоритми воронки.