Что это
Открой навигатор в телефоне — внутри него весь город хранится как граф: перекрёстки — вершины, улицы — рёбра, а вес — время в пути с учётом пробок. Графы вокруг нас повсюду: в интернете, в соцсетях, в поисковиках и даже в ИИ-ассистентах.
Зачем это нужно
Маршрутизаторы интернета считают кратчайшие пути для пакетов данных, соцсети предлагают друзей друзей, а языковые модели подключают к графам знаний, чтобы ИИ опирался на проверенные связи между фактами. Беспилотники, роботы доставки и энергосети тоже думают графами. Чем больше работы берёт на себя ИИ, тем важнее человек, который понимает, какую задачу решает алгоритм, выбирает подходящий и проверяет, не обманывает ли результат. Умение увидеть граф в жизни и выбрать к нему правильный инструмент — это навык проектировщика, а не исполнителя.
Как это работает
Друзья друзей, которые ещё не ваши друзья, — это вершины на расстоянии два от вас, и находит их обычный обход в ширину. Поисковики оценивали важность страниц по простой идее: страница важна, если на неё ссылаются важные страницы. Граф знаний связывает факты, например «Мария Кюри — получила — Нобелевскую премию». А алгоритм выбирают по задаче: обход в ширину — когда важно число пересадок, алгоритм Дейкстры — когда важны время или цена.
Немного истории
Идею оценки страниц по ссылкам назвали ПейджРанк. Её придумали аспиранты Стэнфордского университета Ларри Пейдж и Сергей Брин, когда искали способ навести порядок в стремительно растущем интернете. Из этого студенческого проекта вырос поисковик Гугл, и вся его ранняя сила держалась на одной мысли о графе ссылок.
Что будем делать на практике
А теперь давай попробуем выполнить практическое задание. Сейчас на экране начало твоего графа: четыре вершины от A до D и три ребра с весами, старт в A, финиш в D, включён режим «строить». Дострой граф хотя бы до шести вершин и семи рёбер и подбери веса так, чтобы маршрут Дейкстры от старта до финиша содержал больше рёбер, чем путь обхода в ширину. Подумай, как сделать короткую по числу рёбер дорогу очень дорогой, а длинный обход — дешёвым. Потом запусти оба алгоритма и сравни маршруты. Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай.