Zrandomizowany Max-Cut
lion137
Kolejny odcinek algorytmów zrandomizowanych.
Weźmy Max-Cut Problem, czyli: na wejściu mamy graf, i staramy się tak pokolorować jego wierzchołki, używając jedynie dwóch kolorów, aby jak najwięcej ścieżek było pomiędzy różnymi kolorami (czyli – Max-Cut).
Problem jest NP Hard. Istnieje algorytm "local search" – gwarantuje on, w czasie wielomianowym (O(n2)?), że co najmniej połowa wierzchołków będzie w zbiorze "Cut".
Przykład: losowy wybór "Cut"
A co, gdyby spróbować, dla hecy, kompletnie losowo wybrać "Cut"? Na przykład:
for i from 1 to n:
color[i] = RandomInteger[1,2]
Bardzo prosto, iterujemy po wierzchołkach i każdemu, losowo, przypisujemy jeden z dwóch kolorów – nie potrzebujemy do tego nawet grafu. Okazuje się, że taki losowy wybór jest nie gorszy od "local search" (!). Dowód:
Niech X będzie zmienną losową, której wartością jest ilość krawędzi, które są "Cut". Szukamy E[X] = ? (jej wartości oczekiwanej).
Dla każdej z m krawędzi e, niech Be będzie zdarzeniem, że jest "Cut". Niech Xe będzie zmienna losową charakterystyczną dla Be ( tzw, _Indicator Function). Wtedy:
Dalej, z własności funkcji charakterystycznej:
Teraz potrzebujemy już tylko prawdopodobieństwa, że krawędź jest w "Cut". Wynosi ono 1/2 (z możliwości (1,1), (1, 2), (2, 1), (2,2), dwie (1, 2) i (2, 1) oznaczają przecięcie). Czyli finalnie:
Dwie linijki kodu; algorytm szybki, a statystycznie nie gorszy niż bardziej skomplikowany.
@lion137: poprawiłem kilka rzeczy w tym artykule (składnię, słownictwo, formatowanie), ale może mógłbyś jakoś bardziej to opisać? Nie znam się na tym algorytmie. Wydaje mi się, że przykład "dla hecy" jest całkiem nie na miejscu w Kompendium – chyba że wynikowo nie będzie "dla hecy", a rzeczywiście będzie coś wnosić.