Вченим вдалося вирішити алгоритмічну загадку 50-х років

Главная » Маркетинг, Статті » Вченим вдалося вирішити алгоритмічну загадку 50-х років

Уже понад півстоліття дослідники всього світу б’ються над алгоритмічною проблемою, відомою як “проблема найкоротшого шляху з одного джерела”. Суть проблеми полягає в тому, як розробити математичне рішення, що дає змогу знайти найкоротший маршрут між вузлом і всіма іншими вузлами в мережі, де можуть бути зв’язки з негативними вагами.

Звучить складно? Можливо. Але насправді цей тип розрахунків уже використовується в широкому спектрі застосунків і технологій, від яких ми залежимо під час пошуку шляхів – наприклад, Google Maps веде нас ландшафтами і містами.

Тепер дослідникам з факультету комп’ютерних наук Копенгагенського університету вдалося розв’язати проблему найкоротшого шляху з одного джерела – загадку, що десятиліттями ставила в глухий кут дослідників та експертів.

“Ми виявили алгоритм, який вирішує цю проблему практично за лінійний час, найшвидшим способом. Це фундаментальна алгоритмічна проблема, яка вивчається з 1950-х років і викладається в усьому світі. Це була одна з причин, що спонукали нас розв’язати її”, – пояснює доцент Крістіан Вульф-Нільсен, який явно вважає, що важко залишити в спокої невирішену алгоритмічну проблему.

Більш швидкі розрахунки для маршрутизації електромобілів

Минулого року Вульф-Нільсен здійснив ще один прорив у тій самій царині – він отримав результат, що дає змогу знайти найкоротший шлях у мережі, яка змінюється з часом. Його рішення недавньої загадки ґрунтується на цій роботі.

Дослідник вважає, що розв’язання проблеми найкоротшого шляху з одного джерела може прокласти шлях до алгоритмів, які не тільки допоможуть електромобілям миттєво розрахувати найшвидший маршрут із пункту А до пункту Б, а й зробити це в найенергоефективніший спосіб.

“Ми додаємо вимір, якого немає у попередніх алгоритмів. Цей вимір дозволяє нам розглядати те, що ми називаємо негативними вагами. Практичним прикладом цього можуть бути пагорби в дорожній мережі, що корисно знати, якщо у вас є електромобіль, який заряджається під час руху вниз по схилу”, – пояснює Вульф-Нільсен.

Факти про проблему найкоротшого шляху:

Мета задачі про найкоротший шлях від одного джерела – знайти найкоротші шляхи від заданого початкового вузла до всіх інших вузлів мережі.
Мережу представлено у вигляді графа, що складається з вузлів і зв’язків між ними, які називаються ребрами.
Кожне ребро має напрямок (наприклад, його можна використовувати для представлення доріг з одностороннім рухом), а також вагу, яка виражає, наскільки дорого обходиться подорож цим ребром. Якщо всі ваги ребер невід’ємні, то задачу можна розв’язати практично за лінійний час за допомогою класичного алгоритму Дейкстри.
Новий результат розв’язує проблему майже за той самий час, що й алгоритм Дейкстри, але дає змогу використовувати і негативні ваги ребер.

“У принципі, алгоритм можна використовувати для попередження суб’єктів, таких як центральні банки, про те, що спекулянти займаються купівлею-продажем різних валют. Сьогодні багато чого з цього відбувається за допомогою комп’ютерів. Але оскільки наш алгоритм працює так швидко, його можна було б використовувати для виявлення лазівок до того, як ними скористаються”, – каже Крістіан Вульф-Нільсен.

Дослідник підкреслює, що системи для розрахунку валюти і маршрутів для електромобілів уже існують. Але вирішення проблеми найкоротшого шляху з одного джерела дало змогу дослідникам створити чудовий алгоритм, який практично неможливо перевершити за швидкістю. Водночас його простота робить його легко застосовним для різних потреб суспільства.

Нагорода в США

Робота над вирішенням проблеми не залишилася непоміченою. Дійсно, з Крістіаном Вульфф-Нільсеном і його колегами вже зв’язалися люди з усього світу, які бажають привітати їх і дізнатися більше про те, як їм це вдалося.

Водночас наукову статтю, в якій детально описується їхнє відкриття, було удостоєно нагороди “за найкращу доповідь” на конференції FOCS (Foundation of Computer Science) у Денвері, штат Колорадо.

“Люди з усього світу відвідують цю конференцію, щоб побачити, як презентують найкращі результати”, – каже Крістіан Вульф-Нільсен.

Дослідження було проведене у співпраці між Крістіаном Вульф-Нільсеном з факультету комп’ютерних наук, Данупоном Нанонгкаєм з Інституту Макса Планка та їхнім американським колегою Аароном Бернштейном з Університету Ратгерса.

Наразі дослідження доступне на сайті arXiv