Prioritätswarteschlange für teilweise geordnete Prioritäten mit infima

16

Ich habe einige Objekte mit Priorität, die zusammengesetzt sind und nur teilweise geordnet sind . Ich muss die Objekte in der Reihenfolge dieser Priorität auswählen (dh jedes Mal einen minimalen Gegenstand erhalten). Aber anstatt die Bestellung willkürlich abzuschließen, wäre es mir lieber, wenn die Warteschlange so stabil wäre, dass sie, wenn es mehr als ein minimales Element gibt, das älteste zuerst zurückgeben sollte.

Gibt es eine Heap-Datenstruktur, die bei Teilbestellungen funktionieren würde? Oder eine Änderung der regulären Prioritätswarteschlange, um damit zu arbeiten? Die übliche Wahl für den Algorithmus, den ich benötige, ist einfacher Binär- oder 4-ary-Heap, aber das funktioniert nicht mit partieller Sortierung.

Die Prioritätswerte unterstützen:

  1. Teilbestellung mit Operation . Es ist eine teilweise Anordnung, so dass es möglich ist, dass a \ preccurlyeq b falsch ist und b \ preccurlyeq a auch falsch ist. In diesem Fall schreibe ich ein \ not \ lesseqgtr b .abbaa⋚̸b
  2. Die Suche nach infima (glb) und suprema (lub). inf(xi) ist das maximale y so dass yxi . Die Berechnung des Infimums von n Werten benötigt O(n) Zeit. Es gibt ein Infimum (und ein Supremum) jeder Menge.
  3. Eine lineare Erweiterung für die Teilbestellung könnte definiert werden. Die Verwendung für die Prioritätswarteschlange ist der einfache Ausweg, da der Algorithmus auf diese Weise funktioniert. Die Reihenfolge wirkt sich jedoch auf die Leistung aus, und die Reihenfolge des Einfügens sollte zur Vermeidung von Worst-Cases am besten sein.

Zusätzlich muss der Algorithmus, in dem ich dies verwenden möchte, das Minimum aller Prioritäten in der Warteschlange kennen.

Die Prioritäten haben eine reale Bedeutung, können sich jedoch ändern, sodass es nicht sinnvoll erscheint, sich auf andere Eigenschaften zu verlassen, die sie haben könnten.


Hinweis: Binäre Heaps funktionieren nicht bei Teilbestellungen. Nehmen Sie einen binären Heap mit a , b und c , wobei ac und a⋚̸b und a⋚̸c . Sie sind also in dieser Reihenfolge positioniert

     a (0)
   /   \
 b (1)   c (2)

Jetzt wird d eingefügt. Die nächste freie Position ist 3, das linke Kind von b , also bekommen wir

        a (0)
      /   \
    b (1)   c (2)
  /
d (3)

Wenn (was aus der Transitivität impliziert , aber nichts über und ) und , dann wird nicht mit getauscht , weil es nicht weniger ist. Aber es ist tatsächlich weniger als , aber es wird nicht damit verglichen, so dass jetzt die Haupthaufeninvariante nicht gilt; Top ist nicht minimal.dadcdbd⋚̸bdba

Ich vermute, dass ein Wald von Haufen, der dem Binomialhaufen ähnelt, zum Arbeiten gebracht werden könnte. Grundsätzlich ist es wichtig, immer neue Werte mit root zu vergleichen und nur vergleichbare Elemente miteinander zu verknüpfen. Es würde die Bäume im Wald zufällig dimensionieren und somit die Komplexität von der Anzahl der miteinander unvergleichbaren Mengen im Haufen abhängig machen. Ich vermute, dass die Komplexität nicht behoben werden kann (wir müssen weiter vergleichen, bis wir auf ein vergleichbares Element treffen). Vielleicht habe ich etwas verpasst, also lasse ich dies offen.


