Uogólnienia wyszukiwania binarnego dla zestawów?

28

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).

jkff
źródło
1
Co to jest sieć „multiset”?
Suresh Venkat,
1
Jest to sieć, której elementami są odwzorowania X -> N, spełnione są elementowe min, a łączenie to elementowe maks. Może być uogólniony na dowolną sieć zamiast N jako kodomena.
jkff 11.11.11

Odpowiedzi:

15

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.wwlognP

  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.wPPO(wlogn)


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()

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[n1]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:nX}2[n1]2[n1]P(Y)P(X)X=Y{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).P2nn+1

Sasho Nikolov
źródło
Wow, taki prosty pomysł! Dzięki - Zastanawiam się, czy wydaje się to optymalne, czy nie :)
jkff,
W rzeczywistości jest to nawet mniej niż w log n, ponieważ suma długości łańcucha wynosi n. Myślę, że maksimum to około w log (n / w).
jkff
OK, dla rzędów liniowych daje to wyszukiwanie binarne, dla sieci podzbiorów daje to C (n, n / 2) log (2 ^ n / C (n, n / 2)) ~ exp (n) * n. Nie za szybko, ale też nie wygląda zbyt optymalnie, ponieważ może być tak wiele odpowiedzi. Jednak, aby znaleźć jeden maksymalny podzbiór, potrzebuję cię Binary przeszukiwać byle jeden łańcuch - to jest wielki, a ja teraz nazywają się głupi, że nie myśli o niej. Dzięki jeszcze raz!
jkff,
2
Myślę, że łańcuchy rozłączne dają ci dolną granicę co najmniej (dla algorytmów deterministycznych). Pomyśl o przeciwniku, który „ukrywa” jedno rozwiązanie w ostatnim pytanym łańcuchu. Losowa dolna granica powinna wynikać z zasady minimax Yao. Znalezienie pojedynczego elementu o złożoności może być interesujące. ww+lognΩ(w)w+logn
Sasho Nikolov
1
@YanKingYin Krata nie może być połączeniem (więcej niż jednego) rozłącznych łańcuchów, ponieważ każdy z dwóch elementów musi mieć supremum. Poset to połączenie rozłącznych łańcuchów, jeśli można je podzielić, tak aby elementy z różnych części były nieporównywalne, a elementy w tej samej części przyjmowały całkowity porządek.
Sasho Nikolov,
8

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ąnwO(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.

Suresh Venkat
źródło
Heh, to nie brzmi zbyt inspirująco w porównaniu do log (n) :), ale i tak dzięki!
jkff 11.11.11
Ale o to chodzi. Bez struktur danych nie można uzyskać dziennika nawet dla kompletnie uporządkowanego zestawu, ponieważ wszystko, co można zrobić, to skanować. To naprawdę fajne pytanie, aby znaleźć odpowiednik BST.
Suresh Venkat,
Cóż - mówię o złożoności pod względem liczby ocen predykatu P, a nie predykatu porównawczego.
jkff 11.11.11
1
W pewnym sensie tak, ale nie jest to kompletna odpowiedź - np. Nie daje podziału na przypadki 1d lub 2d :) co sugerujesz zrobić z pierwiastkami?
jkff 11.11.11
1
Nie wiem jeszcze. myśleć na głos. Ale to doskonałe pytanie.
Suresh Venkat,
4

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.nd

domotorp
źródło
Obawiam się, że nie rozumiem pierwszego akapitu. Czy w swojej redukcji masz wszystkie n-bitowe ciągi w zestawie S i czy są one podane jako część danych wejściowych? Jeśli tak, możemy przejść przez wszystkie ciągi w czasie wielomianowym.
Yoshio Okamoto,
1
@YoshioOkamoto: Myślę, że w tym akapicie założono, że porównanie w S podano jako obwód logiczny. (Ale to nie ma nic wspólnego z wyszukiwaniem w zestawie i dlatego nie jest dla mnie interesujące.)
Tsuyoshi Ito,
@Tsuyoshi: Dziękuję. To ma sens.
Yoshio Okamoto
4

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 PP2[n]nPP

a3nm
źródło