Содержание
- 2. Введение Алгоритм поиска пути на графе, начиная с некоторой стартовой вершины, исследует достижимые из нее узлы
- 3. Основные понятия Путем называется последовательность вершин в графе G = (V, Е), такая что каждое из
- 4. Дискретная модель На карту накладывается дискретная сетка Перемещение по карте - перемещение по клеткам сетки Математическая
- 5. Непрерывная модель Положение объектов на карте определяется их геометрической формой и взаимным расположением Вводится набор абстракций,
- 6. Обход препятствий Пока цель не достигнута Выбрать направление в сторону цели Если сделать шаг невозможно (встретили
- 7. Обход препятствий Простота реализации Учет взаимного расположения стартовой и финишной точки на карте Достоинства: Недостатки: При
- 8. Поиск в ширину Поиск в ширину — обход графа, который посещает все вершины, достижимые из данной
- 9. Поиск в ширину. Пример. На каждом шаге алгоритма происходит обработка 1 активной вершины Путь длины L+1
- 10. Поиск в глубину Поиск в глубину - обход графа, при этом на очередном шаге выбирается смежная
- 11. Поиск в глубину. Пример. На каждом шаге алгоритма происходит обработка 1 активной вершины Сударикова М.А. Филичев
- 12. Алгоритм Дейкстры Алгоритм Дейкстры находит все кратчайшие пути взвешенного графа с неотрицательными весами из исходной вершины
- 13. Алгоритм Дейкстры. Пример. стартовой вершине проставляется метка = 0, остальным = ∞ Сударикова М.А. Филичев Т.А.
- 14. Алгоритм Дейкстры. Пример. 13 стартовой вершине проставляется метка = 0, остальным = ∞ Обновляем метки в
- 15. Алгоритм Дейкстры. Пример. 13 стартовой вершине проставляется метка = 0, остальным = ∞ Обновляем метки в
- 16. Алгоритм Дейкстры. Пример. 13 стартовой вершине проставляется метка = 0, остальным = ∞ Обновляем метки в
- 17. Эвристические алгоритмы 14 Алгоритм «лучший - первый» Алгоритм использует знание о пространстве поиска; Работает как алгоритм
- 18. Алгоритм А* 15 Сортировка узлов по приближению наилучшего маршрута: f(n) = g(n) + h(n) f(n) -
- 19. Алгоритм А* 16 В компьютерных играх за счет приближения стоимости пути можно учесть дополнительные ограничения при
- 20. Эксперименты(1) 17 Сударикова М.А. Филичев Т.А. Поиск путей на графах. Обзор алгоритмов. 17 Поиск в ширину
- 21. Эксперименты(2) 18 Сударикова М.А. Филичев Т.А. Поиск путей на графах. Обзор алгоритмов. 18 Поиск в глубину
- 22. Эксперименты(3) 19 Сударикова М.А. Филичев Т.А. Поиск путей на графах. Обзор алгоритмов. 19 Алгоритм Дейкстры Серия
- 23. Эксперименты(4) 20 Сударикова М.А. Филичев Т.А. Поиск путей на графах. Обзор алгоритмов. 20 Сравнение алгоритмов Серия
- 24. Список литературы 21 Сударикова М.А. Филичев Т.А. Поиск путей на графах. Обзор алгоритмов. 21 1. Лекции
- 26. Скачать презентацию