Hinweis: Die Reihenfolge ist unvollständig, und obwohl es Möglichkeiten gibt, eine lineare Erweiterung dafür zu definieren, gehört das Hinzufügen eines Zeitstempels und die Verwendung als sekundäres Kriterium nicht dazu. Angenommen, wir haben den Zeitstempel für jedes zugewiesen und die Reihenfolge als iff oder ( und . Dann nehmen wir an, wir haben verschiedene , , , so dass und . Dann undt(a)aababbat(a)t(b)abct(a)t(b)t(c)caabbc , aber , so ist die Beziehung nicht transitiv und daher überhaupt keine Ordnung. Diese Art der Erweiterung funktioniert nur bei schwachen, aber nicht bei partiellen Ordnungen.ca


Bearbeiten: Ich habe festgestellt, dass nicht nur das Infimum einer Gruppe definiert ist, sondern dass ich auch in der Lage sein muss, das Infimum der Elemente, die sich derzeit in der Warteschlange befinden, effizient abzurufen. Ich überlege nun, ob das Hinzufügen spezieller Knoten, die Infima von Teilbäumen enthalten, zu einer allgemeinen Heap-Struktur hilfreich wäre.

Jan Hudec
quelle
Haben Sie eine Warteschlange mit indizierter Priorität in Betracht gezogen?
@hulkmeister: Könnten Sie bitte erklären, wie die Indizierung der Warteschlange bei Teilbestellungen funktioniert (nein, einfacher Binär-Heap funktioniert bei Teilbestellungen nicht)?
1
Mein Gedanke war, dass, wenn zwei Elemente nicht vergleichbar sind, Sie den Index verwenden können, um die Reihenfolge der Einfügung zu verfolgen. Stellen Sie also die Priorität mit dem Index zusammen, und Sie haben eindeutige Schlüssel, die auch dann vergleichbar sind, wenn die Priorität nicht vorhanden ist. Wenn das so klingt, wie Sie es wollen, kann ich es in eine vollständige Antwort setzen.
1
@hulkmeister: Naja, das Problem ist viel tiefer. Wenn ein neues Element eingefügt wird, vergleicht die Prioritätswarteschlange es normalerweise mit einem Element. Aber wenn sie unvergleichlich sind, weiß es einfach nicht, wo es eingefügt werden soll. Und die Disambiguierung mit dem Index wird nicht funktionieren, weil sich der Index ändert und weil es wahrscheinlich sowieso keine Gesamtreihenfolge gibt, die mit der Priorität übereinstimmt.
Können Sie ein Beispiel für diesen Verbindungstyp nennen, und wenn es unvergleichlich ist? Kann man diese "unvergleichlichen" Werte als gleich betrachten? In diesem Fall können Sie sie in der Reihenfolge des Einfügens im selben Knoten speichern.

Antworten:

3

Obwohl das genaue Problem, das in der ursprünglichen Frage aufgeworfen wurde, schwierig zu sein scheint (und ich an einer Lösung für dieses Problem interessiert wäre, insbesondere für den infima-Findeteil). Ich wollte nur festhalten, dass, wenn die teilweise bestellte Menge tatsächlich aus Vektoren besteht, die eine Produktbestellung verwenden, und wenn es ausreicht, nur die Garantie zu haben, dass die Prioritätswarteschlange die Werte in einer Reihenfolge zurückgibt, die mit der teilweisen Bestellung "kompatibel" ist ( Das heißt, kleinere Elemente werden immer vor größeren Elementen zurückgegeben.

Die Idee besteht im Wesentlichen darin, eine topologische Anordnung der teilweise geordneten Menge zu finden. Das heißt, eine Gesamtreihenfolge ' ', so dass . Für Vektoren, die eine Produktreihenfolge verwenden, ist dies ziemlich einfach: Verwenden Sie einfach eine lexikografische Reihenfolge ' ', wobei die erste "Komponente" die Summe aller für die Produktreihenfolge verwendeten Komponenten ist (der Rest der Komponenten ist im Wesentlichen willkürlich). Sie können sich also auch an eine schwache Reihenfolge halten. Wir können dann sehen, dass und TabaTbS

a<bi(aibi) and i(ai<bi)(iai)<(ibi)aSb
a=bi(ai=bi)(iai)=(ibi)aSb,
und somit das . Wir können diese Reihenfolge also mit einer Prioritätswarteschlange verwenden und sicherstellen, dass kleinere Elemente (in der Produktreihenfolge) immer vor größeren Elementen extrahiert werden.abaSb
Jaspis
quelle
Es gibt viele weitere Möglichkeiten. Unter Verwendung einer der Komponenten Minimum, Maximum, jede Linearkombination mit mindestens nicht negativen Koeffizienten. Die Wahl der Erweiterung beeinflusst, wie schnell der Überlagerungsalgorithmus sein wird.
Jan Hudec
2

Was ist falsch daran, Ihre Teilbestellung abzuschließen?

Aber anstatt die Bestellung willkürlich abzuschließen, wäre es mir lieber, wenn die Warteschlange so stabil wäre, dass sie, wenn es mehr als ein minimales Element gibt, das älteste zuerst zurückgeben sollte.

Wenn Sie "älteste zuerst" bevorzugen, ist Ihre Bestellung effektiv abgeschlossen. "unvergleichliche" Gegenstände sind nach Alter vergleichbar.

Fügen Sie jedem Element einen Zeitstempel (oder eine andere monoton wachsende Ganzzahl) hinzu und verwenden Sie ihn, wenn ein "echter" Vergleich nicht möglich ist.


quelle
3
Das wäre toll, wenn es eine lineare Erweiterung der Teilbestellung geben könnte. Ist es aber nicht. Lassen Sie uns 3 verschiedene Werte in der Reihenfolge a , b , c einfügen , sodass c ≤ a und b mit beiden nicht vergleichbar sind. Die Erweiterung mit dem Zeitstempel in Füllungen a ≤ ‚b und b ≤‘ c , so von Transitivität jetzt a sollte kleiner sein als C , aber die tatsächliche Bestellung , dass widerspricht.
Vielleicht haben Sie es mit einer schwachen Reihenfolge verwechselt. Bei einer schwachen Reihenfolge bilden die unvergleichbaren Elemente Äquivalenzklassen, sodass Sie beliebige zusätzliche Kriterien hinzufügen können. Bei Teilbestellungen ist dies nicht möglich.
1

EDIT: Dies scheint ein interessantes Problem zu sein, und ich hatte ein wenig Nachforschungen darüber. Ich schlage vor, dass Sie Folgendes lesen:

  1. Darell Raymond. Teilordnungsdatenbanken, Dissertation, University of Waterloo.

Ich schlage vor, Sie lesen dieses Papier: Daskalakis, Constantinos, et al. "Sortieren und Selektieren in Posets." SIAM Journal on Computing 40.3 (2011): 597-622.

Die Autoren präsentieren hier eine Datenstruktur namens ChainMerge, die ein Poset und eine Kettenzerlegung des Posets in Ketten akzeptiert . Die Größe der Datenstruktur ist . Die Autoren präsentieren einen Algorithmus zum Finden der Minima, die in wobei eine Obergrenze für die Breite des Posets ist. ..Ich dachte vielleicht ist das interessant.qO(nq)O(wn)w

Hinweis: Ich habe eine vorherige naive Antwort gelöscht. Bitte klicken Sie auf Bearbeiten, um es zu sehen.

AJed
quelle
0

Meine Terminologie ist möglicherweise falsch. Bitte bearbeite meine Antwort direkt, um alle Probleme zu beheben, die du findest.


Zunächst müssen nicht miteinander vergleichbare Mengen an den Eingaben ermittelt werden.

Zum Beispiel kann es 5 Objekte geben, a, b, c, d, eaber ihre teilweise Anordnung bildet zwei getrennte Graphen:

  • a ≤ b ≤ c
  • d ≤ e
  • aber eines von {a, b, c}ist unvergleichlich mit einem von {d, e}.

Diese nicht miteinander vergleichbaren Mengen müssen zuerst erkannt werden, bevor die Objekte in einer geeigneten Datenstruktur gespeichert werden können. Dies kann mit einem Union-Suchalgorithmus erfolgen


Für die Effizienz muss das Einfügen eines neuen Objekts eine effiziente Methode zum Auffinden "der Liste vorhandener Objekte, die mit diesem neuen Objekt vergleichbar sind" aufweisen.


Nun innerhalb jeder Teilmenge (bzw. {a, b, c}und {d, e}) sollte die Minima werden gut definiert. (Für jede Untergruppe kann es aufgrund einer Teilordnung ein oder mehrere Minima geben.)

Ich sehe dies als gerichteten azyklischen Graphen . Der Versuch, ihn in einen Haufen zu stecken, scheint katastrophal.


Um die Minima aus dieser zusammengesetzten Datenstruktur zu extrahieren, müssen Sie im nächsten Schritt die Liste aller Minima aus allen Teilmengen abrufen, das mit dem frühesten Zeitstempel auswählen und dieses Objekt entfernen und zurückgeben.

rwong
quelle
Leider sehe ich keinen Weg, die Liste vergleichbarer Objekte effizient zu finden.
Teilweise geordnete Mengen können in der Tat als gerichtete azyklische Graphen angesehen werden. Aber eine, die durch die Adjazenztabelle (Funktion, tatsächlich) und nicht durch die Adjazenzliste gegeben ist. Es ist einfach, anhand der Adjazenzliste die Minima des Posets zu finden, für die Adjazenztabelle ist dies jedoch ein Problem.
Minima sind auch im Originalset gut definiert. Ich verstehe nicht, wie das Auffinden der verbundenen Komponenten helfen könnte, da es sich nicht um vollständige Diagramme handelt.
1
Sie scheinen anzunehmen, dass das Hasse-Diagramm ein Wald von unären Bäumen ist (entsprechend Pfadgraphen), aber die Frage besagt bereits, dass es sich um eine Produktbestellung handelt, also um ein mehrdimensionales Gitter.
Peter Taylor
0

Ein Projekt, an dem ich arbeite, weist ein ähnliches Problem auf (nebenbei verwende ich auch die Teilreihenfolge von Vektoren). Wir hatten bereits einen quadratischen Zeitalgorithmus zum Sortieren einer zufällig sortierten Liste, und ich entwickelte einen Einfügealgorithmus, indem ich sein Verhalten beobachtete, wenn nur ein Objekt außer Betrieb war. Wir wissen nicht, ob dies die schnellste mögliche Implementierung ist.

Hier ist ein Pseudocode.

class PartialOrderPriorityQueue
   q <- empty list
   method insert (n):
     for i <- 0 to (q.length - 1):
       if q[i] <= n:
         t <- q[i]
         q[i] <- n
         n <- t
     q.append(n)

   method pop():
     return q.remove(0)
Jeremy List
quelle
-1

Das übliche Heap-Verhalten besteht darin, den neuen Wert an die Rückseite anzuhängen und dann zu sichten, während der Vergleich größer als der übergeordnete Wert ist.

Wenn Sie einen Vergleich schreiben, der für Eltern und Kind den gleichen Wert zurückgibt, sind nicht vergleichbare Fälle wie für Eltern, die größer als Kind sind , sollte das Sichten immer noch am richtigen Punkt enden.

Gilt das als ausreichend stabile Bestellung für Ihre Zwecke?


Nehmen Sie zur Verdeutlichung das Beispiel aus Ihrem Kommentar: a> b , und c ist nicht vergleichbar mit a oder b :

  • a dann b dann c => a, b, c ... dies ist bereits in Haufenreihenfolge und nichts bewegt sich jemals im Sichten
  • b, a, c => a, b, c ... a wird an die richtige Stelle gesiebt, und wieder sind wir in der richtigen Heap-Reihenfolge
  • a, c, b => a, c, b ... b kann nicht sichten, weil es nicht mit c vergleichbar ist, aber dies lässt sie in FIFO-Reihenfolge, wie Sie gefragt haben
  • c, b, a => c, a, b ... a und b sind in der richtigen relativen Reihenfolge, aber keiner kann vor c kommen, weil sie nicht damit verglichen werden können

Das Ergebnis hängt also von der Reihenfolge der Einfügung ab. Dies scheint mit Ihrer Anfrage übereinzustimmen, aber ich bin mir nicht sicher, ob es wirklich das ist, was Sie wollen. Wenn nicht, könnten Sie das erhoffte Ergebnis anzeigen?


OK, ausgehend von Ihrem Kommentar (und der Bearbeitung Ihrer Frage) möchten Sie, dass "vergleichbare" Elemente "nicht vergleichbare" Elemente überspringen und unter der Bestellung den richtigen Platz finden, falls es einen gibt. Ich habe danach gefragt, weil ich mir nicht sicher war, wie ich das interpretieren soll

Wenn einige Elemente nicht vergleichbar sind, werden sie in der Reihenfolge zurückgegeben, in der sie eingefügt wurden

(d und b sind in deiner Bearbeitung paarweise nicht vergleichbar , aber du willst sie nicht in der Reihenfolge, in der sie eingefügt wurden).

Meine nächste Frage wäre über die Beziehung zwischen den "vergleichbaren" und "nicht vergleichbaren" Elementen gewesen, aber ich sehe, dass Sie jetzt enthüllt haben, dass es sich um Vektoren in der Produktreihenfolge handelt (es war nicht klar, ob einige Elemente paarweise sind). unvergleichbar mit allem , wie NaN oder was).

Wenn ich also Ihr neues Beispiel nehme und Vektorwerte zuordne, ist es richtig, dass dies ein Beispiel ist, in dem b mit nichts anderem vergleichbar ist:

        a (1,1)
      /      \
    b (0,4)   c (3,3)
  /
d (2,2)

und es sollte so sortieren:

        a (1,1)
      /      \
    d (2,2)   c (3,3)
  /
b (0,4)

?

Nutzlos
quelle
Ich habe in der Frage ausdrücklich erwähnt, dass es nicht funktionieren wird, weil ich dachte, ich hätte ein Gegenbeispiel, aber ich bin mir jetzt nicht so sicher. Können Sie nachweisen, dass eine solche Warteschlange fehlerfrei ist (auch zum Löschen, Einfügen und Aktualisieren)? Und denken Sie daran, dass es möglich ist, dass a ≤ b , aber c nicht mit der obigen Regel vergleichbar ist (und daher "gleich" ist).
Nun, das ist noch kein Beweis. Kümmere dich noch nicht um die Reihenfolge und beweise, dass ein solcher Heap immer ein minimales Element an der Spitze hat (Anmerkung: (mehr) allgemeine Konvention und die tatsächliche Notwendigkeit des Algorithmus ist an der Spitze minimal , also wenn a> b , kommt b zuerst ).
Eigentlich vermute ich, dass es Gegenbeispiel gibt. Angenommen, a , b und c sind auf dem Haufen, a ≤ b und a ≤ c , a ist oben, b ist linkes Kind, c ist rechtes Kind. Jetzt kommt d, dass d ≤ c und unvergleichbar mit a und b . Es wird als Kind von b eingefügt , ist nicht kleiner und bleibt dort. Nun kommt e , das ist c ≤ e (also auch a ≤ e ) und unvergleichbar mit b . Also geht e als rechtes Kind von b einund bleibt. Nun extrahiere a (OK, a ist minimal), e wird an seiner Stelle getauscht und abgesiebt. Es ist unvergleichlich mit b , aber kleiner als c , also tauscht es mit c . Nun extrahiere c , FALSCH , d ≤ c .
Wenn Sie im vorherigen Kommentar einen Fehler finden (der eine Form der Ungleichung erfordern würde, die aufgrund der Transitivität gelten muss, und ich habe ihn verpasst), haben Sie immer noch eine Chance. Sonst geht es nicht.
1
Ok, noch einfacher Gegenbeispiel. Angenommen, a , b und c befinden sich im Haufen, a ≤ c , b ist mit beiden nicht vergleichbar. a ist oben, b ist linkes Kind, c ist rechtes Kind. d kommt so herein, dass d ≤ a (also d ≤ c ) und nicht mit b zu vergleichen ist . Der nächste freie Steckplatz ist als linkes Kind von b und d unvergleichbar, also bleibt er dort. Nun extrahiere a , FALSCH , d ≤ a . Beachten Sie, ob a ≤ coder nicht, egal, die Situation ist die gleiche, wenn sie unvergleichlich waren.