Pairwise Prioritätswarteschlange

Question

I einen Satz von A ‚s und einen Satz von B‘ s, die jeweils mit einem zugeordneten numerischen Priorität, wobei jede A grundsätzlich einige oder alle B ‚s und umgekehrt, und meine Hauptschleife entsprechen kann, besteht von:

Nehmen Sie die besten A und B in der Reihenfolge der Priorität, und tun Sie Dinge mit A und B.

Der offensichtlichste Weg, dies zu tun, ist mit einer einzelnen Prioritätswarteschlange von (A,B) Paaren, aber wenn es 100.000 A ‚s und 100.000 B‘ s ist dann die Menge der O(N^2) Paare nicht in dem Speicher passen (und Scheibe zu langsam).

Eine andere Möglichkeit ist für jede A, Schleife durch alle B. Dies bedeutet jedoch, dass die globale Prioritätsbestellung nur A ist und ich wirklich die Priorität beider Komponenten berücksichtigen muss.

(Die Anwendung ist Theorembeweisen, wo die oben genannten Optionen das Paar Algorithmus und die gegebene Klausel Algorithmus jeweils genannt werden, die Mängel von jedem bekannt sind, aber ich habe keinen Hinweis auf eine gute Lösung gefunden.)

Eine Art von Zwei-Ebenen-Prioritätswarteschlange scheint angezeigt, aber es ist nicht klar, wie dies ohne die Verwendung entweder O(N^2) Speicher oder O(N^2) Zeit im schlimmsten Fall zu tun.

Gibt es eine bekannte Methode, dies zu tun?

Erläuterung: jeder A muss mit allen entsprechenden B 's verarbeitet werden, nicht nur einer.

Answer 1

Vielleicht gibt es etwas, das ich nicht, aber das Verständnis,

Warum nicht die A hält und bs in getrenntem Haufen, get_Max auf jedem des Haufens, tun Sie Ihre Arbeit, nehmen Sie jeden max von seinem zugehörigen Haufen und weiter?

Answer 2

Sie haben also eine Menge von A's und eine Menge von B's, und Sie müssen ein Paar (A, B) aus dieser Menge auswählen, so dass ein f (a, b) das höchste aller anderen ist (A , B) Paar.

Dies bedeutet, dass Sie entweder alle möglichen (A, B) Paare speichern und sortieren können, und wählen Sie jedes Mal die höchste durch die Schleife (O (1) pro Iteration aber O (N * M) Speicher).

Oder Sie könnten alle möglichen Paare durchlaufen und das aktuelle Maximum verfolgen und dieses verwenden (O (N * M) pro Iteration, aber nur O (N + M) Speicher).

Wenn ich Sie richtig verstehe, ist das, was Sie fragen.

Ich denke, es hängt sehr viel von f() ab, ob es einen besseren Weg gibt, es zu tun.

Wenn f (a, b) = a + b, dann ist es offensichtlich sehr einfach, das höchste A und das höchste B sind was du willst.

Answer 3

Sie könnten zuerst mit den besten Paaren umgehen, und wenn nichts Gutes auftaucht, wischen Sie den Rest mit dem gegebenen Klauselalgorithmus der Vollständigkeit halber auf. Dies kann zu doppelter Arbeit führen, aber ich würde wetten, dass dies unbedeutend ist.

Haben Sie eine geregelte Paramodulation oder Superposition in Betracht gezogen?

Answer 4

Ich denke, Ihre ursprüngliche Idee wird funktionieren, Sie müssen nur Ihre As und Bs in separaten Sammlungen und nur Verweise auf sie in Ihrer Warteschlange priorisieren. Wenn jede Referenz 16 Bytes benötigt (nur um eine Zahl auszuwählen), benötigen 10.000.000 A/B-Referenzen nur ~ 300M. Angenommen, Ihr As und Bs selbst sind nicht zu groß, sollte es praktikabel sein.

Answer 5

Es scheint, dass die Elemente in A eine individuelle Priorität haben, die Elemente in B eine individuelle Priorität haben und die (A, B) Paare eine kombinierte Priorität haben. Nur die kombinierte Priorität ist wichtig, aber hoffentlich können wir die einzelnen Eigenschaften auf dem Weg nutzen. Es gibt jedoch auch eine übereinstimmende Beziehung zwischen Elementen in A und Elementen in B mit unabhängiger Priorität.

Ich nehme an, dass für alle a in A, b1 und b2 in B, so dass Match (a, b1) und Match (a, b2), dann Priorität (b1)> = Priorität (b2) CombinedPriority (a, b1)> = Kombinierte Priorität (a, b2).

Beginnen Sie nun damit, B in absteigender Reihenfolge zu sortieren. Sei B (j) das j-te Element in dieser sortierten Reihenfolge an. Auch soll A (i) das i-te Element von A anzeigen (das in einer sortierten Reihenfolge sein kann oder nicht).

Sei nextb (i, j) eine Funktion, die den kleinsten j '> = j findet, so dass Match (A (i), B (j')). Wenn kein solches j existiert, gibt die Funktion null (oder einen anderen geeigneten Fehlerwert) zurück. Die Suche nach j 'kann nur eine Schleife von j nach oben beinhalten, oder wir können etwas schneller machen, wenn wir mehr über die Struktur der Match-Relation wissen.

Erstellen Sie eine Prioritätswarteschlange Q, die (i, nextb (i, 0)) für alle Indizes i in A enthält, so dass nextb (i, 0)! = Null ist. Die Paare (i, j) in Q sind nach CombinedPriority geordnet (A (i), B (j)).

Jetzt nur Schleife, bis Q leer ist. Ziehen Sie das Paar mit der höchsten Priorität (i, j) heraus und bearbeiten Sie (A (i), B (j)) entsprechend. Dann füge (i, nextb (i, j + 1)) wieder in Q ein (es sei denn nextb (i, j + 1) ist null).

Insgesamt dauert dies im schlechtesten Fall, in dem alle Paare übereinstimmen, O (N^2 log N). Im Allgemeinen benötigt man O (N^2 + M log N), wobei M die Anzahl der Übereinstimmungen ist. Die N^2-Komponente kann reduziert werden, wenn es einen schnelleren Weg zum Berechnen von nextb (i, j) gibt, der einfach nach oben läuft, aber dies hängt von der Kenntnis der Übereinstimmungsbeziehung ab.

(In der obigen Analyse, nahm ich sowohl A als auch B der Größe N. waren die Formeln leicht modifiziert werden könnten, wenn sie unterschiedlich groß sind.)

Sie schien etwas besser als O (N^2 zu wollen) Zeit im schlimmsten Fall, aber wenn Sie jede Übereinstimmung verarbeiten müssen, dann haben Sie eine untere Grenze von M, die selbst N^2 sein kann. Ich denke nicht, dass Sie besser als O (N^2 logN) Zeit schaffen können, es sei denn, es gibt eine spezielle Struktur für die kombinierte Priorität, die es Ihnen ermöglicht, eine Proreichenwarteschlange besser als log-N zu verwenden.