Kolejka priorytetowa dla częściowo uporządkowanych priorytetów z infima

16

Mam kilka obiektów o priorytecie, które są typu złożonego i są tylko częściowo uporządkowane . Muszę wybierać obiekty w kolejności tego priorytetu (tzn. Za każdym razem uzyskiwać minimalny przedmiot). Ale zamiast arbitralnie realizować zamówienie, wolałbym, aby kolejka była stabilna w takim sensie, że jeśli jest więcej niż jeden minimalny element, powinna zwracać najstarszą jako pierwszą.

Czy istnieje struktura danych sterty, która działałaby przy częściowym uporządkowaniu? Czy modyfikacja zwykłej kolejki priorytetowej do pracy z nią? Częstym wyborem algorytmu, którego potrzebuję, jest prosta sterta binarna lub 4-arytowa, ale to nie działa z częściowym uporządkowaniem.

Wartości priorytetów obsługują:

Częściowe zamawianie za pomocą operacji . Jest to częściowe uporządkowanie, więc możliwe jest, że jest fałszywe, a również jest fałszywe. W takim przypadku piszę . $\preccurlyeq$ $a \preccurlyeq b$ $b \preccurlyeq a$ $a \not\lesseqgtr b$
Znalezienie infima (glb) i suprema (lub). $\inf(x_i)$ jest maksymalnym $y$ takim, że $y \preccurlyeq x_i$ . Obliczenie minimum $n$ wartości zajmuje czas $O(n)$ . Istnieje minimum (i supremum) każdego zestawu.
Można zdefiniować rozszerzenie liniowe dla częściowego uporządkowania. Użycie go w kolejce priorytetowej jest łatwym rozwiązaniem, ponieważ algorytm działa w ten sposób. Ale kolejność wpływa na wydajność, a kolejność wstawiania wygląda najlepiej, aby unikać najgorszych przypadków.

Dodatkowo algorytm, w którym chcę tego używać, musi znać minimum wszystkich priorytetów w kolejce.

Priorytety mają pewne znaczenie w świecie rzeczywistym, ale mogą ulec zmianie, więc nie można polegać na innych właściwościach, które mogą mieć.

Uwaga: Kupy binarne nie działają przy częściowym uporządkowaniu. Załóżmy stertę binarną z $a$ , $b$ i $c$ , gdzie $a \preccurlyeq c$ i $a \not\lesseqgtr b$ i $a \not\lesseqgtr c$ . Są one ustawione w tej kolejności, więc

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

teraz d jest wstawione. Następna wolna pozycja to 3, lewe dziecko $b$ , więc otrzymujemy

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

Jeśli (co implikuje z przechodniości, ale nic nie mówi o i ) i , to nie zostanie zamienione na , ponieważ to nie jest mniej. Ale tak naprawdę jest mniej niż , ale nie jest z nim porównywany, więc teraz główny niezmiennik sterty nie ma miejsca; góra nie jest minimalna. $d \preccurlyeq a$ $d \preccurlyeq c$ $d$ $b$ $d \not\lesseqgtr b$ $d$ $b$ $a$

Podejrzewam, że las hałd w stylu dwumianowej hałdy mógłby zostać wykorzystany. Zasadniczo ważne jest, aby zawsze porównywać nowe wartości z rootem i łączyć tylko porównywalne elementy. Spowodowałoby to, że drzewa w lesie miałyby losowy rozmiar, a tym samym złożoność zależałaby od liczby wzajemnie nieporównywalnych zbiorów w hałdzie. Podejrzewam, że złożoności nie da się naprawić (musimy porównywać, aż trafimy na porównywalny element) Mogłem coś przeoczyć, więc zostawiam to otwarte.

