Дослідники спростовують поширену думку про онлайн-алгоритми | Журнал Quanta

У житті нам іноді доводиться приймати рішення, не маючи всієї необхідної інформації; це також вірно в інформатиці. Це сфера онлайн-алгоритмів, які, незважаючи на свою назву, не обов’язково включають Інтернет. Натомість це стратегії вирішення проблем, які реагують на дані, щойно вони надходять, без жодного знання про те, що може бути далі. Ця здатність справлятися з невизначеністю робить ці алгоритми корисними для реальних головоломок, як-от керування пам’яттю на ноутбуці чи вибір реклами для показу людям, які переглядають веб-сторінки.

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

«Дійсно просто визначити цю проблему», — сказав Марцін Бєньковський, дослідник алгоритмів у Вроцлавському університеті в Польщі. Але це «виявляється дивно складним». Оскільки дослідники почали атакувати k-серверною проблемою наприкінці 1980-х, вони задалися питанням, наскільки добре онлайн-алгоритми можуть впоратися з цим завданням.

Протягом десятиліть дослідники почали вірити, що завжди можна досягти певного рівня алгоритмічної продуктивності k- проблема з сервером. Тому незалежно від того, з якою версією проблеми ви маєте справу, знайдеться алгоритм, який досягне цієї мети. Але в статті, вперше опублікованій в Інтернеті в листопаді минулого року, троє комп'ютерників показав що це не завжди можливо. У деяких випадках кожен алгоритм не виконується.

«Мені приємно сказати, що це було для мене великою несподіванкою», - сказав Анупам Гупта, який вивчає алгоритми в Університеті Карнегі-Меллона і не брав участі в роботі. Робота пропонує «глибше розуміння центральної проблеми в цій сфері».

Перш за все комп’ютерники окреслив цю проблему у 1988 році. Щоб зрозуміти це, уявімо компанію, у якій працюють сантехніки. У міру надходження дзвінків компанії потрібно вирішити, який сантехнік до якого місця піде. Мета компанії — і мета алгоритму для k-проблема сервера — мінімізувати загальну відстань, яку проходять усі сантехніки.

Складність полягає в тому, що компанія не знає заздалегідь, звідки надходитимуть дзвінки. Якщо так, то він міг би покладатися на «автономний алгоритм», який знає майбутнє. Зокрема, він може використовувати ідеальну стратегію диспетчеризації, яка знаходить рішення з найменшим загальним переміщенням для будь-якої серії викликів. Жоден онлайн-алгоритм ніколи не зможе перемогти його або навіть надійно зрівняти його.

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

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

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

Хоча ця абстрактна проблема не актуальна для реальних сантехнічних компаній, “the k«Сама проблема сервера є визначальним питанням» в онлайн-обчисленнях Юваль Рабані, комп’ютерний науковець з Єврейського університету в Єрусалимі, який є співавтором нещодавньої статті. Частково це тому, що інструменти та методи, розроблені під час роботи над k-серверні проблеми часто знаходять застосування в інших місцях дослідження онлайн-алгоритмів і навіть поза ним.

«Це частина магії роботи над алгоритмами», — сказав він.

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

Ця стратегія досить ефективна, і з початку 1990-х років дослідники підозрювали, що ви завжди можете знайти рандомізований алгоритм, який досягає конкретної цілі продуктивності: конкурентоспроможного співвідношення, пропорційного log k, Де k це кількість агентів. Це називається рандомізованим k-серверну гіпотезу, і дослідники показали, що це справедливо для деяких приміщень або певних наборів точок (еквівалент будинків, які можуть викликати сантехніків). Але не для всіх випадків це доведено.

Як і більшість дослідників, Рабані та його співавтори — Себастьян Бубек Microsoft Research and Крістіан Костер Оксфордського університету — вважав, що припущення було вірним. «У мене не було причин сумніватися», — сказав Костер.

Але це почало змінюватися, коли вони працювали над іншою онлайн-проблемою. Це мало зв'язки з k-проблема з сервером, і відома нижня межа конкурентоспроможності була неочікувано високою. Це змусило їх подумати про низьку ціль, як колода k для k-проблема з сервером була надто оптимістичною.

Рабані сказав, що саме Костер першим запропонував провести рандомізацію k- припущення про сервер може бути хибним. «Як тільки він це сказав, усе набуло сенсу».

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

Вибір нагадав Рабані вірш Роберта Фроста «Дорога не пройдена,», де мандрівник розмірковує про два потенційних шляхи через жовтий ліс. «Ми просто застосовуємо вірш рекурсивно», — пожартував він. «І тоді справи йдуть дуже погано».

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

Ця робота, яка перемогла а Нагорода за найкращу роботу в 2023 Симпозіум з теорії обчислювальної техніки, знаменує собою «тверду теоретичну» віху, сказав Гупта. Такий результат допомагає визначити, на яку продуктивність ми можемо сподіватися від наших алгоритмів. На практиці, однак, розробники алгоритмів часто не орієнтуються на найгірші сценарії з всемогутнім ворогом і повним незнанням про майбутнє. Коли алгоритми розв’язують проблеми реального світу, вони часто перевершують теоретичні очікування.

Стаття, в якій також доведено обмеження для рандомізованих алгоритмів, що використовуються для інших проблем, також може мати наслідки для майбутньої роботи в цій галузі. Результат чітко «підкреслює потужність» техніки, яку використовували автори, сказав Гупта.

Можливо, ці майбутні відкриття кинуть виклик очікуванням дослідників, як це сталося, сказав Рабані. «Це один із випадків, коли помилятися дуже добре».

Quanta проводить серію опитувань, щоб краще обслуговувати нашу аудиторію. Візьміть наші опитування читачів інформатики і ви будете введені, щоб виграти безкоштовно Quanta товар