3.3.3 — как реальные системы адаптируют базовые алгоритмы под масштаб3.3.3 — how real systems adapt the base algorithms to scale
Последняя карточка раздела — не новые фундаментальные алгоритмы, а витрина того, как Дейкстра из 3.2.1 масштабируется до навигатора всей страны (A*, Contraction Hierarchies), и как сама идея "графа" применяется там, где рёбра — не физическая связь, а отношение (кто на кого ссылается) — PageRank и HITS.This section's final card isn't new foundational algorithms, but a showcase of how Dijkstra from 3.2.1 scales up to a country-wide navigation app (A*, Contraction Hierarchies), and how the idea of a "graph" itself applies where an edge isn't a physical connection but a relationship (who links to whom) — PageRank and HITS.
Дейкстра из 3.2.1 не знает, где находится цель — он одинаково добросовестно исследует все направления от старта. A* использует дополнительную информацию — эвристическую функцию h(v), оценивающую (не обязательно точно) оставшееся расстояние от v до цели, — и на каждом шаге выбирает вершину с минимальным f(v) = g(v) + h(v), где g(v) — уже пройденное расстояние (то, чем оперирует Дейкстра), а h(v) — оценка оставшегося пути. Если h — допустимая эвристика (никогда не переоценивает реальное расстояние — например, для карты это прямая линия "по воздуху", которая физически не может быть длиннее пути по дорогам), A* гарантированно находит кратчайший путь, но исследует значительно меньше вершин, чем Дейкстра, потому что явно "смотрит" в сторону цели, а не во все стороны равномерно.Dijkstra from 3.2.1 doesn't know where the goal is — it explores all directions from the start equally diligently. A* uses extra information — a heuristic function h(v) estimating (not necessarily exactly) the remaining distance from v to the goal — and at each step picks the vertex with minimum f(v) = g(v) + h(v), where g(v) is the distance traveled so far (what Dijkstra works with) and h(v) is the estimated remaining distance. If h is an admissible heuristic (never overestimates the real distance — for a map, that's the straight-line "as the crow flies" distance, which can never physically exceed the road distance), A* is guaranteed to find the shortest path, but explores far fewer vertices than Dijkstra, since it explicitly "looks toward" the goal instead of spreading out evenly in all directions.
область исследованных вершин: круг у Дейкстры против узкого "луча" у A*, направленного на Tthe region of explored vertices: a circle for Dijkstra vs. a narrow "beam" for A* aimed at T
A* всё ещё слишком медленный для запроса "кратчайший путь" на графе всей дорожной сети страны в реальном времени (десятки миллионов вершин). Contraction Hierarchies решает это предвычислением: офлайн, один раз, "сжимает" вершины в порядке важности (второстепенный перекрёсток — рано, крупная трасса — поздно), для каждой сжимаемой вершины добавляя "шорткат"-рёбра между её соседями, если удаляемая вершина была на единственном кратчайшем пути между ними — сохраняя корректность расстояний. В рантайме поиск идёт одновременно от старта и от цели только по рёбрам "вверх" по иерархии важности, встречаясь где-то в середине — на реальных дорожных сетях это ускоряет запрос в тысячи раз по сравнению с обычным Дейкстрой/A*.A* is still too slow for a "shortest path" query on a country's entire road-network graph in real time (tens of millions of vertices). Contraction Hierarchies solves this via precomputation: offline, once, it "contracts" vertices in order of importance (a minor intersection early, a major highway late), adding "shortcut" edges between a contracted vertex's neighbors whenever the removed vertex sat on the unique shortest path between them — preserving distance correctness. At query time, a search runs simultaneously from the start and the goal, only along edges going "up" the importance hierarchy, meeting somewhere in the middle — on real road networks this speeds up queries by a thousandfold compared to plain Dijkstra/A*.
Здесь граф перестаёт быть физической сетью и становится моделью отношения "кто на кого ссылается" (веб-граф из 3.1.1). PageRank формализует интуицию "страница важна, если на неё ссылаются важные страницы" рекурсивно: ранг страницы — это сумма рангов ссылающихся на неё страниц, поделённых на число исходящих ссылок каждой из них (авторитет "передаётся" по ссылке и делится поровну между всеми исходящими ссылками источника), плюс небольшой коэффициент случайного перехода (damping factor, обычно 0.85) — гарантирующий, что процесс не застрянет и не выродится в вершинах-тупиках. Вычисляется как собственный вектор для наибольшего собственного значения соответствующей матрицы переходов — на практике находится итеративно (степенной метод), сходясь за десятки итераций.Here the graph stops being a physical network and becomes a model of the "who links to whom" relationship (the web graph from 3.1.1). PageRank formalizes the intuition "a page is important if important pages link to it" recursively: a page's rank is the sum of the ranks of pages linking to it, each divided by that source page's number of outgoing links (authority "flows" along a link and splits evenly among all of the source's outgoing links), plus a small random-jump term (the damping factor, typically 0.85) that guarantees the process doesn't get stuck or degenerate at dead-end vertices. It's computed as the eigenvector for the largest eigenvalue of the corresponding transition matrix — in practice found iteratively (the power method), converging within a few dozen iterations.
HITS (Hyperlink-Induced Topic Search) идёт дальше, разделяя авторитетность на две отдельные роли: hub (страница, ценная тем, что хорошо указывает на авторитетные страницы — например, подборка ссылок) и authority (страница, ценная тем, что на неё ссылается много хороших hub'ов) — они определяются взаимно рекурсивно (хороший hub указывает на хорошие authority, хорошая authority получает ссылки от хороших hub) и вычисляются на подграфе, отобранном под конкретный поисковый запрос, а не на всём вебе разом, как PageRank.HITS (Hyperlink-Induced Topic Search) goes further, splitting authority into two separate roles: a hub (a page valuable for pointing well to authoritative pages — say, a curated link list) and an authority (a page valuable for being linked to by many good hubs) — these are defined mutually recursively (a good hub points to good authorities, a good authority is linked from good hubs) and are computed on a subgraph selected for a specific search query, rather than on the whole web at once like PageRank.
Практически каждая стратегия и RPG с перемещением юнитов по карте использует A* с эвклидовой или манхэттенской дистанцией как эвристику — стандарт индустрии, преподаваемый именно в контексте игровой разработки, а не только теории графов.Nearly every strategy game and RPG with units moving across a map uses A* with Euclidean or Manhattan distance as the heuristic — an industry standard, taught specifically in the context of game development, not just graph theory.
Открытые навигационные движки на основе OpenStreetMap используют именно Contraction Hierarchies (или их развития) для ответа на запрос маршрута за миллисекунды на графе всей планеты — без такого предвычисления запрос был бы непригоден для интерактивного использования.Open-source navigation engines built on OpenStreetMap use exactly Contraction Hierarchies (or their descendants) to answer a route query in milliseconds on a graph of the entire planet — without such precomputation, a query would be unusable interactively.
Название говорит само за себя — это тот самый алгоритм из основополагающей статьи Ларри Пейджа и Сергея Брина (1998), который лёг в основу Google Search и остаётся частью (сильно расширенной) ранжирующей системы по сей день.The name says it all — this is the exact algorithm from Larry Page and Sergey Brin's foundational 1998 paper, which underpinned Google Search and remains part of its (heavily extended) ranking system to this day.
"Кто наиболее влиятелен в этой сети" (для рекомендаций, для приоритизации модерации) и "какие аккаунты подозрительно много ссылаются друг на друга кольцом" (для антифрода) — оба используют варианты PageRank за пределами исходной задачи ранжирования веб-страниц."Who's most influential in this network" (for recommendations, for moderation prioritization) and "which accounts suspiciously link to each other in a ring" (for anti-fraud) — both use PageRank variants outside its original web-page-ranking task.
Разделение на hub/authority исторически применялось в поисковике Teoma, а сегодня используется в анализе графов научного цитирования — "обзорная статья с хорошими ссылками" (hub) и "часто цитируемая оригинальная работа" (authority) — разные, но взаимоусиливающие роли в этом графе.The hub/authority split was historically used in the Teoma search engine and is used today in citation-network analysis — "a well-referenced survey paper" (a hub) and "a frequently cited original work" (an authority) are distinct but mutually reinforcing roles in that graph.
Если h(v) хотя бы иногда переоценивает реальное оставшееся расстояние, A* может закрыть (settle) вершину слишком рано, до того как найден настоящий кратчайший путь через неё — результат перестаёт быть гарантированно оптимальным, хотя алгоритм по-прежнему успешно завершается и возвращает какой-то путь, что маскирует проблему.If h(v) ever overestimates the true remaining distance, A* can settle a vertex too early, before the actual shortest path through it is found — the result stops being guaranteed optimal, even though the algorithm still completes successfully and returns some path, which masks the problem.
Иерархия важности вершин и все шорткаты предвычисляются офлайн для конкретного снимка графа — закрытие дороги или пробка в реальном времени не отражаются в предвычисленной структуре без дорогого частичного пересчёта, что требует отдельного слоя "живых" поправок поверх статичной иерархии в реальных навигаторах.The vertex-importance hierarchy and all shortcuts are precomputed offline for one snapshot of the graph — a real-time road closure or traffic jam isn't reflected in the precomputed structure without an expensive partial recomputation, requiring a separate layer of "live" adjustments on top of the static hierarchy in real navigation apps.
Страница без исходящих ссылок ("dangling node") или группа страниц, ссылающихся только друг на друга, без damping factor превращаются в "ловушку", накапливающую весь ранг и не отдающую его дальше — коэффициент случайного перехода (обычно 0.85) существует именно для того, чтобы гарантировать сходимость степенного метода на любом реальном графе, а не только на "хорошо себя ведущих".A page with no outgoing links (a "dangling node"), or a group of pages linking only to each other, without a damping factor turns into a "trap" that accumulates all the rank and never passes it along — the random-jump coefficient (typically 0.85) exists precisely to guarantee the power method converges on any real graph, not just "well-behaved" ones.