Uwaga: Kolejność jest częściowa i chociaż istnieją sposoby na zdefiniowanie rozszerzeń liniowych, dodanie znacznika czasu i użycie go jako kryterium wtórnego nie jest jednym z nich. Załóżmy, że przypisaliśmy znacznik czasu dla każdego i zdefiniowaliśmy kolejność jako i lub ( i . następnie załóżmy, że posiada odrębną , , tak, że i , a następnie i $t(a)$ $a$ $\preccurlyeq'$ $a \preccurlyeq' b$ $a \preccurlyeq b$ $b \not\preccurlyeq a$ $t(a) \le t(b)$ $a$ $b$ $c$ $t(a) \le t(b) \le t(c)$ $c \le a$ $a \preccurlyeq' b$ $b \preccurlyeq' c$ , ale , więc relacja nie jest przechodnia i dlatego w ogóle nie jest porządkiem. Ten rodzaj rozszerzenia działa tylko w przypadku słabych zamówień, ale nie częściowych. $c \preccurlyeq' a$

Edycja: Zdałem sobie sprawę, że nie tylko jest najmniej zdefiniowany zestaw, ale tak naprawdę muszę być w stanie efektywnie uzyskać minimum elementów znajdujących się w kolejce. Zastanawiam się więc, czy dodanie specjalnych węzłów zawierających infima poddrzewa do jakiejś wspólnej struktury stosu byłoby pomocne.

data-structures priority-queues Jan Hudec
źródło

Czy rozważałeś indeksowaną kolejkę priorytetową?

@hulkmeister: Czy możesz wyjaśnić, w jaki sposób indeksowanie kolejki sprawia, że działa ona z częściowym porządkowaniem (nie, zwykła kupa binarna nie działa z częściowym porządkowaniem)?

1

Myślałem, że gdy dwa elementy są nieporównywalne, możesz użyć indeksu do śledzenia kolejności wstawiania. Skomponuj więc priorytet za pomocą indeksu, a otrzymasz unikalne klucze, które są porównywalne, nawet jeśli priorytet nie jest. Jeśli brzmi to tak, jak chcesz, mogę udzielić pełnej odpowiedzi.

1

@hulkmeister: Cóż, problem jest znacznie głębszy. Po wstawieniu nowego elementu kolejka priorytetowa zwykle porównuje go z jakimś elementem. Ale jeśli są nieporównywalne, po prostu nie wie, gdzie je wstawić. A ujednoznacznienie z indeksem nie zadziała, ponieważ indeks się zmienia i prawdopodobnie i tak nie dałby całkowitego uporządkowania zgodnego z priorytetem.

Czy możesz podać przykład tego typu związku i kiedy jest on nieporównywalny? Czy można uznać te „nieporównywalne” wartości za równe? Jeśli tak, możesz przechowywać je w tym samym węźle w kolejności wstawiania.

3

Chociaż dokładny problem postawiony w pierwotnym pytaniu wydaje się być trudny (i chciałbym być zainteresowany rozwiązaniem tego problemu, szczególnie części dotyczącej znalezienia infima). Chciałem tylko zauważyć, że jeśli częściowo uporządkowany zestaw rzeczywiście składa się z wektorów korzystających z zamówienia produktu i jeśli wystarczy mieć gwarancję, że kolejka priorytetowa zwróci wartości w kolejności „zgodnej” z kolejnością częściową ( to znaczy, mniejsze elementy są zawsze zwracane przed większymi elementami), wtedy istnieje dość łatwy sposób, aby to zrobić.

Chodzi przede wszystkim o uporządkowanie topologiczne częściowo uporządkowanego zestawu. Oznacza to całkowite zamówienie „ ” takie, że . W przypadku wektorów korzystających z zamówienia produktu jest to dość proste: wystarczy użyć porządku leksykograficznego „ ”, gdzie pierwszy „komponent” jest sumą wszystkich komponentów użytych do zamówienia produktu (pozostałe komponenty są zasadniczo dowolne, abyś mógł trzymać się słabej kolejności). Możemy wtedy zobaczyć, że i $\le_T$ $\mathbf{a}\le\mathbf{b}\implies \mathbf{a}\le_T\mathbf{b}$ $\le_S$

a < b ⟹ \forall_{i} (a_{i} \leq b_{i}) and \exists_{i} (a_{i} < b_{i}) ⟹ (\sum_{i} a_{i}) < (\sum_{i} b_{i}) ⟹ a \leq_{S} b

$\mathbf{a}<\mathbf{b}\implies \forall_i(a_i\le b_i)\text{ and }\exists_i(a_i<b_i)\implies(\sum_i a_i)<(\sum_i b_i)\implies\mathbf{a}\le_S\mathbf{b}$

za = b ⟹ \forall_{ja} ({za}_{ja} = b_{ja}) ⟹ (\sum_{ja} {za}_{ja}) = (\sum_{ja} b_{ja}) ⟹ za \leq_{S.} b,

$\mathbf{a}=\mathbf{b}\implies \forall_i(a_i=b_i)\implies(\sum_i a_i)=(\sum_i b_i)\implies\mathbf{a}\le_S\mathbf{b},$ a zatem że . Możemy więc użyć tego zamówienia z kolejką priorytetową i mieć pewność, że mniejsze elementy (w zamówieniu produktu) będą zawsze wyodrębniane przed większymi elementami.

a \leq b ⟹ a \leq_{S} b

$\mathbf{a}\le\mathbf{b}\implies\mathbf{a}\le_S\mathbf{b}$

Jaspis
źródło

Istnieje wiele innych opcji. Przy użyciu jednego ze składników: minimum, maksimum, dowolna kombinacja liniowa z co najmniej nieujemnymi współczynnikami. Wybór rozszerzenia wpływa na szybkość algorytmu nakładania.

Jan Hudec

2

Co jest złego w kompletowaniu częściowego zamówienia?

Ale zamiast arbitralnie realizować zamówienie, wolałbym, aby kolejka była stabilna w takim sensie, że jeśli jest więcej niż jeden minimalny element, powinna zwracać najstarszą jako pierwszą.

Jeśli wolisz „najpierw najstarsze”, Twoje zamówienie jest faktycznie ukończone; „nieporównywalne” przedmioty są porównywalne pod względem wieku.

Dodaj znacznik czasu (lub dowolną monotonnie rosnącą liczbę całkowitą) do każdego elementu i użyj go, jeśli „rzeczywiste” porównanie jest niemożliwe.

źródło

3

Byłoby wspaniale, gdyby można było dokonać liniowego przedłużenia częściowego uporządkowania. Ale tak nie jest. Miejmy 3 różne wartości, wstawione w kolejności a , b , c , tak aby c ≤ a i b były nieporównywalne z żadnym z nich. Rozszerzenie ze znacznikiem czasu wypełnia ≤ ≤ „b” i „ b ≤” c , więc z przechodnialności teraz a powinna być mniejsza niż c , ale jest to sprzeczne z rzeczywistym uporządkowaniem.

Być może pomyliłeś to ze słabym uporządkowaniem. Przy słabym uporządkowaniu nieporównywalne elementy tworzą klasy równoważności, dzięki czemu można dodawać dowolne dodatkowe kryteria. W przypadku częściowego zamówienia nie możesz.

1

EDYCJA: wydaje się to interesującym problemem i miałem na ten temat trochę badań. Proponuję przeczytać następujące informacje:

Darell Raymond. Bazy danych zamówień częściowych, praca doktorska, University of Waterloo.

Proponuję przeczytać ten artykuł: Daskalakis, Constantinos i in. „Sortowanie i selekcja w zestawach”. SIAM Journal on Computing 40.3 (2011): 597-622.

Autorzy przedstawiają tutaj strukturę danych o nazwie ChainMerge, która akceptuje poset i rozkład łańcucha poset na łańcuchy. Rozmiar struktury danych wynosi . Autorzy przedstawiają algorytm znajdowania minimów działających w gdzie jest górną granicą szerokości zbioru. .. Myślałem, że może to interesujące. $q$ $O(n q)$ $O(w n)$ $w$

Uwaga: usunąłem poprzednią naiwną odpowiedź. Kliknij edytuj, aby go zobaczyć.

AJed
źródło

0

Moje użycie terminologii może być nieprawidłowe. Edytuj moją odpowiedź bezpośrednio, aby naprawić znalezione problemy.

Najpierw na wejściach należy wykryć zestawy nieporównywalne ze sobą.

Na przykład może być 5 obiektów a, b, c, d, e, ale ich częściowe uporządkowanie tworzy dwa niepowiązane wykresy:

a ≤ b ≤ c
d ≤ e
ale żaden z nich {a, b, c}jest nieporównywalny z żadnym z nich {d, e}.

Te wzajemnie nieporównywalne zestawy należy najpierw wykryć, zanim obiekty będą mogły zostać zapisane w odpowiedniej strukturze danych. Można to zrobić za pomocą algorytmu wyszukiwania Unii

W celu zwiększenia wydajności wstawienie nowego obiektu musi mieć skuteczny sposób na znalezienie „listy istniejących obiektów, które są porównywalne z tym nowym obiektem”.

Teraz w ramach każdego podzbioru (odpowiednio {a, b, c}i {d, e}) minima powinny być dobrze zdefiniowane. (Dla każdego podzestawu może istnieć jeden lub więcej minimów, z powodu częściowego uporządkowania.)

Widzę to jako ukierunkowany wykres acykliczny . Próba zmieszczenia go w kupę wydaje się katastrofalna.

Aby wyodrębnić minima z tej złożonej struktury danych, następnym krokiem jest pobranie listy wszystkich minimów ze wszystkich podzbiorów, wybranie tej z najwcześniejszym znacznikiem czasu oraz usunięcie i zwrócenie tego obiektu.

rwong
źródło

Niestety nie widzę sposobu, aby skutecznie znaleźć listę porównywalnych obiektów.

Częściowo zamówiony zestaw można rzeczywiście postrzegać jako ukierunkowany wykres acykliczny. Ale jeden podany przez tabelę przylegania (właściwie funkcję), a nie listę przyległości. Znalezienie minimów zestawu określonych przez listę przylegania jest łatwe, ale dla tabeli przyległości jest to problem.

Minima są również dobrze określone w oryginalnym zestawie. Nie rozumiem, jak znalezienie podłączonych komponentów mogłoby pomóc, ponieważ nie są to kompletne wykresy.

1

Wydaje się, że zakładasz, że diagram Hassego to las jednych drzew (równoważnie wykresy ścieżek), ale pytanie już mówi, że jest to zamówienie produktu, a więc wielowymiarowa sieć.

Peter Taylor

0

Projekt, nad którym pracuję, wiąże się z podobnym problemem (nawiasem mówiąc, używam także częściowej kolejności wektorów). Mieliśmy już kwadratowy algorytm czasowy do sortowania losowo uporządkowanej listy i opracowałem algorytm wstawiania, obserwując jego zachowanie, gdy tylko jeden obiekt był niesprawny. Nie wiemy, czy jest to najszybsza możliwa implementacja.

Oto pseudokod.

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)

