Информатика • 9 класс
91
Поиск оптимального пути
- Оптимальный путь — это путь с самой минимальной суммой рёбер между двумя точками (вершинами) на графе.
- Оптимальный путь получил применение в GPS-навигаторах. В качестве вершин выступают перекрёстки, а дороги являются рёбрами, которые лежат между ними.
- Пример. Найдём с помощью графа кратчайший путь из пункта А в пункт В.
Решение. Необходимо построить весовую матрицу и с её помощью дерево перебора.
Ответ. Кратчайший путь — ADEB с весом 3.
Было полезно?
Рекомендуем
Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках