Навколо планети всього за кілька годин: науковці створили інноваційний метод для формування маршрутів.

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

Алгоритм Дейкстри, розроблений голландським комп'ютерним вченим Едсгером Дейкстрою в 1956 році, є основним інструментом для вирішення задачі знаходження найкоротшого шляху в графах і різноманітних системах, які передбачають переміщення між двома точками. Спочатку його створили для демонстрації можливостей нового комп'ютера, і сам Дейкстра зміг сформулювати алгоритм без жодних записів всього за 20 хвилин у кафе. Цей алгоритм ефективно визначає найкоротший шлях від однієї вихідної точки до всіх інших цілей у мережі, як зазначає Quanta Magazine.

У Фокус.Технології стартував новий Telegram-канал! Підписуйтеся, щоб бути в курсі найактуальніших та найзахопливіших новин з галузі науки!

Попри свою простоту й адаптивність, що зробило його основоположною темою в навчанні інформатики, Алгоритм Дейкстри залишав місце для оптимізації структур даних, щоб прискорити виконання різних завдань. З роками з'явилися такі вдосконалення, як "купи", які збільшували час роботи алгоритму за рахунок швидкого пошуку найближчих вершин. Розробка такої спеціалізованої купи 1984 року встановила теоретичний стандарт для задач найкоротших шляхів з одним джерелом, зробивши алгоритм неперевершеним за найгірших умов, йшлося в дослідженні, опублікованому в arXiv.

Проте дослідників продовжує захоплювати ідея знайти алгоритм, який буде оптимальним у будь-яких умовах — це концепція, відома як "універсальна оптимальність". Завдяки нещодавньому науковому прориву команда на чолі з Вацлавом Рожоном і Бернхардом Хойплером створила універсально оптимізований варіант алгоритму Дейкстри. Ця нова реалізація демонструє високу ефективність в будь-якій мережевій структурі навіть у найскладніших умовах трафіку, спираючись на особливості деяких типів купи, які раніше не використовувалися. Їхнє досягнення, що полягає в спрощенні складних конструкцій, підкреслює можливості простих алгоритмів у вирішенні вимогливих задач.

Хоча цей вдосконалений алгоритм, ймовірно, не знайде термінового практичного застосування через реальні обмеження, такі як обчислювальні витрати в системах на кшталт Google Maps, він вже став джерелом натхнення для нових досліджень у сфері теоретичного проєктування алгоритмів, здатних прокладати прості та ефективні маршрути на різних картах. Результати цих досліджень отримають нагороду за найкращу доповідь на Симпозіумі основ комп'ютерних наук 2024 року, що підкреслює їх важливість для подальшого розвитку цієї дисципліни.

Раніше видання "Фокус" розглядало п’ять щоденних практик, здатних сприяти поліпшенню здоров'я мозку. У пошуках способів підтримки когнітивних функцій наука та звичні дії переплітаються в надзвичайно простих формах, що призводять до легких та результативних кроків для покращення нашого самопочуття і функціонування центру прийняття рішень.

Також Фокус писав про особисті якості, які не дають нам вірити фейковим новинам. Згідно з дослідженням, проникливість відіграє вирішальну роль у здатності оцінювати точність інформації.