Lista Jeremy
źródło

-1

Zwykłym zachowaniem sterty jest dołączanie nowej wartości z tyłu, a następnie przesiewanie w górę, gdy porównuje ona wartość większą niż jej rodzic.

Jeśli napiszesz porównanie, które zwraca to samo dla rodzica, a dziecko nie jest porównywalnym przypadkiem, ponieważ dla rodzica jest większy niż dziecko , przesiewanie w górę powinno nadal kończyć się w odpowiednim momencie.

Czy to liczy się jako wystarczająco stabilne zamówienie dla twoich celów?

Aby to wyjaśnić, weź przykład z komentarza: a> b , a c nie jest porównywalne z a lub b :

a następnie b, a następnie c => a, b, c ... to jest już w kolejności stosu i nic nie przesuwa się
b, a, c => a, b, c ... a przesiewa się na właściwe miejsce, i znowu mamy prawidłową kolejność stert
a, c, b => a, c, b ... b nie może przesiewać w górę, ponieważ nie jest porównywalne z c, ale to pozostawia je w kolejności FIFO, jak prosiłeś
c, b, a => c, a, b ... a i b są w prawidłowej kolejności względnej, ale żadna nie może wyprzedzić c, ponieważ nie można ich z tym porównać

więc wynik zależy od kolejności wstawiania - wydaje się, że pasuje do tego, o co prosisz, ale nie jestem pewien, czy naprawdę tego chcesz. Jeśli nie, czy mógłbyś pokazać wynik, który miałeś nadzieję zobaczyć?

OK, więc z twojego komentarza (i edycji pytania) chcesz, aby „porównywalne” elementy przeskoczyły „nieporównywalne” i znaleźć właściwe miejsce pod zamówieniem, jeśli takie istnieje. Zapytałem o to, ponieważ nie byłem pewien, jak interpretować

jeśli niektóre elementy są nieporównywalne, zwraca je w kolejności, w której zostały wstawione

(d i b są nieporównywalne parami w twojej edycji, ale nie chcesz ich w kolejności, w której zostały wstawione).

Moje następne pytanie dotyczyłoby związku między elementami „porównywalnymi” i „nieporównywalnymi”, ale widzę, że ujawniłeś teraz, że są wektorami w kolejności produktów (nie było jasne, czy niektóre elementy były parami - nieporównywalne ze wszystkim , jak NaN, czy co).

Jeśli więc wezmę twój nowy przykład i przypiszę wartości wektorowe, czy to prawda, że jest to przykład, w którym b nie jest porównywalny z niczym innym:

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

i powinno posortować to:

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

?

Nieprzydatny
źródło

W pytaniu wyraźnie wspomniałem, że to nie zadziała, ponieważ myślałem, że mam kontrprzykład, ale nie jestem już tego taki pewien. Czy możesz udowodnić, że taka kolejka byłaby dobra (dla usunięcia, wstawienia i aktualizacji też)? I pamiętaj, że możliwe jest, że a ≤ b , ale c nie jest porównywalne (i dlatego porównałoby „równe” z powyższą regułą) do któregokolwiek z nich.

