File d'attente prioritaire pour les priorités partiellement ordonnées avec infima

16

J'ai quelques objets avec priorité qui sont de type composé et qui ne sont que partiellement ordonnés . Je dois sélectionner les objets dans l'ordre de cette priorité (c.-à-d. Produire un élément minimal à chaque fois). Mais plutôt que de terminer arbitrairement la commande, je préférerais que la file d'attente soit stable en ce sens que s'il y a plus d'un élément minimal, il devrait renvoyer le plus ancien en premier.

Existe-t-il une structure de données de tas qui fonctionnerait avec un ordre partiel? Ou une modification de la file d'attente prioritaire régulière pour fonctionner avec elle? Le choix commun pour l'algorithme dont j'ai besoin est un tas binaire simple ou 4-aires, mais cela ne fonctionne pas avec un ordre partiel.

Les valeurs de priorité prennent en charge:

partiel à l'aide de l'opération . Il s'agit d'un ordre partiel, il est donc possible que soit faux et soit également faux. J'écris dans ce cas. $\preccurlyeq$ $a \preccurlyeq b$ $b \preccurlyeq a$ $a \not\lesseqgtr b$
Trouver infima (glb) et suprema (lub). $\inf(x_i)$ est le maximal $y$ tel que $y \preccurlyeq x_i$ . Le calcul de l'infimum de $n$ valeurs prend du temps $O(n)$ . Infimum (et supremum) de chaque ensemble existe.
Une extension linéaire pour l'ordre partiel pourrait être définie. L'utiliser pour la file d'attente prioritaire est la solution la plus simple car l'algorithme fonctionne de cette façon. Mais l'ordre affecte les performances et l'ordre d'insertion semble être le meilleur pour éviter les pires cas.

De plus, l'algorithme dans lequel je veux l'utiliser doit connaître l'infimum de toutes les priorités dans la file d'attente.

Les priorités ont une signification concrète, mais sont sujettes à changement, il ne semble donc pas viable de s'appuyer sur d'autres propriétés qu'elles pourraient avoir.

Remarque: les tas binaires ne fonctionnent pas avec un ordre partiel. Supposons un tas binaire avec $a$ , $b$ et $c$ , où $a \preccurlyeq c$ et $a \not\lesseqgtr b$ et $a \not\lesseqgtr c$ . Ils sont positionnés dans cet ordre, donc

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

maintenant d est inséré. La prochaine position libre est 3, l'enfant gauche de $b$ , donc nous obtenons

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

Si (ce qui implique de transitivité, mais ne dit rien sur et ) et , alors n'est pas échangé avec , car ce n'est pas moins. Mais il est en fait inférieur à , mais il n'est pas comparé à lui, donc maintenant l'invariant du tas principal ne tient pas; le sommet n'est pas minimal. $d \preccurlyeq a$ $d \preccurlyeq c$ $d$ $b$ $d \not\lesseqgtr b$ $d$ $b$ $a$

Je soupçonne qu'une forêt de tas quelque peu dans le style d'un tas binomial pourrait être mise en place. Fondamentalement, il est important de toujours comparer les nouvelles valeurs avec root et de ne lier que des éléments comparables. Cela rendrait les arbres de la forêt de taille aléatoire et rendrait ainsi la complexité dépendante du nombre d'ensembles mutuellement incomparables dans le tas. Je soupçonne quelque peu que la complexité ne peut pas être corrigée (nous devons continuer à comparer jusqu'à ce que nous atteignions un élément comparable) J'ai peut-être manqué quelque chose, alors je laisse cela ouvert.

Remarque: l'ordre est partiel et bien qu'il existe des moyens de lui définir des extensions linéaires, l'ajout d'un horodatage et son utilisation comme critère secondaire n'en fait pas partie. Supposons que nous ayons affecté l'horodatage pour chaque et défini l'ordre comme ssi ou ( et . Supposons alors que nous ayons , , distincts , tels que et . Alors et $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$ , mais , donc la relation n'est pas transitive et n'est donc pas du tout un ordre. Ce type d'extension ne fonctionne que pour les commandes faibles, mais pas partielles. $c \preccurlyeq' a$

Edit: je me suis rendu compte que non seulement l'infimum d'un ensemble était défini, mais que je devais en fait pouvoir obtenir efficacement l'infimum des éléments actuellement dans la file d'attente. Donc, je me demande maintenant si l'ajout de nœuds spéciaux contenant des infima de sous-arbres à une structure de tas commune serait utile.

