Binäre Ish-Suche durch teilweise bestellte Set

Question

Ich habe eine interessante Funktion. Es nimmt Teilmengen von {1, ..., n} bis positive Ganzzahlen, d. H. $ F: P ([N]) \ Rightarrow Z ^ + $ . Ich weiß, dass, wenn S ein Teilset von S ', $ f (S) ist . Wenn S und S 'dieselbe Kardinalität haben, ist die von F induzierte Reihenfolge lexikologisch, so dass zum Beispiel $ F (\ {1,2,4 \}) . Angesichts eines Werts z möchte ich s so finden, dass $ f (s) <= z $ und $ F (S) <= f (t) <= Z $ impliziert $ f (s)= f (t) $ - das heißt, ich möchte eine Suche auf dem Gitter von Subsets von [n] machen.

Wenn ich wusste, dass die Bestellung perfekt lexikologisch war, würde ich eine einfache binäre Suche verwenden. Das weiß ich nicht, und ich glaube, es ist nicht (z. B. $ f (\ {1,2,3,4,5,6 \}) $ ist möglicherweise größer als $ F (\ {7 \}) $ ). Gibt es einen guten O (N) -Algorithmus, um diese Suche auf dem Poset zu tun? Natürlich muss ich für n der nennenswerten Größe f on-the-fliege berechnen und kann sich nicht auf den lagerung im Speicher verlassen.

Klarstellung nach einer Diskussion in den Kommentaren: Der jeweilige $ F $ Ich bin der Umgang mit Additiv - speziell, $ f (s)=sum_ {k \ In S} g (k) + f (\ emelesigset) $ , mit $ g $ eine monoton steigende Funktion. Dies kann einfacher sein als der allgemeine Fall (was auch interessant ist, aber nicht mein besonderes Problem).

Answer 1

Hier ist ein einfacher Algorithmus, der in $ O (N ^ 2) $ Zeit und $ O (N) ausgeführt wird $ Speicherplatz, vorausgesetzt, dass $ F (\ ENEPYSET) $ , $ F (\ {1 \}) $ , $ F (\ {2 \}) $ , $ \ cdots $ , $ F (\ {n \}) $ sind in einem Array angegeben.

Die Startidee ist ungefähr das Gleiche wie das, was das OP in seinem Kommentar gegeben hat. "Wir werden nach Subsets der Größe K mit der lexikografischen Reihenfolge suchen, für jeden $ K $ aus $ 0 $ zu $ N $ . Behalten Sie den mit dem besten Wert von $ F $ . "

Das Problem ist dann, wie Sie den besten Wert von $ F $ auf Subsets der Größe $ K $ , benannter $ b_k $ , in $ o (n) $ Zeit. Anstelle von binärer Suche prüfen wir, ob $ N $ , $ n-1 $ , \ CDOTs, $ 1 $ sollte in die beste Teilset nacheinander einbezogen werden, indem er den echten Vorteil der lexikografischen Reihenfolge auf Subsets einnimmt.

.
1. Initialisieren $ b_k= f (\ emesyset) $ . $ \ b_k $ ist der beste Wert auf subsets der größe $ k $ am Ende dieses Vorgangs .
2. initialisieren $ count= 0. $ $ \ count $ ist die Anzahl der Elemente, die wir haben bisher in der besten Teilmenge enthalten.
3. Check $ F (\ {n \}) $ . Wenn $ b_k + f (\ {n \ \}) + f (\ {1, 2, \ cdoten, k-count -1 \}) \ le z $ , $ N $ muss aufgenommen werden. Fügen Sie $ F (\ {n \}) $ auf $ B_K $ und fügen Sie 1 zu $ count $ .
4. Check $ F (\ {n-1 \}) $ . Wenn $ b_k + f (\ {n-1 \}) + f (\ {1, 2, \ Cdoten, k-count-1 \}) \ le z $ , $ n-1 $ muss einbeziehen. $ F (\ {n-1 \}) $ auf $ B_K $ und fügen Sie 1 zu $ count $ .
5. und so weiter.
6. , bis wir entweder geprüft haben, $ f (\ {1 \}) $ oder $ count== k $ < / span>.

wir könnten sich wundern, wenn es $ o (n) $ dauert, um jeden $ F (\ {1) zu berechnen , 2, \ cdoten, k-count-1 \}) $ , berechnen Jeder $ B_K $ allein wird $ O (n * n) $ Zeit. Da jedoch $ F $ Additiv ist, können wir alle Präfixsummen von $ F (\ {1 \}) berechnen $ , $ F (\ {2 \}) $ , $ \ cdots $ , < Span-Klasse="Math-Container"> $ F (\ {n \ \}) $ upfront in $ o (n) $ Zeit. Dann dauert es $ O (1) $ , um auf jede Präfixsumme zuzugreifen.

Da suche $ b_k $ in $ o (n) $ Time, für jede $ K $ aus $ 0 $ bis $ n $ , Die Gesamtlaufzeit ist $ O (N ^ 2) $ .

---

Die Beschreibung oben des Algorithmus überspringt den einfachsten Fall, wenn $ f (\ emesyet) \ gt Z $ . In diesem Fall sollte der Algorithmus zurückkehren, dass es keine solche Teilmenge gibt.