Алгоритмы решения задачи построения маршрута из одной заданной точки в другую. Построение графа маршрута, его сравнение с неинформированным поиском. Алгоритм поиска в ширину, в глубину, с итерационным заглублением. Двунаправленный и информированный поиск.
Аннотация к работе
Изучение алгоритмов поискаВыполнить: 1) поиск в ширину; 2) затем, используя информацию о расстоянии до цели по прямой от каждого узла, выполнить поиск методом минимизации суммарной оценки Поиск в ширину - это простая стратегия, в которой в начале развертывается корневой узел, затем все преемники корневого узла, после этого развертываются преемники этих преемников и т.д. Сначала просматриваются вершины: Казань-(Москва, Уфа), затем вершины-потомки этих вершин: Москва-(Минск, Орел, Донецк, Санкт-Петербург, Нижний Новгород); Уфа-Самара; так как не найден целевой узел, поиск осуществляется дальше. На каждом шаге поиска в глубину алгоритм выбирает новую вершину, смежную с текущей и продолжает поиск уже из нее.