The shortest way: Dakestra and A*

Содержание и основные понятия

Back to the table of contents
Alterna · Chapter 19 · page 19.3
The shortest way: Dakestra and A*
The Dakestra and A* algorithm with euristics, step-by-step visualization on the graph.
Dakestra
Finds the shortest path from one summit to all others.
A*
=Daxtra + Heuristics, both used in navigators, games and network router.
GEF
PIF
EEG No. 1, No. 3
01
Dakestra algorithm
Algoritm
All tops.
dist[v] = ∞
other than start:
dist[start] = 0
.
Remove top u c
minimum dist
.
For neighbor v: if
dist[u] + w(u,v) < dist[v]
, update.
Repeat until the line is empty.
Complexity
O((V+E)·log V)
Priority.
02
A* - Dakestra + Heuristics
A* uses
f(v) = g(v) + h(v)
:
g(v)
is the real route from start to v.
h(v)
- Heuristics (estimate v-to-target).
Three heuristics, each responsible for:
Manhattan
|dx| + |dy|
It works when you can only move on the axles (without diagonals).
An example: a robot in a warehouse, a pedestrian around the block.
Euclidova
√(dx²+dy²)
For free movement in any direction.
Example: drone in the air, ship in the sea.
Fuck you!
max(|dx|,|dy|)
When you can move on diagonals (the chess king).
Example: A character in an 8-track game.
Allowable Heuristics
If h(v) ≤ the real distance, A* finds the optimal path.
03
Calculation of the routes to the DAG
A task like EEG #3 is a randomized generator.
🎲
DAG: calculation of routes
Press "New Task"
Response:
04
A* grid
Network 20×20 · Random start/finish · obstacles
🎯
A* Visualizer: 20×20
Euristics
Legend
Start (S)
Objective (G)
Open
Clossed
Wall
Path
XP: 0
To practike
Graphic algorithms (Dakestra, A*) are processed in
Workshop
and in
Chapter 24 (DAG)
.