data-structures priority-queues Jan Hudec
la source

Avez-vous envisagé une file d'attente prioritaire indexée?

@hulkmeister: Pourriez-vous s'il vous plaît expliquer comment avoir la file d'attente indexée le fait fonctionner avec un classement partiel (non, le tas binaire ordinaire ne fonctionne pas avec un classement partiel)?

1

Ma pensée était que lorsque deux éléments sont incomparables, vous pouvez utiliser l'index pour suivre l'ordre d'insertion. Composez donc la priorité avec l'index, et vous avez des clés uniques qui sont comparables même lorsque la priorité ne l'est pas. Si cela ressemble à ce que vous voulez, je peux le mettre dans une réponse complète.

1

@hulkmeister: Eh bien, le problème est bien plus profond que cela. Lorsqu'un nouvel élément est inséré, la file d'attente prioritaire le compare normalement à un élément. Mais s'ils sont incomparables, il ne sait tout simplement pas où les insérer. Et la désambiguïsation avec l'index ne fonctionnera pas, car l'index change et parce qu'il ne donnera probablement pas un ordre total cohérent avec la priorité de toute façon.

Pouvez-vous donner un exemple de ce type de composé, et quand il est incomparable? Est-il possible de considérer ces valeurs «incomparables» égales? Si c'est le cas, vous pouvez les stocker dans le même nœud par ordre d'insertion.

3

Bien que le problème exact posé dans la question d'origine semble être difficile (et je serais intéressé par une solution à ce problème, en particulier la partie de recherche d'infima). Je voulais juste noter que si l'ensemble partiellement ordonné se compose en effet de vecteurs utilisant une commande de produit, et s'il suffit d'avoir la garantie que la file d'attente prioritaire renvoie les valeurs dans un ordre "compatible" avec l'ordre partiel ( c'est-à-dire que les éléments plus petits sont toujours renvoyés avant les éléments plus grands), il existe alors un moyen assez simple de le faire.

L'idée est essentiellement de trouver un ordre topologique de l'ensemble partiellement ordonné. Autrement dit, un ordre total ' ' tel que . Pour les vecteurs utilisant une commande de produit, cela est assez simple: utilisez simplement un ordre lexicographique ' ', où le premier "composant" est la somme de tous les composants utilisés pour la commande de produit (les autres composants sont essentiellement arbitraires, vous pouvez donc vous en tenir à un ordre faible). On peut alors voir que et $\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}$

a = b ⟹ \forall_{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=b_i)\implies(\sum_i a_i)=(\sum_i b_i)\implies\mathbf{a}\le_S\mathbf{b},$ et donc que . Nous pouvons donc utiliser cet ordre avec une file d'attente prioritaire et être sûr que les éléments plus petits (dans la commande du produit) seront toujours extraits avant les éléments plus grands.

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

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

Jaspe
la source

Il y a beaucoup plus d'options. En utilisant l'un des composants, minimum, maximum, toute combinaison linéaire avec des coefficients non négatifs au moins. Le choix de l'extension affecte la vitesse de l'algorithme de superposition.

Jan Hudec

2

Quel est le problème avec la finalisation de votre commande partielle?

Mais plutôt que de terminer arbitrairement la commande, je préférerais que la file d'attente soit stable en ce sens que s'il y a plus d'un élément minimal, il devrait renvoyer le plus ancien en premier.

Si vous préférez «le plus ancien d'abord», alors votre commande est effectivement terminée; les articles «incomparables» sont comparables selon l'âge.

Ajoutez un horodatage (ou tout autre entier à croissance monotone) à chaque élément et utilisez-le si une comparaison «réelle» est impossible.

la source

3

Ce serait formidable si l'on pouvait faire une extension linéaire de l'ordre partiel. Mais ce n'est pas le cas. Ayons 3 valeurs distinctes, insérées dans l'ordre a , b , c , telles que c ≤ a et b soit incomparable avec l'une ou l'autre. L'extension avec horodatage remplit a ≤ 'b et b ≤' c , donc de transitivité maintenant a devrait être inférieur à c , mais cela contredit l'ordre réel.

Peut-être l'avez-vous confondu avec un ordre faible. Dans un ordre faible, les éléments incomparables forment des classes d'équivalence, vous pouvez donc ajouter des critères supplémentaires arbitraires. Pour une commande partielle, vous ne pouvez pas.

1

EDIT: cela semble être un problème intéressant, et j'ai eu quelques recherches à ce sujet. Je vous suggère de lire ce qui suit:

Darell Raymond. Bases de données d'ordre partiel, thèse de doctorat, Université de Waterloo.

Je vous suggère de lire cet article: Daskalakis, Constantinos, et al. "Tri et sélection en posets." SIAM Journal on Computing 40.3 (2011): 597-622.

Les auteurs présentent ici une structure de données appelée ChainMerge qui accepte un poset et une décomposition en chaîne du poset en chaînes. La taille de la structure de données est . Les auteurs présentent un algorithme pour trouver les minimas qui s'exécutent dans où est une limite supérieure sur la largeur du poset. .. J'ai pensé que c'était peut-être intéressant. $q$ $O(n q)$ $O(w n)$ $w$

Remarque: j'ai supprimé une réponse naïve précédente. Veuillez cliquer sur modifier pour le voir.

AJed
la source

0

Mon utilisation de la terminologie peut être incorrecte. Veuillez modifier ma réponse directement pour résoudre les problèmes que vous rencontrez.

Premièrement, des ensembles mutuellement incomparables doivent être détectés à partir des entrées.

Par exemple, il peut y avoir 5 objets a, b, c, d, e, mais leur ordre partiel forme deux graphiques déconnectés:

a ≤ b ≤ c
d ≤ e
mais tout {a, b, c}est incomparable avec aucun {d, e}.

Ces ensembles mutuellement incomparables doivent d'abord être détectés, avant que les objets puissent être stockés dans une structure de données appropriée. Cela peut être fait avec un algorithme de recherche Union

Pour être efficace, l'insertion d'un nouvel objet doit avoir un moyen efficace de trouver "la liste des objets existants qui sont comparables avec ce nouvel objet".

