Iteration über Vektoren in der Reihenfolge ihrer Wahrscheinlichkeit auf kleinem Raum

12

Man betrachte einen dimensionalen Vektor v, wobei v i{ 0 , 1 } ist . Für jedes i kennen wir p i = P ( v i = 1 ) und nehmen an, dass v i unabhängig sind. Gibt es unter Verwendung dieser Wahrscheinlichkeiten einen effizienten Weg, um binäre n- dimensionale Vektoren zu iterieren, um mit größter Wahrscheinlichkeit die geringste Wahrscheinlichkeit (mit willkürlichen Auswahlmöglichkeiten für Bindungen) zu erzielen, indem Raum-Sublinearität in der Ausgabegröße verwendet wird? nvvi{0,1}ipi=P(vi=1)vin

Nehmen wir zum Beispiel . Der wahrscheinlichste Vektor ist ( 1 , 0 , 1 ) und der am wenigsten wahrscheinliche ist { 0 , 1 , 0 } . p={0.8,0.3,0.6}(1,0,1){0,1,0}

Für sehr kleine könnten wir jeden der 2 n Vektoren mit seiner Wahrscheinlichkeit bezeichnen und einfach sortieren, aber dies würde natürlich immer noch keinen sublinearen Raum verwenden.n2n

Eine enge Variante dieser Frage wurde zuvor unter /cs/24123/how-to-iterate-over-vectors-in-order-of-probability gestellt .

Lembik
quelle
Gibt es einen Grund, warum Sie die Folgefrage dort nicht gestellt haben? Geht es hier hauptsächlich darum, dies im sublinearen Raum zu tun?
Suresh Venkat
@SureshVenkat Ja, das Problem liegt ausschließlich im sublinearen Raum (in der Ausgabegröße). Ich habe es hier gefragt, da ich denke, dass die Frage sehr schwierig sein kann.
Lembik
Um dies in Raum und Zeit zu lösen, scheinen Techniken erforderlich zu sein, die SUBSET-SUM ähneln (schnell zu wissen, welche Summen von Subsets unterschiedliche Summen annähernd aufheben). Daher ist es unwahrscheinlich, dass es eine schnelle Lösung gibt. poly(n)
Geoffrey Irving
@GeoffreyIrving Glaubst du, diese Intuition kann formalisiert werden?
Lembik

Antworten:

9

Das Folgende gibt einen Algorithmus an, der ungefähr Zeit und 2 n / 2 Raum verwendet.2n2n/2

Betrachten wir zunächst das Problem des Sortierens der Summen aller Teilmengen von Elementen.n

Betrachten Sie dieses Unterproblem: Sie haben zwei sortierte Listen mit der Länge und möchten eine sortierte Liste der paarweisen Summen der Zahlen in den Listen erstellen. Sie möchten dies in ungefähr 0 ( m 2 ) Zeit (der Ausgabegröße), aber im sublinearen Raum tun . Wir können O ( m ) Raum erreichen. Wir führen eine Prioritätswarteschlange und ziehen die Summen in aufsteigender Reihenfolge aus der Prioritätswarteschlange heraus.mO(m2)O(m)

Die Listen seien und b 1b m , in aufsteigender Reihenfolge sortiert. Wir nehmen die m Summen a i + b 1 , i = 1 m und stellen sie in eine Prioritätswarteschlange.a1amb1bmmai+b1i=1m

Wenn wir nun die kleinste verbleibende Summe aus der Prioritätswarteschlange ziehen, setzen wir , wenn j < m , die Summe a i + b j + 1 in die Prioritätswarteschlange. Der Raum wird von der Prioritätswarteschlange dominiert, die immer höchstens m Summen enthält. Und die Zeit ist O ( m 2 log m ) , da wir O ( log m ) für jede Prioritätswarteschlangenoperation verwenden. Dies zeigt, dass wir das Teilproblem in O ( m 2 lösen könnenai+bjj<mai+bj+1mO(m2logm)O(logm) Zeit und O ( m ) Raum.O(m2logm)O(m)

Um nun die Summen aller Teilmengen von Zahlen zu sortieren , verwenden wir einfach diese Unterroutine, bei der die Liste a i die Menge von Teilmengen der ersten Hälfte der Elemente ist und die Liste b i die Menge von Teilmengen ist der zweiten Hälfte der Artikel. Wir können diese Listen mit demselben Algorithmus rekursiv finden.naibi

Wir werden nun das ursprüngliche Problem betrachten. Sei der Satz von Koordinaten, die 0 sind , und S 1 der Satz von Koordinaten, die 1 sind . Dann i S 0 p ( v i = 0 ) i S 1 p ( v i = 1 )S00S11

iS0p(vi=0)iS1p(vi=1)=1inp(vi=0)iS1p(vi=1)p(vi=0)=1inp(vi=0)exp(iS1logp(vi=1)p(vi=0)).

Das Sortieren dieser Zahlen ist dasselbe wie das Sortieren der Zahlen , daher haben wir das Problem auf das Sortieren der Summen von Teilmengen von n Elementen reduziert .iS1logp(vi=1)logp(vi=0)n

Peter Shor
quelle
Gibt es plausibel eine Reduzierung, die eine Poly-Raum-Lösung unplausibel machen würde?
Lembik
Sie werden wahrscheinlich keine Lösung erhalten, die weniger als Zeit benötigt, da dies die Größe der Ausgabe ist (und meine Lösung benötigt n2n Zeit). Ich habe jedoch keine gute Untergrenze für den Weltraum. n2n
Peter Shor
Vielen Dank. Ich meinte natürlich nicht Polyzeit, sondern eher etwas Lineares in der Ausgabegröße und im Polyraum.
Lembik
4

Wir können das im Raum (wenn uns die Laufzeit egal ist).O(n)

  1. Für eine gegebene Zeichenkette können wir im Raum O ( n ) die Anzahl r ( x ) von Zeichenketten berechnen , die wahrscheinlicher als x sind ; das heißt, die Anzahl von x ' st p ( x 'x{0,1}nO(n)r(x)xx : gehe einfach über alle x '{ 0 , 1 } n und zähle die Anzahl von x ' stp(x)>p(x)x{0,1}nx . Beachten Sie, dass r ( x ) die fortlaufende Nummer der Zeichenfolge x in der Ausgabe ist.p(x)>p(x)r(x)x
  2. Für jedes können wir x mit r ( x ) = k im Raum O ( n ) finden : gehe über alle x { 0 , 1 }kxr(x)=kO(n) , für jedes x berechnen Sie r ( x ) , stoppen Sie und geben Sie x aus, wenn r ( x ) = k .x{0,1}nxr(x)xr(x)=k
  3. Jetzt gehe einfach alle von 0 durchk0 zu , für jedes k Druck x mit r ( x ) = k .2n1kxr(x)=k

(Wir sollten uns auch um mögliche Bindungen kümmern, aber das ist nicht schwierig.)

Yury
quelle
Vielen Dank. Das ist jedoch ein ziemlich langsamer Algorithmus :)
Lembik
0

