Generalisasi pencarian biner untuk poset?

28

Misalkan saya memiliki poset "S" dan predikat monoton "P" pada S. Saya ingin menemukan satu atau semua elemen maksimal dari S yang memuaskan P.

EDIT : Saya tertarik dalam meminimalkan jumlah evaluasi P .

Algoritma apa yang ada untuk masalah ini dan properti serta operasi tambahan apa yang mereka butuhkan di S?

Bagaimana dengan kasus khusus yang penting, seperti:

S adalah urutan linier - maka pencarian biner biasa berfungsi, selama Anda memiliki operasi "find middle"
S adalah sebuah kisi
S adalah kisi subset
S adalah kisi multiset
...

Dua kasus terakhir tampaknya sangat penting misalnya untuk desain eksperimen - Anda memiliki serangkaian parameter boolean atau nyata, dan Anda ingin menemukan kombinasi terkecil dari mereka yang mereproduksi pola tertentu (misalnya tes gagal).

ds.algorithms ds.data-structures partial-order order-theory search-problem Jkff
sumber

1

Apa kisi 'multiset'?

Suresh Venkat

1

Ini adalah kisi yang elemennya adalah pemetaan X -> N, meet adalah elementwise min dan join adalah elementwise max. Ia dapat digeneralisasikan ke sembarang kisi alih-alih N sebagai kodomain.

jkff

15

Saya belum terlalu memikirkan hal ini, jadi tolong perbaiki saya jika saya salah.

Katakanlah adalah lebar poset. $w$

Untuk poset yang merupakan gabungan dari rantai menguraikan Anda memerlukan setidaknya evaluasi dari dengan hanya menerapkan standar batas bawah pada kompleksitas query pencarian biner untuk masing-masing rantai. $w$ $w\log n$ $P$
Karena Anda memberikan perbandingan secara gratis, Anda dapat menghitung dekomposisi rantai poset menjadi rantai secara gratis. Melakukan pencarian biner pada setiap rantai untuk mengidentifikasi elemen pertama yang memenuhi . Kemudian pergi ke elemen yang diidentifikasi dan menghapus yang dominan. Jumlah evaluasi adalah . Ini mengidentifikasi semua elemen maksimal, karena mungkin ada paling banyak satu elemen maksimal per rantai. $w$ $P$ $P$ $O(w\log n)$

TAMBAH: Sebenarnya saya melihat algoritma rekursif sederhana untuk melakukan jauh lebih baik ( ) untuk kisi subset ( EDIT : domotor menggambarkan strategi umum dalam jawabannya). Di sini saya berasumsi adalah monoton ke bawah (yaitu himpunan bagian membentuk himpunan yang lebih rendah), yang saya pikir apa yang Anda maksud. Jadi, inilah algoritme untuk menemukan anggota kelompok yang lebih rendah: $O(n)$ $2^{[n]}$ $P$ $\{X: P(X) = 1\}$

a) Uji . Jika 0, maka berhenti. $P(\emptyset)$

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

bi) Jika 0, maka kambuh pada (OK, karena tidak ada set yang mengandung bisa di set lebih rendah). $2^{[n-1]}$ $n$

b.ii) Jika 1, maka ada anggota himpunan bagian bawah di sublattice . Subkisi ini isomorfik hingga jadi sekali lagi kita bisa kambuh. Lebih tepatnya, kita dapat menjalankan algoritma untuk , tetapi ketika algoritma meminta untuk mengevaluasi , kita mengevaluasi mana . $\{X: n \in X\}$ $2^{[n-1]}$ $2^{[n-1]}$ $P(Y)$ $P(X)$ $X = Y \cup \{n\}$

Jadi dalam setiap langkah kita mengulang pada sublattice yang setengah dari ukuran aslinya. Secara keseluruhan, kita perlu mengevaluasi paling banyak kali (pada kenyataannya Anda dapat mengimplementasikan algoritma untuk mengevaluasi predikat kali seperti yang ditunjukkan Yoshio, karena Anda hanya perlu memeriksa sekali). $P$ $2n$ $n+1$ $\emptyset$

Sasho Nikolov
sumber

Wow, ide yang sangat sederhana! Terima kasih - Saya akan memikirkan apakah ini terlihat optimal atau tidak :)

jkff

Ini sebenarnya bahkan kurang dari w log n, karena jumlah panjang rantai adalah n. Saya kira maksimum sekitar w log (n / w).

jkff

OK, untuk pesanan linier ini memberikan pencarian biner, untuk kisi subset ini memberikan log C (n, n / 2) (2 ^ n / C (n, n / 2)) ~ exp (n) * n. Tidak terlalu cepat, tetapi juga tidak terlihat terlalu suboptimal, karena mungkin ada banyak jawaban. Namun untuk menemukan satu yang maksimal bagian, Anda perlu biner mencari lebih dari hanya salah satu rantai - ini adalah besar dan saya sekarang menyebut diriku bodoh karena tidak memikirkan hal itu. Terima kasih lagi!

jkff

2

Saya pikir rantai disjoint memberi Anda batas bawah setidaknya (untuk algoritma deterministik). Pikirkan musuh yang "menyembunyikan" satu solusi dalam rantai terakhir. Batas bawah acak dari harus mengikuti dari prinsip minimum Yao. Menemukan elemen tunggal dengan kompleksitas mungkin menarik.

w

$w$

w + \log n

$w + \log n$

Ω (w)

$\Omega(w)$

w + \log n

$w + \log n$

Sasho Nikolov

1

