Информатика • 9 класс
161

Поиск оптимального пути

  • Оптимальный путь — это путь с самой минимальной суммой рёбер между двумя точками (вершинами) на графе.
  • Оптимальный путь получил применение в GPS-навигаторах. В качестве вершин выступают перекрёстки, а дороги являются рёбрами, которые лежат между ними.

 

  • Пример. Найдём с помощью графа кратчайший путь из пункта А в пункт В.

    Решение. Необходимо построить весовую матрицу и с её помощью дерево перебора.

    Ответ. Кратчайший путь — ADEB с весом 3.

Было полезно?

Рекомендуем

Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках
Зарегистрироваться в «Облаке знаний»