Nowy algorytm może radykalnie usprawnić rozwiązania problemu „maksymalnego przepływu”

Znalezienie najbardziej wydajnego sposobu transportu przedmiotów w sieci, takiej jak amerykański system autostrad lub Internet, to problem, który od dziesięcioleci obciąża matematyków i informatyków.

Aby rozwiązać ten problem, naukowcy tradycyjnie stosowali algorytm maksymalnego przepływu, znany również jako maksymalny przepływ, w którym sieć jest reprezentowana jako graf z serią węzłów, zwanych wierzchołkami i łączącymi je liniami, zwanymi krawędziami.

Biorąc pod uwagę, że każda krawędź ma maksymalną przepustowość — podobnie jak drogi lub kable światłowodowe używane do przesyłania informacji w Internecie — takie algorytmy próbują znaleźć najbardziej wydajny sposób przesyłania towarów z jednego węzła grafu do drugiego, bez przekraczania te ograniczenia.

Ale ponieważ rozmiar sieci, takich jak Internet, rósł wykładniczo, rozwiązywanie tych problemów za pomocą tradycyjnych technik obliczeniowych jest często zbyt czasochłonne, jak twierdzi Jonathan Kelner, profesor matematyki stosowanej na MIT i członek MIT. Laboratorium Informatyki i Sztucznej Inteligencji (CSAIL).

Tak więc w artykule, który ma zostać zaprezentowany w tym tygodniu na Sympozjum ACM-SIAM na temat algorytmów dyskretnych w Portland w stanie Oregon, Kelner i jego kolega Lorenzo Orecchia, instruktor matematyki stosowanej, wraz ze studentami Yin Tat Lee i Aaronem Sidfordem opiszą nowy algorytm teoretyczny, który może radykalnie zmniejszyć liczbę operacji potrzebnych do rozwiązania problemu maksymalnego przepływu, umożliwiając rozwiązanie nawet ogromnych sieci, takich jak Internet czy ludzki genom.

WIZERUNEK: CHRISTINE DANILOFF / Z

Ostatnio nastąpiła eksplozja rozmiarów badanych wykresów, mówi Kelner. Na przykład, jeśli chcesz kierować ruch w Internecie, badać wszystkie połączenia na Facebooku lub analizować dane genomowe, możesz łatwo otrzymać wykresy z milionami, miliardami, a nawet bilionami krawędzi.

Poprzednie algorytmy z maksymalnym przepływem rozwiązywały problem po jednej krawędzi lub ścieżce, mówi Kelner. Na przykład, wysyłając elementy z węzła A do węzła B, algorytmy przesyłają część towarów jedną ścieżką, aż osiągną maksymalną pojemność, a następnie zaczynają wysyłać część kolejną ścieżką.

Wiele poprzednich algorytmów, jak mówi Kelner, znajdowałoby ścieżkę z punktu A do punktu B, wysyłało wzdłuż niej pewien przepływ, a następnie pytało: „Biorąc pod uwagę to, co już zrobiłem, czy mogę znaleźć inną ścieżkę, wzdłuż której mogę wysłać więcej?”. Gdy trzeba przesyłać przepływ jednocześnie wieloma różnymi ścieżkami, prowadzi to do wewnętrznego ograniczenia szybkości algorytmu.

Jednak w 2011 roku Kelner, absolwent CSAIL Aleksander Madry, student matematyki Paul Christiano oraz koledzy z Yale University i University of Southern California opracowali technikę analizy wszystkich ścieżek jednocześnie.

Naukowcy postrzegali wykres jako zbiór rezystorów elektrycznych, a następnie wyobrazili sobie podłączenie akumulatora do węzła A i uziemienia do węzła B, co umożliwiło przepływ prądu przez sieć. Prąd elektryczny nie wybiera tylko jednej ścieżki, prześle trochę prądu przez każdy rezystor w sieci, mówi Kelner. Sonduje więc cały wykres globalnie, badając jednocześnie wiele ścieżek.

Umożliwiło to nowemu algorytmowi rozwiązanie problemu maksymalnego przepływu znacznie szybciej niż poprzednie próby.

Teraz zespół MIT opracował technikę jeszcze bardziej skracającą czas działania, umożliwiającą analizę nawet gigantycznych sieci, mówi Kelner.

W przeciwieństwie do poprzednich algorytmów, które traktowały wszystkie ścieżki w grafie jako równe, nowa technika identyfikuje te trasy, które tworzą wąskie gardło w sieci. Algorytm zespołu dzieli każdy wykres na klastry dobrze połączonych węzłów i ścieżki między nimi, które tworzą wąskie gardła, mówi Kelner.

Nasz algorytm określa, które części wykresu mogą z łatwością kierować to, czego potrzebują, a które części są wąskimi gardłami. Dzięki temu możesz skupić się na obszarach problemowych i strukturze wysokiego poziomu, zamiast spędzać dużo czasu na podejmowaniu nieistotnych decyzji, co oznacza, że ​​możesz znacznie efektywniej wykorzystać swój czas – mówi.

Rezultatem jest prawie liniowy algorytm, mówi Kelner, co oznacza, że ​​czas potrzebny na rozwiązanie problemu jest bardzo zbliżony do wprost proporcjonalnej do liczby węzłów w sieci. Więc jeśli liczba węzłów na wykresie zostanie pomnożona przez 10, czas zostanie pomnożony przez coś bardzo bliskiego 10, w przeciwieństwie do pomnożenia przez 100 lub 1000, mówi. Oznacza to, że skaluje się zasadniczo tak dobrze, jak można mieć nadzieję z rozmiarem danych wejściowych, mówi.

Shanghua Teng, profesor informatyki na Uniwersytecie Południowej Kalifornii, który nie brał udziału w najnowszym artykule, mówi, że stanowi on wielki przełom w algorytmach grafowych i oprogramowaniu optymalizacyjnym.

Teng, który jest zdobywcą nagrody za najlepszy artykuł na konferencji [ACM-SIAM], jest wynikiem nieustających wysiłków Kelnera i jego współpracowników nad zastosowaniem przepływów elektrycznych do projektowania wydajnych algorytmów grafowych, mówi Teng. Artykuł zawiera niesamowitą gamę wkładów technicznych.

ukryć