@YanKingYin Kisi tidak bisa menjadi penyatuan (lebih dari satu) rantai terpisah, karena masing-masing dua elemen harus memiliki supremum. Poset adalah penyatuan rantai terputus-putus jika dapat dipartisi sehingga elemen-elemen dari bagian yang berbeda tak tertandingi dan elemen-elemen dalam bagian yang sama menerima urutan total.

Sasho Nikolov

9

Jika adalah pohon, maka ada algoritma waktu polinomial yang membangun pohon keputusan yang optimal. $P$

Generalisasi Pencarian Biner: Pencarian di Pohon dan Pesanan Sebagian Seperti Hutan

ilyaraz
sumber

8

Satu makalah baru-baru ini oleh Daskalakis et al menunjukkan bahwa untuk poset ukuran dan lebar , elemen minimal dapat ditemukan dalam waktu . Yang menarik adalah bahwa dalam abstrak mereka, kata mereka $n$ $w$ $O(wn)$

Ini juga akan menarik untuk menemukan struktur data statis dan dinamis yang efisien yang memainkan peran yang sama untuk pesanan parsial yang menumpuk dan pohon pencarian biner bermain untuk total pesanan.

Suresh Venkat
sumber

Heh, terdengar tidak terlalu menginspirasi dibandingkan dengan log (n) :) tapi terima kasih lagian!

jkff

Tapi itu intinya. Tanpa struktur data, Anda tidak bisa mendapatkan log dan bahkan untuk set yang benar-benar dipesan, karena yang dapat Anda lakukan hanyalah memindai. Sebenarnya ini adalah pertanyaan yang sangat bagus untuk mencoba dan menemukan padanan BST.

Suresh Venkat

Nah - saya sedang berbicara tentang kompleksitas dalam hal jumlah evaluasi predikat P, bukan predikat perbandingan.

jkff

1

Dalam arti ya, tapi itu jauh dari jawaban yang lengkap - misalnya tidak memberikan pembagian dua untuk kasus 1d atau 2d :) apa yang Anda sarankan untuk dilakukan dengan root?

jkff

1

Belum yakin. berpikir keras. Tapi itu pertanyaan yang sangat bagus.

Suresh Venkat

4

Jika S adalah bagian dari input, maka masalah menemukan elemen maksimal sudah menjadi `` NP-hard '' (jika kita memikirkan kisi sedemikian sehingga elemen-elemennya adalah n string yang agak panjang), misalnya Anda dapat mengatakan jika CNF (x) tidak benar dan CNF (y) berlaku untuk beberapa CNF tetap. $x<y$

Juga, mungkin ada banyak elemen maksimal yang memuaskan P, jadi bahkan untuk mengeluarkan semuanya mungkin butuh waktu lama, jadi saya pikir hanya ada harapan untuk menemukan satu yang maksimal.

Secara umum, pencarian biner berfungsi jika Anda dapat memilih elemen secara rekursif sehingga setelah Anda dibiarkan dengan elemen-elemen di atas, atau elemen-elemen di atas dihapus, dan di setiap set seperti itu rasio tetap dari elemen-elemen dihapus.

Misalnya. jika S adalah grid dimensi tetap, maka ada algoritma cepat: Selalu membagi dua satu koordinat sambil menjaga yang lain minimal, jadi tanyakan misalnya pada langkah pertama (n / 2,0, ..., 0).

Salah satu teorema terkait yang penting adalah teorema titik tetap Tarski, di mana alih-alih P Anda memiliki pemetaan monoton dari kisi ke dirinya sendiri. Teorema mengatakan bahwa titik tetap membentuk kisi. Kami membuktikan dengan Jaroslaw Byrka dan Paul Duetting bahwa dalam pengaturan ini jika kisi adalah grid d-dimensi, maka Anda dapat menemukan titik tetap di sekitar waktu di mana algoritma adalah generalisasi sederhana dari pencarian biner. $n^d$

domotorp
sumber

Saya khawatir saya tidak mengerti paragraf pertama. Dalam pengurangan Anda, apakah Anda memiliki semua string n-bit di poset S dan apakah mereka diberikan sebagai bagian dari input? Jika demikian, kita dapat melewati semua string dalam waktu polinomial.

Yoshio Okamoto

1

@YoshioOkamoto: Saya pikir asumsi dalam paragraf itu adalah bahwa perbandingan dalam S diberikan sebagai sirkuit Boolean. (Tapi itu tidak ada hubungannya dengan pencarian di poset dan karena itu tidak menarik bagi saya.)

Tsuyoshi Ito

@ Tsuyoshi: Terima kasih. Itu sangat masuk akal.

Yoshio Okamoto

4

Untuk masalah menemukan semua elemen maksimal atas kisi himpunan himpunan bagian , ini sama dengan inferensi eksak dari fungsi boolean positif dari variabel boolean. Jika Anda hanya peduli dengan jumlah evaluasi (bukan kompleksitas komputasi), Anda dapat menemukan survei di Penambangan Data dan Penemuan Pengetahuan melalui Metode Berbasis Logika , Bab 10, bagian 10.2.4, atau dalam paragraf terakhir dari bagian 6.1 dari artikel ini , yang saya tunjukkan dengan jawaban ini (berhati-hatilah, sisa artikel ini membahas kompleksitas komputasi, bukan hanya kompleksitas mengevaluasi ). $P$ $2^{[n]}$ $n$ $P$ $P$

a3nm
sumber

Generalisasi pencarian biner untuk poset?

Jawaban: