Nowy algorytm przepływu bije rekordy szybkości według najnowszych badań naukowych

WarsawZespół badaczy z ETH Zurich, pod kierownictwem Rasmusa Kynga, opracował najszybszy algorytm do rozwiązywania problemów przepływu w sieciach. Ta innowacyjna metoda ma zmienić sposób, w jaki obliczamy optymalne przepływy w sieciach.

Algorytm Kynga rozwiązuje problem maksymalnego przepływu. Pozwala znaleźć najefektywniejszy sposób przemieszczania towarów przez sieć, minimalizując jednocześnie koszty. Metoda ta może być zastosowana do różnego rodzaju sieci, takich jak systemy transportowe czy internet.

Oto kluczowe informacje na temat nowego algorytmu:

• Błyskawicznie oblicza optymalny przepływ w sieci po załadowaniu danych
• Jest skuteczny zarówno w statycznych, jak i dynamicznie zmieniających się sieciach
• Obsługuje dodawanie i usuwanie połączeń sieciowych
• Uzyskał status jednego z dziesięciu największych odkryć informatyki w 2022 roku
• Zdobył nagrodę dla najlepszego artykułu na IEEE Annual Symposium on Foundations of Computer Science (FOCS) w 2022 roku

Kiedyś znalezienie najlepszych tras w sieciach zajmowało dużo czasu. Wraz z rozwojem i zwiększoną złożonością sieci, czas potrzebny na ich obliczenie jeszcze bardziej się wydłużał. Jednak metoda Kynga sprawia, że czas obliczeń rośnie wprost proporcjonalnie do rozmiaru sieci.

Do 2004 roku najlepsze algorytmy obliczały przepływy w sieci złożoności czasowej proporcjonalnej do liczby połączeń podniesionej do potęgi 1,5. W 2004 roku udało się to poprawić do złożoności czasowej proporcjonalnej do liczby połączeń podniesionej do potęgi 1,33. Teraz algorytm Kynga znacząco zmniejsza czas potrzebny na dodatkowe obliczenia.

Prace Kynga są udoskonalane. Zaktualizowane algorytmy potrafią teraz działać w sieciach, które zmieniają się w czasie. Szybko obliczają najlepsze przepływy, nawet w sieciach z wieloma zmianami. Jest to istotne dla rzeczywistych sieci, takich jak systemy ruchu drogowego, które nieustannie się zmieniają.

Na sympozjum ACM na temat teorii obliczeń w Vancouver, Simon Meierhans z ETH przedstawił szybki algorytm. Algorytm ten rozwiązuje problem maksymalnego przepływu o minimalnym koszcie w sieciach, które zmieniają się stopniowo.

Zobacz również:

Dzisiaj · 15:52

Miasta a zdrowie Rafy: wykorzystanie kompensacji wodnej

Zespół napisał kolejny artykuł, który został przyjęty na konferencję FOCS, gdzie opracowali algorytm do zarządzania usuwaniem połączeń. Jest to pomocne w sytuacjach takich jak zamknięcie i ponowne otwarcie tras komunikacyjnych.

Zespół Kynga opracował nową metodę, ulepszając starsze techniki. Zamiast pracować nad dużymi fragmentami, stosują wiele małych kroków. Dzięki temu podejściu obliczenia są znacznie szybsze.

W latach 50. XX wieku naukowcy zaczęli systematycznie rozwiązywać problemy przepływu w sieciach. W tym czasie Lester R. Ford Jr. i Delbert R. Fulkerson opracowali ważne algorytmy. Zajmowali się problemem maksymalnego przepływu, który polega na efektywnym przemieszczaniu dóbr przez sieć.

Wcześniejsze algorytmy były skuteczne, lecz działały wolno. Algorytm Kynga jest zarazem skuteczny i szybki. Przed Kyngiem badacze skupiali się na modelach sieci kolejowej lub energetycznej. Metoda Kynga łączy najlepsze cechy obu modeli.

Zespół stworzył nowe narzędzia matematyczne, aby przyspieszyć działanie swoich algorytmów. Opracowali nową metodę organizacji danych sieciowych, która umożliwia szybkie wykrywanie zmian w połączeniach sieciowych. Dzięki temu algorytm działa znacznie szybciej.

Naukowcy z ETH Zurich opracowali nowe algorytmy, które działają bardzo szybko. Te algorytmy umożliwiają błyskawiczne rozwiązywanie dużych problemów i zmieniają sposób, w jaki komputery radzą sobie z trudnymi zadaniami.

To badanie ma istotne znaczenie w dziedzinie informatyki. Usprawnia ono sposób zarządzania dużymi i zmieniającymi się sieciami danych. Znajduje zastosowanie w wielu obszarach, w tym w biologii i sieciach społecznościowych.