РусҚаз

Графы вокруг нас

Информатика · 10 класс · Графы и поиск пути · Урок 4 из 4

Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Что это

Открой навигатор в телефоне — внутри него весь город хранится как граф: перекрёстки — вершины, улицы — рёбра, а вес — время в пути с учётом пробок. Графы вокруг нас повсюду: в интернете, в соцсетях, в поисковиках и даже в ИИ-ассистентах.

Велосипедист остановился на перекрёстке большого города и смотрит на карту с маршрутом в телефоне, закреплённом на руле.

Зачем это нужно

Маршрутизаторы интернета считают кратчайшие пути для пакетов данных, соцсети предлагают друзей друзей, а языковые модели подключают к графам знаний, чтобы ИИ опирался на проверенные связи между фактами. Беспилотники, роботы доставки и энергосети тоже думают графами. Чем больше работы берёт на себя ИИ, тем важнее человек, который понимает, какую задачу решает алгоритм, выбирает подходящий и проверяет, не обманывает ли результат. Умение увидеть граф в жизни и выбрать к нему правильный инструмент — это навык проектировщика, а не исполнителя.

Специалист в серверном зале с рядами мигающих стоек проверяет на планшете схему соединений сети.

Как это работает

Друзья друзей, которые ещё не ваши друзья, — это вершины на расстоянии два от вас, и находит их обычный обход в ширину. Поисковики оценивали важность страниц по простой идее: страница важна, если на неё ссылаются важные страницы. Граф знаний связывает факты, например «Мария Кюри — получила — Нобелевскую премию». А алгоритм выбирают по задаче: обход в ширину — когда важно число пересадок, алгоритм Дейкстры — когда важны время или цена.

Пассажирка на вокзале рассматривает табло пересадок и выбирает между быстрым поездом с пересадкой и медленным прямым.

Немного истории

Идею оценки страниц по ссылкам назвали ПейджРанк. Её придумали аспиранты Стэнфордского университета Ларри Пейдж и Сергей Брин, когда искали способ навести порядок в стремительно растущем интернете. Из этого студенческого проекта вырос поисковик Гугл, и вся его ранняя сила держалась на одной мысли о графе ссылок.

Два молодых аспиранта в тесной университетской комнате, заставленной компьютерами и коробками, обсуждают что-то у монитора.

Что будем делать на практике

А теперь давай попробуем выполнить практическое задание. Сейчас на экране начало твоего графа: четыре вершины от A до D и три ребра с весами, старт в A, финиш в D, включён режим «строить». Дострой граф хотя бы до шести вершин и семи рёбер и подбери веса так, чтобы маршрут Дейкстры от старта до финиша содержал больше рёбер, чем путь обхода в ширину. Подумай, как сделать короткую по числу рёбер дорогу очень дорогой, а длинный обход — дешёвым. Потом запусти оба алгоритма и сравни маршруты. Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай.

Задание в опыте

Постройте свой граф: не меньше 6 вершин и 7 рёбер. Подберите веса так, чтобы маршрут Дейкстры от старта до финиша содержал больше рёбер, чем путь BFS, и запустите оба алгоритма.
Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Уроки темы: Графы и поиск пути

  1. Что такое граф
  2. Обход в ширину
  3. Алгоритм Дейкстры
  4. Графы вокруг нас