Ricerca Binary-ISH attraverso set parzialmente ordinato

Question

Ho una funzione interessante. Ci vogliono sottoinsiemi di {1, ..., n} con numeri interi positivi, I.e. $ f: P ([N]) \ RightArrow Z ^ + $ . So che se S è un sottoinsieme di s ', $ f (s) . Inoltre, se S e S 'hanno la stessa cardinalità, l'ordine indotto da F è lessicografico, quindi ad esempio $ f (\ {1,2,4}) . Dato un valore z , vorrei trovare s tale che $ f (s) <= z $ e $ f (s) <= f (t) <= z $ implica $ f (s)= f (t) $ - cioè, voglio fare una ricerca sul reticolo di sottoinsiemi di [n].

Se sapessi che l'ordine fosse perfettamente lessicografico, utilizzerei una semplice ricerca binaria. Non lo so, e credo che non sia (ad esempio, $ f (\ {1,2,3,4,5,6 \}) $ è probabilmente maggiore di $ f (\ {7 \}) $ ). C'è un buon o (n) algoritmo per fare questa ricerca sul poset? Ovviamente per N di qualsiasi dimensione apprezzabile devo calcolare F on-the-fly e non può fare affidamento su memoria in memoria.

Chiarimento dopo una discussione nei commenti: La particolare $ f $ Ho a che fare è additivo è specificamente, $ f (s)=sum_ {k \ in s} g (k) + f (\ styleyset) $ , con $ G $ una funzione monotonicamente crescente. Questo potrebbe essere più facile del caso generale (che è anche interessante, ma non il mio particolare problema).

Answer 1

Ecco un semplice algoritmo che funziona in $ o (n ^ 2) $ tempo e $ o (n) $ spazio, assumendo che $ f (\ styleyset) $ , $ f (\ {1 \}) $ , $ f (\ {2 \}) $ , $ \ cdots $ , $ f (\ {n \}) $ sono forniti in un array.

L'idea di avviamento è la stessa cosa che è stata data dall'OP nel suo commento. "Cercheremo sui sottoinsiemi di dimensioni K utilizzando l'ordine lessicografico, per ogni $ k $ da $ 0 $ a $ N $ . Mantieni quello con il miglior valore di $ f $ . "

Il problema è quindi come cercare il miglior valore di $ f $ sui sottoinsiemi di dimensioni $ k $ , denominato $ B_K $ , in $ o (n) $ tempo. Invece della ricerca binaria, controlleremo se $ N $ , $ n-1 $ , \ cdots, $ 1 $ dovrebbe essere incluso nel miglior sottoinsieme uno per uno, prendendo il vero vantaggio dell'ordine lessicografico sui sottoinsiemi.

.
1. Inizializza $ B_K= F (\ Emptyset) $ . $ \ B_K $ sarà il miglior valore sui sottoinsiemi di dimensioni $ k $ Alla fine di questa procedura .
2. Inizializza $ conteggio= 0. $ $ \ conteggio $ è il numero di elementi che abbiamo incluso nel miglior sottoinsieme fino ad ora.
3. Check $ f (\ {n \}) $ . Se $ B_K + F (\ {N \}) + f ({1, 2, \ Cdots, K-count -1 \}) \ le z $ , $ N $ deve essere incluso. Aggiungi $ f (\ {n \}) $ a $ B_K $ e aggiungi 1 a $ conteggio $ .
4. Check $ f (\ {n-1 \}) $ . Se $ B_K + F (\ {N-1 \}) + f (\ {1, 2, \ Cdots, K-Count-1 \}) \ le z $ , $ N-1 $ deve essere incluso. Aggiungi $ f (\ {n-1}) $ a $ B_K $ e aggiungi 1 a < Span Class="Math-Container"> $ Count $ .
5. e così via.
6. fino a quando non abbiamo controllato $ f (\ {1 \}) $ o $ conteggio== k $ < / span>.

Potremmo chiederci, se prenderà $ o (n) $ per calcolare ogni $ f (\ {1 , 2, \ cdots, k-count-1 \}) $ , calcolo di ogni $ B_K $ da solo prenderà la $ O (n * n) $ tempo. Tuttavia, poiché $ f $ è additivo, possiamo calcolare tutte le somme di prefisso di $ f (\ {1 \}) $ , $ f (\ {2 \}) $ , $ \ cdots $ , < Span Class="Math-Container"> $ f (\ {n \}) $ in anticipo in $ o (n) $ tempo. Quindi ci vuole $ o (1) $ per accedere a ciascuna somma del prefisso.

Dal momento che cerca $ B_K $ prende $ o (n) $ tempo, per ogni classe di span="container math"> $ k $ da $ 0 $ a $ n $ , Il tempo di esecuzione totale è $ o (n ^ 2) $ .

---

.

La descrizione al di sopra dell'algoritmo salta il caso più semplice quando $ f (\ styleyset) \ gt z $ . In tal caso, l'algoritmo dovrebbe restituire che non esiste un sottoinsieme del genere.