Bearbeiten: Diese Antwort ist falsch. Siehe Kommentare für Details. ~ Gandaliter

Linear im Ausgabemittel . Ich denke, der offensichtliche Algorithmus verwendet nur den O ( n ) Raum, abgesehen von der Ausgabe selbst natürlich.O(2n)O(n)

  1. Nimm die Liste mit den Paaren und sortieren Sie sie nach | 0,5 - p i | größte zuerst.(i,pi)|0.5pi|

  2. Definieren Sie eine doppelt rekursive Funktion, die eine Liste solcher Paare und einen teilweise gefüllten Vektor aufnimmt und den Wert von v i auf 1 setzt, wenn p i > 0,5 ist , undvvi1pi>0.5andernfalls auf 0 , und rekursiv (unter Verwendung des Endes der Liste und v ) , kippt dann v i und rekursiert erneut. Wenn die Liste leer ist, wird stattdessen v ausgegeben.0vviv

  3. Rufen Sie diese rekursive Funktion für die sortierte Liste und einen leeren Vektor auf.

Die Intuition ist, dass Sie die Werte der sichersten Elemente im Vektor zuerst festlegen (diejenigen, deren Wahrscheinlichkeiten am nächsten bei und 1 liegen ) und den Vektor auf diese Weise ausfüllen und mit denen abschließen, deren Wahrscheinlichkeiten am nächsten bei 0,5 liegen . Jeder mögliche Wert, den der gesamte Vektor annehmen könnte, wird in der Reihenfolge seiner Wahrscheinlichkeit ausgegeben.010.5

Die Laufzeit ist . Dies ist die Untergrenze, da dies die Länge der Ausgabe ist. Die Raumkomplexität ist O ( n ), weil die Sortierung nicht mehr als das erfordert, und die rekursive Länge ist die Länge des Vektors, die n ist . Ich glaube, dass dies auch die Untergrenze ist, da es für jeden Zeitschritt beim Ausführen des Algorithmus einen anderen Speicherzustand geben muss und die Zeitkomplexität O ( 2 n ) ist .O(2n)O(n)nO(2n) -Zustände im Speicher sind erforderlich, um O ( 2 n ) aufzulisten.O(n)O(2n)Zeitschritte. Daher ist dieser Algorithmus im ungünstigsten Fall für die Komplexität optimal.

Gandaliter
quelle
Die andere Antwort ist sicherlich anders, da sie eine Prioritätswarteschlange erfordert und daher Speicherplatz verwendet. Θ(2n)
Lembik
Vielen Dank. Ich habe es offensichtlich nicht sorgfältig genug gelesen! Ich habe meine Antwort bearbeitet.
Gandaliter
3
Sind Sie sicher, dass diese Lösung funktioniert? Ich konnte die Details der doppelten Rekursion nicht herausfinden (Pseudocode würde helfen!), Aber ich sehe nicht, wie das funktionieren könnte. Insbesondere scheint Ihre Lösung lokal zu sein: Wenn sie sie jetzt 2 n - 1 Antworten mit v 1 = 1 aus . Aber die tatsächlichen Antworten sollten nicht so aussehen. Soweit ich Ihre Lösung verstanden habe, scheint sie sogar für den einfachsten Fall, in dem alle p i = 0,5 sind, zu scheitern . v1=12n1v1=1pi=0.5
Möbius Knödel
Du hast recht, das funktioniert nicht. Es tut uns leid!
Gandaliter