To jeszcze nie dowód. Nie dbaj jeszcze o kolejność i udowodnij, że taka sterty zawsze ma minimalny element na górze (uwaga: (więcej) wspólna konwencja i faktyczna potrzeba algorytmu jest minimalna na górze, więc jeśli a> b , b jest pierwsze ).

Podejrzewam, że istnieje kontrprzykład. Załóżmy , że a , b i c znajdują się na stosie, a ≤ b i a c , a jest górny, b jest lewym dzieckiem, c jest prawym dzieckiem. Teraz d przychodzi, że d ≤ c i nieporównywalne z a i b . Jest wstawiany jako dziecko b , jest nie mniejszy i zostaje tam. Teraz pojawia się e, które jest c ≤ e (a więc także a ≤ e ) i nieporównywalne z b . Tak e idzie jako prawe dziecko bi zostaje. Teraz wyodrębnić (OK, jest minimalny), e zostanie zamienione w jego miejsce i przesiane dół. Jest nieporównywalny do b , ale mniejszy niż c , więc zamienia się na c . Teraz wyodrębnij c , ŹLE , d ≤ c .

Jeśli znajdziesz błąd w poprzednim komentarzu (który musiałby mieć formę nierówności, która musi się utrzymywać z powodu przechodniości, a ja go przegapiłem), nadal będziesz miał szansę. W przeciwnym razie to nie zadziała.

1

Ok, jeszcze prostszy kontrprzykład. Załóżmy, , b i c są w stosie, a ≤ C , b jest nieporównywalny z innym. a jest górny, b jest lewym dzieckiem, c jest prawym dzieckiem. d pojawia się tak, że d ≤ a ( a więc d ≤ c ) i nieporównywalne z b . Następny wolny slot jest jako lewy dziecko b oraz d jest nieporównywalny, więc pozostaje tam. Teraz wyodrębnij a , ŹLE , d ≤ a . Zauważ, że czy a ≤ cczy nie ma znaczenia, sytuacja jest taka sama, jeśli byłyby one nieporównywalne.

Kolejka priorytetowa dla częściowo uporządkowanych priorytetów z infima

Odpowiedzi: