Fila de prioridade para prioridades parcialmente solicitadas com infima

Eu tenho alguns objetos com prioridade que é do tipo composto e é apenas parcialmente ordenada . Eu preciso selecionar os objetos na ordem desta prioridade (ou seja, produzir itens mínimos a cada vez). Mas, em vez de concluir arbitrariamente o pedido, eu preferiria que a fila fosse estável, no sentido de que, se houver mais de um elemento mínimo, ele retornará o mais antigo primeiro.

Existe alguma estrutura de dados de heap que funcione com pedidos parciais? Ou uma modificação da fila de prioridade regular para trabalhar com ela? A escolha comum para o algoritmo de que eu preciso é um binário simples ou heap de 4 árias, mas isso não funciona com a ordenação parcial.

Os valores de prioridade suportam:

1. Pedido parcial usando a operação . É uma ordem parcial, portanto, é possível que a \ preccurlyeq b seja falso e b \ preccurlyeq a também seja falso. Eu escrevo a \ not \ lesseqgtr b nesse caso.a ≼ b b ≼ a a ⋚ ̸ $\preccurlyeq$$a \preccurlyeq b$$b \preccurlyeq a$$a \not\lesseqgtr b$
2. Encontrar infima (glb) e suprema (lub). $\inf(x_i)$ é o máximo $y$ modo que $y \preccurlyeq x_i$ . Calcular o mínimo de $n$ valores leva $O(n)$ tempo. Existe o mínimo (e supremo) de todos os conjuntos.
3. Uma extensão linear para a ordem parcial pode ser definida. Usá-lo para a fila de prioridade é a saída mais fácil, pois o algoritmo funciona dessa maneira. Mas a ordem afeta o desempenho e a ordem de inserção parece ser melhor para evitar os piores casos.

Além disso, o algoritmo em que eu quero usar isso precisa conhecer o mínimo de todas as prioridades na fila.

As prioridades têm algum significado no mundo real, mas estão sujeitas a alterações, portanto, não parece viável confiar em outras propriedades que possam ter.

---

Nota: pilhas binárias não funcionam com pedidos parciais. Suponha uma pilha binário com $a$ , $b$ e $c$ , onde $a \preccurlyeq c$ e $a \not\lesseqgtr b$ e $a \not\lesseqgtr c$ . Eles estão posicionados nessa ordem, então

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

agora d está inserido. A próxima posição livre é 3, o filho esquerdo de $b$ , então obtemos

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

Se (o que implica de transitividade, mas não diz nada sobre e ) e , então não se trocado com , porque não menos é. Mas, na verdade, é menor que , mas não é comparado a ele, então agora a invariante principal do heap não se sustenta; top não é mínimo.d ≼ c d b d ⋚ ̸ b d b $d \preccurlyeq a$$d \preccurlyeq c$$d$$b$$d \not\lesseqgtr b$$d$$b$$a$

Suspeito que uma floresta de montes um tanto no estilo de pilha binomial possa ser feita para funcionar. Basicamente, é importante sempre comparar novos valores com raiz e vincular apenas elementos comparáveis. Isso tornaria as árvores da floresta de tamanho aleatório e, portanto, tornaria a complexidade dependente do número de conjuntos mutuamente incomparáveis ​​no monte. Suspeito que a complexidade não possa ser corrigida (temos que continuar comparando até encontrarmos um elemento comparável). Talvez eu tenha perdido alguma coisa, então estou deixando isso em aberto.

---

Nota: A ordem é parcial e, embora haja maneiras de definir extensões lineares para ela, adicionar um carimbo de data e hora e usá-lo como critério secundário não é um deles. Suponha que atribuiu o timestamp para cada e definiu a ordenação como sse ou ( e . em seguida, suponha que temos distinta , , , tal que e . então e$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$ , mas , então a relação não é transitiva e, portanto, não é uma ordenação. Esse tipo de extensão funciona apenas para pedidos fracos, mas não parciais.$c \preccurlyeq' a$

---

Edit: eu percebi que não só é o mínimo de qualquer conjunto definido, mas também preciso ser capaz de obter o menor número possível de elementos atualmente na fila com eficiência. Portanto, agora estou pensando se a adição de nós especiais contendo informações de subárvores a alguma estrutura de heap comum ajudaria.

Embora o problema exato colocado na pergunta original pareça difícil (e eu estaria interessado em uma solução para esse problema, especialmente a parte de encontrar informações). Eu só queria observar que, se o conjunto parcialmente ordenado consistir em vetores usando um pedido de produto e se for suficiente apenas garantir que a fila de prioridade retorne os valores em um pedido "compatível" com o pedido parcial ( ou seja, elementos menores sempre são retornados antes dos elementos maiores), então existe uma maneira bastante fácil de fazer isso.

A idéia é essencialmente encontrar uma ordem topológica do conjunto parcialmente ordenado. Ou seja, uma ordem total ' ' tal que . Para vetores que usam um pedido de produto, isso é bastante fácil: basta usar um pedido lexicográfico ' ', em que o primeiro "componente" é a soma de todos os componentes usados ​​para o pedido do produto (o restante dos componentes é essencialmente arbitrário, para que você também possa manter uma ordem fraca). Podemos então ver que e a ≤ $\le_T$≤ S a < $\mathbf{a}\le\mathbf{b}\implies \mathbf{a}\le_T\mathbf{b}$$\le_S$a =

$$\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}$$ $$\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},$$ e portanto, que . Assim, podemos usar esse pedido com uma fila prioritária e garantir que os elementos menores (na ordem do produto) sejam sempre extraídos antes dos elementos maiores.$\mathbf{a}\le\mathbf{b}\implies\mathbf{a}\le_S\mathbf{b}$

O que há de errado em concluir sua encomenda parcial?

Mas, em vez de concluir arbitrariamente o pedido, eu preferiria que a fila fosse estável, no sentido de que, se houver mais de um elemento mínimo, ele retornará o mais antigo primeiro.

Se você preferir "o mais antigo primeiro", seu pedido será efetivamente concluído; itens 'incomparáveis' são comparáveis ​​por idade.

Adicione um carimbo de data / hora (ou qualquer outro número inteiro que cresce monotonamente) a cada item e use-o se a comparação 'real' for impossível.

EDIT: este parece ser um problema interessante, e eu tive uma pequena pesquisa sobre isso. Eu sugiro que você leia o seguinte:

1. Darell Raymond. Bancos de dados de pedidos parciais, tese de doutorado, University of Waterloo.

Sugiro que você leia este artigo: Daskalakis, Constantinos, et al. "Classificação e seleção em posets." Jornal SIAM sobre Computação 40.3 (2011): 597-622.

Os autores apresentam aqui uma estrutura de dados chamada ChainMerge que aceita um poset e uma decomposição em cadeia do poset em cadeias . O tamanho da estrutura de dados é . Os autores apresentam um algoritmo para encontrar os mínimos que são executados em onde é um limite superior na largura do poset. .. Eu pensei que talvez isso seja interessante.$q$$O(n q)$$O(w n)$$w$

Nota: eu apaguei uma resposta ingênua anterior. Clique em editar para vê-lo.

Meu uso da terminologia pode estar incorreto. Por favor, edite minha resposta diretamente para corrigir os problemas encontrados.

---

Primeiro, conjuntos mutuamente incomparáveis ​​precisam ser detectados a partir das entradas.

Por exemplo, pode haver 5 objetos a, b, c, d, e, mas sua ordem parcial forma dois gráficos desconectados:

• a ≤ b ≤ c
• d ≤ e
• mas qualquer um de {a, b, c}é incomparável com qualquer um de {d, e}.

Esses conjuntos mutuamente incomparáveis ​​precisam ser detectados primeiro, antes que os objetos possam ser armazenados em uma estrutura de dados apropriada. Isso pode ser feito com um algoritmo de localização da União

---

Para eficiência, a inserção de um novo objeto precisa ter uma maneira eficiente de encontrar "a lista de objetos existentes que são comparáveis ​​a esse novo objeto".

---

Agora, dentro de cada subconjunto (respectivamente {a, b, c}e {d, e}), os mínimos devem ser bem definidos. (Para cada subconjunto, pode haver um ou mais mínimos, devido a pedidos parciais.)

Eu vejo isso como um gráfico acíclico direcionado . Tentar encaixá-lo em uma pilha parece desastroso.

---

Para extrair os mínimos dessa estrutura de dados composta, a próxima etapa é obter a lista de todos os mínimos de todos os subconjuntos, escolher aquele com o carimbo de data / hora mais antigo e remover e retornar este objeto.

Um projeto em que estou trabalhando envolve um problema semelhante (aliás, também estou usando a ordem parcial de vetores). Já tínhamos um algoritmo de tempo quadrático para classificar uma lista ordenada aleatoriamente, e desenvolvi um algoritmo de inserção observando seu comportamento quando apenas um objeto estava fora de ordem. Não sabemos se essa é a implementação mais rápida possível.

Aqui está algum pseudocódigo.

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)

O comportamento usual da pilha é anexar o novo valor à parte traseira e, em seguida, peneirar enquanto ele compara maior que o pai.

Se você escrever uma comparação que retorne o mesmo para o pai e o filho não é um caso comparável , pois o pai é maior que o filho , a peneiração ainda deve terminar no ponto certo.

Isso conta como um pedido suficientemente estável para seus propósitos?

---

Para esclarecer, tomar o exemplo do seu comentário: a> b e c não é comparável a um ou b :

• a então b então c => a, b, c ... isso já está em ordem de pilha e nada se move na peneiração
• b, a, c => a, b, c ... a é peneirado no lugar correto e, novamente, estamos na ordem correta da pilha
• a, c, b => a, c, b ... b não pode filtrar porque não é comparável com c, mas isso os deixa na ordem FIFO, como você pediu
• c, b, a => c, a, b ... aeb estão na ordem relativa correta, mas nenhum deles pode se antecipar a c porque não pode ser comparado a ele

portanto, o resultado depende da ordem de inserção - isso parece corresponder ao que você solicita, mas não tenho certeza se é realmente o que você deseja. Caso contrário, você poderia mostrar o resultado que esperava ver?

---

OK, então, a partir do seu comentário (e da edição da sua pergunta), você deseja que elementos "comparáveis" ultrapassem os "não comparáveis" e encontre o local correto sob a ordem, se houver um. Eu perguntei sobre isso, porque eu não tinha certeza de como interpretar

se alguns elementos são incomparáveis, ele os retorna na ordem em que foram inseridos

(d e b são incomparáveis ​​aos pares na sua edição, mas você não os deseja na ordem em que foram inseridos).

Minha próxima pergunta seria sobre a relação entre os elementos "comparáveis" e "não comparáveis", mas vejo que você revelou agora que são vetores em ordem de produto (não ficou claro se alguns elementos eram pareados) incomparável com tudo , como NaN, ou o que).

Portanto, se eu pegar seu novo exemplo e atribuir valores de vetor, é correto que este seja um exemplo em que b não seja comparável a qualquer outra coisa:

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

e deve classificar para isso:

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

?