Maintenant, au sein de chaque sous-ensemble (respectivement {a, b, c}et {d, e}), les minima doivent être bien définis. (Pour chaque sous-ensemble, il peut y avoir un ou plusieurs minima, en raison d'une commande partielle.)

Je vois cela comme un graphique acyclique dirigé . Essayer de l'intégrer dans un tas semble désastreux.

Pour extraire les minima de cette structure de données composite, l'étape suivante consiste à obtenir la liste de tous les minima de tous les sous-ensembles, de choisir celui avec l'horodatage le plus ancien, de supprimer et de renvoyer cet objet.

rwong
la source

Malheureusement, je ne vois pas comment trouver efficacement la liste d'objets comparables.

Un ensemble partiellement ordonné peut en effet être considéré comme un graphique acyclique dirigé. Mais une donnée par une table de contiguïté (fonction, en fait) plutôt que par une liste de contiguïté. Trouver des minima de posets donnés par la liste de contiguïté est facile, mais pour la table de contiguïté c'est un problème.

Les minima sont également bien définis dans l'ensemble d'origine. Je ne vois pas comment trouver les composants connectés pourrait aider, car ce ne sont pas des graphiques complets.

1

Vous semblez supposer que le diagramme de Hasse est une forêt d'arbres unaires (graphes de chemins équivalents), mais la question indique déjà qu'il s'agit d'un ordre de produit, donc d'un réseau multidimensionnel.

Peter Taylor

0

Un projet sur lequel je travaille implique un problème similaire (d'ailleurs, j'utilise également l'ordre partiel des vecteurs). Nous avions déjà un algorithme temporel quadratique pour trier une liste ordonnée de façon aléatoire, et j'ai développé un algorithme d'insertion en observant son comportement lorsqu'un seul objet était en panne. Nous ne savons pas si c'est la mise en œuvre la plus rapide possible.

Voici un 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)

Liste Jeremy
la source

-1

Le comportement de segment de mémoire habituel consiste à ajouter la nouvelle valeur à l'arrière, puis à passer au crible pendant qu'elle se compare plus que son parent.

Si vous écrivez une comparaison qui retourne la même chose pour le parent et l'enfant ne sont pas des cas comparables car pour le parent est supérieur à l'enfant , le tri devrait toujours se terminer au bon point.

Est-ce que cela compte comme une commande suffisamment stable pour vos besoins?

Pour clarifier, prenez l'exemple de votre commentaire: a> b , et c n'est pas comparable à a ou b :

a puis b puis c => a, b, c ... c'est déjà dans l'ordre du tas, et rien ne bouge jamais au crible
b, a, c => a, b, c ... a est tamisé à sa place correcte, et encore une fois, nous sommes dans le bon ordre de tas
a, c, b => a, c, b ... b ne peut pas passer au crible car il n'est pas comparable à c, mais cela les laisse dans l'ordre FIFO comme vous l'avez demandé
c, b, a => c, a, b ... a et b sont dans le bon ordre relatif, mais aucun ne peut devancer c car ils ne peuvent pas être comparés avec lui

donc, le résultat dépend de l'ordre d'insertion - cela semble correspondre à ce que vous demandez, mais je ne sais pas si c'est vraiment ce que vous voulez. Si ce n'est pas le cas, pourriez-vous montrer le résultat que vous espériez voir?

OK, donc à partir de votre commentaire (et de la modification de votre question), vous voulez que les éléments "comparables" dépassent ceux "non comparables" et trouvent le bon endroit sous la commande, s'il y en a un. J'ai posé des questions à ce sujet parce que je ne savais pas comment interpréter

si certains éléments sont incomparables, il les renvoie dans l'ordre où ils ont été insérés

(d et b sont deux par deux incomparables dans votre montage, mais vous ne les voulez pas dans l'ordre où ils ont été insérés).

Ma prochaine question aurait porté sur la relation entre les éléments "comparables" et "non comparables", mais je vois que vous avez maintenant révélé qu'ils sont des vecteurs dans l'ordre des produits (il n'était pas clair si certains éléments étaient appariés- incomparable avec tout , comme NaN, ou quoi).

Donc, si je prends votre nouvel exemple et que j'assigne des valeurs vectorielles, est-il exact que c'est un exemple où b n'est comparable à rien d'autre:

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

et il devrait trier ceci:

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

?

Inutile
la source

J'ai explicitement mentionné dans la question que cela ne fonctionnera pas, parce que je pensais avoir un contre-exemple, mais je n'en suis pas si sûr maintenant. Pouvez-vous prouver qu'une telle file d'attente serait solide (pour la suppression, l'insertion et la mise à jour également)? Et rappelez-vous qu'il est possible que a ≤ b , mais c ne soit pas comparable (et comparerait donc "égal" à la règle ci-dessus) à l'un ou l'autre.

Eh bien, ce n'est pas encore la preuve. Ne vous souciez pas encore de l'ordre et prouvez qu'un tel tas a toujours un élément minimal en haut (note: (plus) convention commune et le besoin réel de l'algorithme est minime en haut, donc si a> b , b vient en premier ).

En fait, je soupçonne qu'il y a un contre-exemple. Supposons que a , b et c sont dans le tas, a ≤ b et a ≤ c , a est en haut, b est enfant gauche, c est enfant droit. Maintenant d vient que d ≤ c et incomparable avec a et b . Il est inséré comme enfant de b , n'est pas moindre et y reste. Vient maintenant e qui est c ≤ e (donc aussi a ≤ e ) et incomparable à b . Alors e entre en tant qu'enfant droit de bet reste. Maintenant, extrayez un (OK, a est minime), e est échangé à sa place et tamisé. Il est incomparable à b , mais inférieur à c , donc échange avec c . Maintenant, extrayons c , FAUX , d ≤ c .

Si vous trouvez une erreur dans le commentaire précédent (qui devrait avoir une forme d'inégalité qui doit tenir à cause de la transitivité et je l'ai ratée), vous auriez encore une chance. Sinon, cela ne fonctionnera pas.

1

Ok, contre-exemple encore plus simple. Supposons que a , b et c sont dans le tas, a ≤ c , b est incomparable avec l'un ou l'autre. a est haut, b est enfant gauche, c est enfant droit. d vient de telle sorte que d ≤ a (donc d ≤ c ) et incomparable avec b . La prochaine fente libre est comme l'enfant gauche de b et d est incomparable, donc elle y reste. Extrayons maintenant a , WRONG , d ≤ a . Notez que si a ≤ cou pas n'a pas d'importance, la situation est la même s'ils étaient incomparables.

File d'attente prioritaire pour les priorités partiellement ordonnées avec infima

Réponses: