This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | Next revision Both sides next revision | ||
courses:algorithms_building_and_analysis:lectures [2024/04/25 21:46] kalishenko |
courses:algorithms_building_and_analysis:lectures [2024/05/01 19:19] kalishenko |
||
---|---|---|---|
Line 39: | Line 39: | ||
==== Кратчайшие пути. A* и его расширения ==== | ==== Кратчайшие пути. A* и его расширения ==== | ||
- | - Напоминание о A* | + | - Напоминание об алгоритмах поиска пути: |
+ | - Поиск в ширину | ||
+ | - Дейкстра | ||
+ | - A*: | ||
+ | - Выбор направления пути Дейкстрой при 0-взвешивании рёбер оптимального пути | ||
+ | - Доказательство неизменности пути при перевзвешивании рёбер | ||
+ | - Ограничения А* | ||
- Эвристические функции | - Эвристические функции | ||
+ | |||
+ | ==== Кратчайшие пути. Расширения A* ==== | ||
- Алгоритм ALT | - Алгоритм ALT | ||
- Алгоритм REACH | - Алгоритм REACH |