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

Количество путей. Поиск оптимального пути

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

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

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

Изображение 1
Было полезно?

Рекомендуем

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