Комп’ютерний науковець розширив можливості класичного алгоритму 1996 року, подолавши його давню межу. Новий підхід до задачі пошуку найкоротших шляхів у графах дає точніші наближені оцінки для близько розташованих вершин, не втрачаючи швидкодії, повідомляє SciTechDaily.
Що таке задача всіх найкоротших шляхів
Задача, відома як All-Pairs Shortest Paths (APSP), полягає в обчисленні найкороткої відстані між кожною парою вершин у мережі. Це не лише дорожні карти: графи описують комп’ютерні мережі, залізничні системи, взаємодію білків у клітині чи зв’язки між нейронами в мозку.
Точки в такій моделі називаються вершинами, а з’єднання між ними — ребрами. Коли кількість вершин зростає, обчислення стають дуже дорогими. Для щільних графів класичні точні методи потребують часу, що зростає приблизно кубічно з числом вершин: подвоєння їх кількості може дати до восьми разів більше роботи. Також стрімко зростає й обсяг результату: у графі з n вершинами є n² впорядкованих пар, для яких потрібно вказати відстані.
Через це дослідники активно шукають наближені алгоритми. Вони жертвують частиною точності, але працюють набагато швидше, гарантуючи, що отримана оцінка лежить у певних математичних межах від істинного значення.
Алгоритм DHZ і його сліпа зона
У 1996 році Дор (Dor), Гальперін (Halperin) і Цвік (Zwick) запропонували впливовий метод, який забезпечував так звану «2-апроксимацію» майже за оптимальний час. Це означає, що оцінка відстані ніколи не перевищувала б удвічі істинну найкоротшу відстань.
Якщо два пункти насправді розділені 10 кілометрами, алгоритм гарантував результат між 10 і 20 кілометрами. Щоб досягти цього, метод DHZ не розглядає всі можливі шляхи повністю, а вибирає відносно невелику підмножину вершин — «вибіркові вершини», які відіграють роль орієнтирів (landmarks). Відстані до інших точок оцінюються через ці орієнтири.
Такий підхід добре працює, коли вершини розташовані далеко одна від одної. На умовному маршруті між Нью-Йорком і Лос-Анджелесом велика ймовірність, що хоча б одна вибіркова вершина лежить близько до найкоротшого шляху. Обхід через такий орієнтир додає невелику «дітку» до маршруту, і оцінка лишається в межах обіцяного коефіцієнта два.
Проблеми виникають на коротких відстанях. Дві сусідні околиці в передмісті Лос-Анджелеса можуть бути з’єднані шляхом із двох ребер, але жодна з вершин на цьому шляху не буде поблизу вибіркового орієнтира. У такому разі обхід через далеку вибіркову вершину може дати шлях у п’ять ребер — більше ніж удвічі довший за справжній.
Отже, алгоритм DHZ був швидким і надійним для достатньо далеких пар вершин, але його гарантія гірше працювала для близько розташованих точок. Ця межа зберігалася майже 25 років.
Багатомасштабне вибіркове зразкування графа
Манодж Ґупта (Manoj Gupta), доцент Індійського технологічного інституту в Гандінагарі, представив новий підхід на 66-й щорічній конференції з теорії обчислень Foundations of Computer Science (FOCS 2025).
Замість однієї «пласкої» множини вибіркових вершин його алгоритм використовує кілька шарів зразків, розподілених по різних масштабах графа. Кожен шар відображає інший рівень структури мережі. Це збільшує ймовірність того, що для будь-якої пари вершин — навіть тих, що з’єднані коротким шляхом, — знайдеться зручна проміжна точка-орієнтир.
Завдяки такій багатомасштабній конструкції знижується поріг відстані, починаючи з якого діє гарантія 2-апроксимації. Практично це означає, що алгоритм може надійно оцінювати відстані між набагато ближчими вершинами, ніж раніше, зберігаючи принаймні ту саму загальну часову складність.
Допускається, що оцінка все ще може бути вдвічі більшою за істинну відстань. Новизна не в поліпшенні самого коефіцієнта двійки, а в значному розширенні множини пар вершин, для яких така гарантія взагалі забезпечується.
Значення для складних мереж і теорії графів
Великі графи лежать в основі інтернет-маршрутизації, транспортного планування, соціальних платформ, біологічних досліджень та систем штучного інтелекту, що аналізують зв’язки в даних. У багатьох випадках не потрібні абсолютно точні відстані: швидка та гарантовано наближена оцінка може бути ціннішою за ідеально точне, але надто повільне рішення.
Нинішній результат поки що є теоретичним досягненням, а не готовою заміною для комерційних навігаторів. Водночас посилені теоретичні межі часто прокладають шлях до майбутніх практичних алгоритмів, показуючи, як ефективніше добувати надійну інформацію з мереж з величезною кількістю з’єднань.
Прогрес у теорії графів зазвичай відбувається через невеликі поліпшення давно відомих обмежень. Продовження дії гарантії, що фактично з 1996 року залишалася майже незмінною, є помітним кроком до швидких і масштабованих обчислень відстаней у гігантських мережах, на яких тримається сучасна наука й технології.