Algoritma pencarian subset

9

Misalkan saya memiliki daftar dari himpunan bagian dari . Saya dapat melakukan preprocessing pada daftar ini jika perlu. Setelah preprocessing ini, saya diberikan satu set . Saya ingin mengidentifikasi set dengan . $\cal X$ $\{1, ..., n\}$ $A \subseteq \{1, ..., n \}$ $B \in \mathcal X$ $B \subseteq A$

Algoritma yang jelas (tanpa preprocessing apa pun) membutuhkan waktu - Anda cukup menguji terhadap setiap secara terpisah. Adakah yang lebih baik dari ini? $O(n |\cal X|)$ $A$ $B \in \mathcal X$

Jika ini membantu, Anda dapat mengasumsikan bahwa, untuk apa pun , jumlah total kecocokan dibatasi oleh sesuatu seperti . $A$ $B \in \mathcal X$ $O(1)$

ds.algorithms ds.data-structures David Harris
sumber

3

Ini bukan jawaban. Ini pengamatan sederhana namun panjang. Semoga bermanfaat.

Versi keputusan masalah Anda adalah: Apakah berisi subset dari ? $\cal X$ $A$

Masalah ini terkait dengan masalah mengevaluasi fungsi monoton boolean dari variabel. Subset dari setara dengan bitstring, sehingga keluarga setara dengan fungsi boolean dari variabel. Diberikan fungsi , kita dapat mendefinisikan fungsi monoton paling kecil yang tidak lebih besar dari , yaitu $n$ $\{1,\ldots,n\}$ $n$ $\cal X$ $f$ $n$ $f$ $f$ . Masalah aslinya kemudian dikurangi menjadi evaluasi . Sebaliknya, masalah mengevaluasi fungsi monoton boolean dapat dikurangi menjadi masalah asli, baik secara naif dengan mengambil atau dengan memilih yang membuat lebih kecil. $g(y)=(\exists x\subseteq y,\,f(x))$ $g(A)$ $f=g$ $f$ $\cal X$

Dalam praktiknya, BDD cenderung bekerja dengan baik. Jadi salah satu pendekatan yang mungkin adalah membangun BDD untuk , berasal dari itu BDD untuk , dan kemudian mengevaluasi . Ukuran rata-rata BDD untuk harus , karena ada banyak fungsi boolean monoton . Oleh karena itu, secara teori ini adalah solusi buruk. $f$ $g$ $g$ $g$ $\Omega\left(\binom{n}{n/2}\right)$

Tetapi (1) analisis yang lebih baik mungkin dilakukan dan (2) mungkin ada perubahan pada pendekatan ini yang membuatnya lebih baik. Sebagai contoh, saya sama sekali tidak menggunakan korelasi antara ukuran dan ukuran BDD . (Pasti ada korelasi, tetapi saya tidak tahu apakah itu sederhana atau dapat digunakan di sini.) $\cal X$ $g$

Untuk kelengkapan, algoritma sederhana untuk menghitung BDD untuk dari BDD untuk adalah sebagai berikut. Di sini adalah standar atau operasi pada BDD. $g$ $f$

m (x ? f_{1} : f_{0}) = x ? (m (f_{0}) \lor m (f_{1})) : m (f_{0})

$m(x?f_1:f_0)=x?(m(f_0)\lor m(f_1)):m(f_0)$

\lor

$\lor$

Radu GRIGore
sumber

2

Bukankah ini kurang lebih sama dengan menghitung ulang jawaban untuk setiap subset dari , menyimpan semua hasil dalam pohon biner ukuran , dan kemudian mencari ke kanan hasil (dalam waktu ) ketika Anda diberi ?

{1, 2, . . ., n}

$\{1,2,...,n\}$

2^{n}

$2^n$

O (n)

$O(n)$

A

$A$

mjqxxxx

Menggunakan ruang eksponensial untuk menyimpan data pra-pemrosesan terdengar seperti menipu saya, meskipun tidak dilarang dalam pertanyaan. Tetapi saya mungkin bias terhadap Gereja Kompleksitas Kasus Terburuk.

Tsuyoshi Ito

mjqxxxx dan Tsuyoshi: Saya setuju dengan Anda berdua. Saya menulis ulang teks sehingga, saya harap, lebih jelas bahwa saya setuju. :)

Radu GRIGore

3

Mungkin Anda dapat menggunakan teknik "pencarian informasi": pada fase preprocessing, buat indeks terbalik (dalam kasus Anda, array bidimensional sudah cukup) yang memetakan elemen ke set di yang berisi itu: . $n \times | {\cal X}|$ $x_i \in \{1,...,n\}$ $\cal X$ $inv(x_i)= \{ X_j \in {\cal X} \; | \; x_i \in X_j \}$

Mendirikan sebuah array integer panjang. $occ$ $|\cal X|$

Kemudian untuk setiap ambil , dan untuk setiap lakukan $y_i \in A$ $inv(y_i)$ $X_j \in inv(y_i)$ $occ[j] = occ[j]+1$

Pada akhirnya set yang Anda butuhkan adalah yang . $|X_j|=occ[j]$

Anda dapat mempercepat proses secara sewenang-wenang (dengan biaya ruang eksponensial) dengan mengindeks dua elemen atau lebih secara bersamaan.

Marzio De Biasi
sumber

Algoritma pencarian subset

Jawaban: