Пошук шляху: відмінності між версіями

[неперевірена версія]

← Попереднє редагування Наступне редагування →

Вилучено вміст Додано вміст

Лінійно

Версія за 11:50, 2 грудня 2017

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

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

Алгоритми

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

Дві основні проблеми пошуку шляху:

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

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

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

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

Це незавершена стаття про алгоритми.
Ви можете допомогти проєкту, виправивши або дописавши її.

↑ http://lcm.csa.iisc.ernet.in/dsa/node162.html
↑ Delling, D.; Sanders, P.; Schultes, D.; Wagner, D. (2009). Engineering route planning algorithms. Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation. Springer. с. 117—139. doi:10.1007/978-3-642-02094-0_7.

[1] ttp://lcm.csa.iisc.ernet.in/dsa/node162.html

[2] Delling, D.; Sanders, P.; Schultes, D.; Wagner, D. (2009). Engineering route planning algorithms. Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation. Springer. с. 117—139. doi:10.1007/978-3-642-02094-0_7.

[1]

[2]

@@ Рядок 12: / Рядок 12: @@
 Більш складною проблемою є пошук оптимального шляху. Вичерпний підхід у даному випадку відомий як [[Алгоритм Беллмана—Форда|алгоритм Беллмана-Форда]], який дає складну часовість <math>O(|V||E|)</math>, або квадратичного часу. Однак не потрібно вивчати всі можливі шляхи, щоб знайти оптимальний. Алгоритми, такі як [[Алгоритм пошуку A*|алгоритм A*]] та [[Алгоритм Дейкстри|алгоритм Дейкстри]], стратегічно виключають шляхи, як за допомогою [[Евристичний алгоритм|евристичному алгоритму]], так і за допомогою [[Динамічне програмування|динамічного програмування]]. Усунувши неможливі шляхи, ці алгоритми можуть досягати складності часу такий же низький, як <math>O(|E|\log(|V|))</math>.<ref>http://lcm.csa.iisc.ernet.in/dsa/node162.html</ref>
+Наведені вище алгоритми є одними з найкращих загальних алгоритмів, які працюють на графу без попередньої обробки. Проте, в практичних системах маршрутизації шляхів, навіть кращі складності часу можна досягти за допомогою алгоритмів, які можуть попередньо обробляти граф для досягнення кращої продуктивності.<ref>{{cite book
+ | last1 = Delling | first1 = D.
+ | last2 = Sanders | first2 = P. | author2-link = Peter Sanders (computer scientist)
+ | last3 = Schultes | first3 = D.
+ | last4 = Wagner | first4 = D. | author4-link = Dorothea Wagner
+ | chapter = Engineering route planning algorithms
+ | doi = 10.1007/978-3-642-02094-0_7
+ | pages = 117–139
+ | publisher = Springer
+ | title= Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation
+ | year = 2009}}
+</ref> Одним з таких алгоритмів є {{Нп|Алгоритм скорочення ієрархій|алгоритм скорочення ієрархій||Contraction hierarchies}}.

Пошук шляху: відмінності між версіями

Версія за 11:50, 2 грудня 2017

Алгоритми

Навігаційне меню

Пошук