Przybliżenie objętości wypukłej
W analizie algorytmów kilku autorów badało obliczanie objętości wielowymiarowych ciał wypukłych , problem, który można również wykorzystać do modelowania wielu innych problemów w wyliczaniu kombinatorycznym . Często prace te wykorzystują model obliczeniowy czarnej skrzynki, w którym dane wejściowe są podawane przez podprogram do testowania, czy punkt znajduje się wewnątrz lub na zewnątrz wypukłego ciała, a nie przez wyraźną listę wierzchołków lub ścian wypukłego polytope . Wiadomo, że w tym modelu żaden algorytm deterministyczny nie może osiągnąć dokładnego przybliżenia, a nawet dla jawnego zestawienia ścian lub wierzchołków problem jest #P-trudny . Jednak wspólna praca Martina Dyera , Alana M. Frieze i Ravindrana Kannana dostarczyła losowego schematu aproksymacji czasu wielomianu dla problemu, zapewniając ostry kontrast między możliwościami algorytmów losowych i deterministycznych.
wynikiem artykułu jest losowy algorytm znajdowania wypukłego -wymiarowej przestrzeni euklidesowej przy istnienia wyrocznia członkowska . Algorytm wymaga wymiarze _ Algorytm łączy w sobie dwie idee:
- Korzystając z metody Monte Carlo łańcucha Markowa (MCMC), możliwe jest generowanie punktów, które są prawie równomiernie rozmieszczone losowo w obrębie danego ciała wypukłego. Podstawowym schematem algorytmu jest prawie jednolite próbkowanie z wnętrza siatki składającej się z i wykonanie losowego spaceru po tych kostkach. Wykorzystując teorię szybkiego mieszania się łańcuchów Markowa , wykazali, że potrzeba czasu wielomianu, aby błądzenie losowe osiągnęło rozkład prawie jednorodny.
- Za pomocą próbkowania odrzutowego możliwe jest porównanie objętości dwóch ciał wypukłych, jednego zagnieżdżonego w drugim, gdy ich objętości różnią się od siebie w niewielkim stopniu. Podstawową ideą jest wygenerowanie losowych punktów w zewnętrznym z dwóch ciał i policzenie, jak często te punkty znajdują się również w ciele wewnętrznym.
Dany korpus wypukły można przybliżyć sekwencją ciał zagnieżdżonych, ostatecznie osiągając jeden o znanej objętości (hipersferę), przy czym podejście to stosuje się do oszacowania współczynnika zmiany objętości na każdym kroku tej sekwencji. Pomnożenie tych czynników daje przybliżoną objętość pierwotnego ciała.
Ta praca przyniosła autorom Nagrodę Fulkersona w 1991 roku .
Ulepszenia
Chociaż czas tego algorytmu jest wielomianowy, ma on wysoki wykładnik. Kolejni autorzy poprawili czas działania tej metody, zapewniając szybsze mieszanie łańcuchów Markowa dla tego samego problemu.
Uogólnienia
Wynik aproksymacji w czasie wielomianowym został uogólniony na bardziej złożone struktury, takie jak połączenie i przecięcie obiektów. Odnosi się to do problemu miary Klee .