Znakomity rozwiązujący zagadki algorytmiczne z lat 50. chwalony przez naukowca – ScienceDaily

Brzmi skomplikowanie? Prawdopodobnie. Ale w rzeczywistości ten rodzaj obliczeń jest już używany w wielu aplikacjach i technologiach, na których polegamy, aby znaleźć drogę — na przykład Mapy Google prowadzą nas przez krajobrazy i miasta.

Teraz problem rozwiązali naukowcy z Wydziału Informatyki Uniwersytetu Kopenhaskiego Problem najkrótszej ścieżki z jednego źródłatajemnica, która od dziesięcioleci wprawia badaczy i ekspertów w zakłopotanie.

„Odkryliśmy algorytm, który rozwiązuje problem w czasie niemal liniowym, w najszybszy możliwy sposób. To podstawowy problem algorytmu, który był badany od lat 50. XX wieku i jest nauczany na całym świecie. To był jeden z powodów, dla których zdecydowaliśmy się przyjechać znaleźć rozwiązanie”, wyjaśnia profesor nadzwyczajny Christian Wolf-Nielsen, któremu trudno jest odpuścić. Problem algorytmu, który nie został rozwiązany samodzielnie.

Szybsze obliczenia do sterowania pojazdami elektrycznymi

W zeszłym roku Wulff-Nilsen dokonał kolejnego przełomu w tym samym obszarze, uzyskując wynik, który dotyczył znalezienia najkrótszej ścieżki w sieci, która zmienia się w czasie. Jego rozwiązanie ostatniej zagadki opiera się na tej pracy.

Badacz uważa, że ​​rozwiązanie problemu najkrótszej ścieżki z jednym źródłem może utorować drogę algorytmom, które nie tylko pomogą samochodom elektrycznym obliczyć najszybszą trasę z punktu A do punktu B w jednej chwili, ale zrobią to w możliwie najbardziej energooszczędny sposób.

„Dodajemy wymiar, którego nie mają poprzednie algorytmy. Ten wymiar pozwala nam przyjrzeć się temu, co nazywamy ujemnymi wagami. Praktycznym tego przykładem może być odniesienie do wzgórz w sieci drogowej, co jest dobre do sprawdzenia, czy masz samochód elektryczny, który ładuje się podczas jazdy po zboczu, wyjaśnia Wolf-Nielsen.

Fakty dotyczące problemu najkrótszej ścieżki z jednego źródła

• Punkt Jedynym źródłem jest najkrótsza ścieżka Problem polega na znalezieniu najkrótszych ścieżek z danego węzła startowego do wszystkich pozostałych węzłów w sieci.
• Sieć jest reprezentowana jako graf składający się z węzłów i połączeń między nimi zwanych krawędziami.
• Dla każdej krawędzi kierunku (na przykład może służyć do reprezentowania dróg jednokierunkowych) plus waga, która wyraża koszt podróży wzdłuż tej krawędzi. Jeśli wszystkie wagi krawędzi są nieujemne, problem można rozwiązać w przybliżeniu w czasie liniowym, stosując klasyczny algorytm Dijkstry.
• Nowy wynik rozwiązuje problem w mniej więcej takim samym czasie jak algorytm Dijkstry, ale pozwala również na ujemne wagi krawędzi.

„W zasadzie algorytm mógłby być używany do ostrzegania aktorów, takich jak banki centralne, jeśli spekulanci spekulują na temat kupna i sprzedaży różnych walut. Wiele z tego dzieje się dzisiaj z komputerami. Ale ponieważ nasz algorytm jest tak szybki, może być w stanie użyć go do wykrywania luk w zabezpieczeniach przed ich wykorzystaniem”, mówi Christian Wolf-Nielsen.

Badaczka potwierdza, że ​​istnieją już systemy obliczania waluty i trasy dla samochodów elektrycznych. Ale rozwiązanie problemu najkrótszej ścieżki za pomocą jednego źródła pozwoliło naukowcom stworzyć imponujący algorytm, który jest prawie niemożliwy do pokonania pod względem szybkości. Jednocześnie jego prostota ułatwia dostosowanie do różnych potrzeb społeczeństwa.

uhonorowany w Stanach Zjednoczonych

Prace nad rozwiązaniem problemu nie pozostały niezauważone. W rzeczywistości z Christianem Wolfem Nielsenem i jego współpracownikami skontaktowali się już ludzie z całego świata, którzy chcieli im pogratulować i dowiedzieć się więcej o tym, jak to zrobili.

W tym samym czasie artykuł naukowy szczegółowo opisujący ich odkrycie został uhonorowany nagrodą „Best Paper Award” na konferencji FOCS (Foundation for Computer Science) w Denver w Kolorado. Obok STOC jest to najbardziej prestiżowa konferencja z zakresu informatyki teoretycznej. Konferencja FOCS odbyła się w dniach 31 października – 3 listopada 2022 roku.

„Ludzie z całego świata przyjeżdżają na tę konferencję, aby zobaczyć najlepsze wyniki”, mówi Christian Wolf-Nielsen.

Badania przeprowadzono we współpracy między Christianem Wolffem Nielsenem z Wydziału Informatyki, Danubonem Nanongkai z Instytutu Maxa Plancka i ich amerykańskim kolegą Aaronem Bernsteinem z Rutgers University.