Uogólnienia wyszukiwania binarnego dla zestawów?

Załóżmy, że mam poset „S” i monotoniczny predykat „P” na S. Chcę znaleźć jeden lub wszystkie maksymalne elementy S spełniające P.

EDIT : Jestem zainteresowany minimalizując liczbę ocen P .

Jakie algorytmy istnieją dla tego problemu i jakich właściwości i dodatkowych operacji wymagają na S?

Co z ważnymi przypadkami specjalnymi, takimi jak:

• S jest rzędem liniowym - wtedy działa zwykłe wyszukiwanie binarne, o ile masz operację „znajdź środek”
• S to krata
• S jest podzbiorem sieci
• S to sieć wielosetowa
• ...

Dwa ostatnie przypadki wydają się szczególnie ważne np. Przy projektowaniu eksperymentu - masz zestaw parametrów boolowskich lub rzeczywistych i chcesz znaleźć najmniejszą możliwą kombinację z nich, która odtwarza określony wzorzec (np. Test nieudany).

Nie zastanawiałem się nad tym bardzo, więc proszę, poprawcie mnie, jeśli się mylę.

Powiedz „ to szerokość zestawu.$w$

1. Dla zestawu, który jest połączeniem łańcuchów rozłącznych, potrzebujesz przynajmniej ocen po prostu stosując standardową dolną granicę złożoności zapytania wyszukiwania binarnego dla każdego łańcucha.$w$$w\log n$$P$

2. Ponieważ dajesz porównania za darmo, możesz obliczyć rozkład łańcucha posetu łańcuchy w za darmo. Wykonaj wyszukiwanie binarne w każdym łańcuchu zidentyfikować pierwszy element, który spełnia . Następnie przejrzyj zidentyfikowane elementy i usuń wszystkie zdominowane. Liczba ocen wynosi . To identyfikuje wszystkie maksymalne elementy, ponieważ może być najwyżej jeden maksymalny element na łańcuch.$w$$P$$P$$O(w\log n)$

DODATKOWO: W rzeczywistości widzę prosty algorytm rekurencyjny, który działałby znacznie lepiej ( ) dla sieci podzbiorów ( EDYCJA : domotor opisał ogólną strategię w swojej odpowiedzi). Tutaj zakładam, że jest monotoniczny w dół (tj. Podzbiory tworzą niższy zbiór), co myślę, co masz na myśli. Oto algorytm znajdowania członka niższego zestawu:$O(n)$$2^{[n]}$$P$$\{X: P(X) = 1\}$

a) Test . Jeśli 0, to przestań.$P(\emptyset)$

b) Test . $P(\{n\})$

bi) Jeśli 0, to powtórz (OK, ponieważ żaden zestaw zawierający może znajdować się w dolnym zestawie).$2^{[n-1]}$$n$

b.ii) Jeśli 1, oznacza to, że istnieje element niższego zestawu w sublattice . Ta podsieć jest izomorficzna do więc po raz kolejny możemy się powtórzyć. Dokładniej, możemy uruchomić algorytm dla , ale kiedy algorytm prosi o ocenę , oceniamy gdzie .$\{X: n \in X\}$$2^{[n-1]}$$2^{[n-1]}$$P(Y)$$P(X)$$X = Y \cup \{n\}$

Tak więc na każdym kroku powracamy do podsieci, która jest o połowę mniejsza od oryginalnej. Ogólnie rzecz biorąc, musimy ocenić co najwyżej razy (w rzeczywistości możesz zaimplementować algorytm, aby oszacować predykat razy, jak wskazuje Yoshio, ponieważ wystarczy sprawdzić tylko raz).$P$$2n$$n+1$$\emptyset$

Jeśli jest drzewem, istnieje algorytm wielomianowy, który konstruuje optymalne drzewo decyzyjne.$P$

Uogólnienie wyszukiwania binarnego: wyszukiwanie w częściowych drzewach i lasach

Jeden z ostatnich artykułów Daskalakisa i in. Pokazuje, że dla zestawu wielkości i szerokości minimalne elementy można znaleźć w czasie . Co ciekawe, w ich streszczeniu, mówią$n$$w$$O(wn)$

Interesujące byłoby również znalezienie wydajnych statycznych i dynamicznych struktur danych, które odgrywają tę samą rolę dla zamówień częściowych, które stosy i drzewa wyszukiwania binarnego odgrywają dla zamówień całkowitych.

Jeśli S jest częścią danych wejściowych, wówczas problem znalezienia maksymalnego elementu staje się już `` trudny NP '' (jeśli myślimy o sieci tak, że jego elementy są n-bitowymi łańcuchami), np. Możesz powiedzieć jeśli CNF (x) nie jest prawdziwe, a CNF (y) jest prawdziwe dla niektórych stałych CNF.$x<y$

Ponadto może być wiele maksymalnych elementów spełniających wymagania P, więc nawet ich wydrukowanie może zająć dużo czasu, więc myślę, że istnieje tylko nadzieja na znalezienie jednego maksimum.

Ogólnie rzecz biorąc, wyszukiwanie binarne działa, jeśli można rekurencyjnie wybierać elementy, tak że po pozostawieniu powyższych elementów lub powyższych elementów są usuwane, a w każdym takim zestawie usuwany jest stały stosunek elementów.

Na przykład. jeśli S jest siatką o stałych wymiarach, to istnieje szybki algorytm: Zawsze zmniejszaj o połowę jedną współrzędną, pozostawiając pozostałe minimalne, więc zapytaj np. w pierwszym kroku (n / 2,0, ..., 0).

Jednym ważnym powiązanym twierdzeniem jest twierdzenie Tarskiego o stałym punkcie, w którym zamiast P masz monotoniczne mapowanie z sieci do siebie. Twierdzenie mówi, że punkty stałe tworzą sieć. Udowodniliśmy z Jarosławem Byrka i Pawła Duetting że w tym ustawieniu, gdy kratownica jest siatką d-wymiarowej, można znaleźć stałą temperaturę w ciągu około czasowej, w której algorytm jest prostym uogólnieniem wyszukiwania binarnego.$n^d$

W przypadku problemu znalezienia wszystkich maksymalnych elementów w sieci podzbiorów , oznacza to dokładne wnioskowanie o dodatniej funkcji boolowskiej zmiennych boolowskich. Jeśli zależy Ci tylko na liczbie ocen (a nie na złożoności obliczeniowej), możesz znaleźć ankietę w Data Mining i Discovery Knowledge za pomocą metod opartych na logice , rozdział 10, sekcja 10.2.4 lub w ostatnim akapicie sekcji 6.1 tego artykułu , na który wskazała mi ta odpowiedź (uwaga, reszta tego artykułu dotyczy złożoności obliczeniowej, a nie tylko złożoności oceny ).2 [ n ] n P $P$$2^{[n]}$$n$$P$$P$