Cola de prioridad para prioridades parcialmente ordenadas con infima

16

Tengo algunos objetos con prioridad que son de tipo compuesto y solo están parcialmente ordenados . Necesito seleccionar los objetos en orden de esta prioridad (es decir, producir un elemento mínimo cada vez). Pero en lugar de completar arbitrariamente el pedido, preferiría que la cola fuera estable en el sentido de que si hay más de un elemento mínimo, debería devolver el más antiguo primero.

¿Existe alguna estructura de datos de montón que funcione con un pedido parcial? ¿O una modificación de la cola de prioridad regular para trabajar con ella? La elección común para el algoritmo que necesito es un binario simple o un montón de 4 arios, pero eso no funciona con un pedido parcial.

Los valores de prioridad soportan:

$\preccurlyeq$ $a \preccurlyeq b$ $b \preccurlyeq a$ $a \not\lesseqgtr b$
Encontrar infima (glb) y suprema (lub). $\inf(x_i)$ es la máxima $y$ tal que $y \preccurlyeq x_i$ . Calcular el valor mínimo de $n$ valores toma $O(n)$ tiempo. Existe una cantidad mínima (y superior) de cada conjunto.
Se podría definir una extensión lineal para el ordenamiento parcial. Usarlo para la cola de prioridad es la salida fácil ya que el algoritmo funciona de esa manera. Pero el orden afecta el rendimiento y el orden de inserción parece ser el mejor para evitar los peores casos.

Además, el algoritmo en el que quiero usar esto necesita saber poco de todas las prioridades en la cola.

Las prioridades tienen algún significado en el mundo real, pero están sujetas a cambios, por lo que no parece viable confiar en otras propiedades que podrían tener.

Nota: los montones binarios no funcionan con pedidos parciales. Supongamos un montón binario con $a$ , $b$ y $c$ , donde $a \preccurlyeq c$ y $a \not\lesseqgtr b$ y $a \not\lesseqgtr c$ . Están posicionados en ese orden, así que

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

ahora se inserta d . La siguiente posición libre es 3, el hijo izquierdo de $b$ , entonces obtenemos

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

Si (que implica de la transitividad, pero no dice nada acerca de y ) y , entonces no se intercambia con , porque no es menor. Pero en realidad es menor que , pero no se compara con él, por lo que ahora el principal montón invariante no se mantiene; La parte superior no es mínima. $d \preccurlyeq a$ $d \preccurlyeq c$ $d$ $b$ $d \not\lesseqgtr b$ $d$ $b$ $a$

Sospecho que se podría hacer funcionar un bosque de montones en cierto modo de montón binomial. Básicamente, es importante comparar siempre los valores nuevos con la raíz y solo vincular elementos comparables. Haría que los árboles en el bosque tuvieran un tamaño aleatorio y, por lo tanto, la complejidad dependería del número de conjuntos mutuamente incomparables en el montón. Sospecho un tanto que la complejidad no se puede solucionar (tenemos que seguir comparando hasta que lleguemos a un elemento comparable) Podría haber pasado algo por alto, así que lo dejo abierto.

Nota: El orden es parcial y, aunque existen formas de definir extensiones lineales para él, agregar una marca de tiempo y usarlo como criterio secundario no es una de ellas. Supongamos que asignamos la marca de tiempo para cada y definimos el orden como iff o ( y . Entonces supongamos que tenemos distintos , , , de modo que y . Entonces y $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$ , pero , por lo que la relación no es transitiva y, por lo tanto, no es un orden en absoluto. Este tipo de extensión solo funciona para pedidos débiles, pero no parciales. $c \preccurlyeq' a$

Editar: me di cuenta de que no solo se define un mínimo de cualquier conjunto, sino que en realidad necesito poder obtener un mínimo de elementos actualmente en la cola de manera eficiente. Así que ahora estoy considerando si ayudaría agregar nodos especiales que contengan infima de subárboles a alguna estructura de montón común.

data-structures priority-queues Jan Hudec
fuente

¿Ha considerado una cola de prioridad indexada?

@hulkmeister: ¿Podría explicar cómo tener la cola indexada hace que funcione con un pedido parcial (no, el montón binario simple no funciona con un pedido parcial)?

1

Pensé que cuando dos elementos son incomparables, puede usar el índice para rastrear el orden de inserción. Entonces, componga la prioridad con el índice, y tendrá claves únicas que son comparables incluso cuando la prioridad no lo es. Si esto suena como lo que quieres, puedo ponerlo en una respuesta completa.

1

@hulkmeister: Bueno, el problema es mucho más profundo que eso. Cuando se inserta un nuevo elemento, la cola de prioridad normalmente lo compara con algún elemento. Pero si son incomparables, simplemente no sabe dónde insertarlo. Y la desambiguación con el índice no funcionará, porque el índice cambia y porque probablemente no daría un orden total consistente con la prioridad de todos modos.

¿Puedes dar algún ejemplo de este tipo compuesto, y cuando es incomparable? ¿Es posible considerar estos valores 'incomparables' iguales? Si es así, puede almacenarlos en el mismo nodo en orden de inserción.

3

Aunque el problema exacto planteado en la pregunta original parece ser difícil (y estaría interesado en una solución a ese problema, especialmente la parte de búsqueda de infima). Solo quería señalar que si el conjunto parcialmente ordenado de hecho consiste en vectores que utilizan un pedido de producto, y si es suficiente con tener la garantía de que la cola de prioridad devuelve los valores en un orden que es "compatible" con el pedido parcial ( es decir, los elementos más pequeños siempre se devuelven antes que los elementos más grandes), entonces hay una manera bastante fácil de hacerlo.

La idea es esencialmente encontrar un orden topológico del conjunto parcialmente ordenado. Es decir, un orden total ' ' tal que $\le_T$ . Para los vectores que usan un pedido de producto, esto es bastante fácil: simplemente use un orden lexicográfico ' ', donde el primer "componente" es la suma de todos los componentes utilizados para el pedido del producto (el resto de los componentes son esencialmente arbitrarios, para que también puedas seguir un orden débil). Entonces podemos ver que $\mathbf{a}\le\mathbf{b}\implies \mathbf{a}\le_T\mathbf{b}$ $\le_S$ y

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}$

y por lo tanto

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},$

. Por lo tanto, podemos usar este orden con una cola prioritaria y asegurarnos de que los elementos más pequeños (en el pedido del producto) siempre se extraerán antes que los elementos más grandes.

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

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

Jaspe
fuente

Hay muchas más opciones. Usando uno de los componentes, mínimo, máximo, cualquier combinación lineal con coeficientes no negativos al menos. La elección de la extensión afecta la rapidez del algoritmo de superposición.

Jan Hudec

2

¿Qué hay de malo en completar su pedido parcial?

Pero en lugar de completar arbitrariamente el pedido, preferiría que la cola fuera estable en el sentido de que si hay más de un elemento mínimo, debería devolver el más antiguo primero.

Si prefiere 'el más antiguo primero', entonces su pedido está efectivamente completado; Los artículos "incomparables" son comparables por edad.

Agregue una marca de tiempo (o cualquier otro número entero de crecimiento monótono) a cada elemento y úselo si la comparación 'real' es imposible.

fuente

3

Eso sería genial si pudiera hacerse una extensión lineal del ordenamiento parcial. Pero no lo es. Tengamos 3 valores distintos, insertados en el orden a , b , c , de modo que c ≤ a y b sea incomparable con cualquiera de los dos. La extensión con rellenos de marca de tiempo en un 'b ≤ y b ≤' c , así que desde transitividad ahora un debe ser inferior a c , pero que contradice el orden real.

Quizás lo confundiste con un orden débil. En un orden débil, los elementos incomparables forman clases de equivalencia, por lo que puede agregar criterios adicionales arbitrarios. Para pedidos parciales no puedes.

1

EDITAR: esto parece ser un problema interesante, y tuve un poco de investigación al respecto. Te sugiero que leas lo siguiente:

Darell Raymond. Bases de datos de orden parcial, tesis doctoral, Universidad de Waterloo.

Le sugiero que lea este artículo: Daskalakis, Constantinos, et al. "Clasificación y selección en posets". SIAM Journal on Computing 40.3 (2011): 597-622.

Los autores presentan aquí una estructura de datos llamada ChainMerge que acepta un poset y una descomposición en cadena del poset en cadenas. El tamaño de la estructura de datos es . Los autores presentan un algoritmo para encontrar las minimas que se ejecutan en donde es un límite superior en el ancho del poset. .. Pensé que tal vez esto es interesante. $q$ $O(n q)$ $O(w n)$ $w$

Nota: eliminé una respuesta ingenua anterior. Haga clic en editar para verlo.

AJed
fuente

0

Mi uso de la terminología puede ser incorrecto. Edite mi respuesta directamente para solucionar cualquier problema que encuentre.

Primero, los conjuntos mutuamente incomparables necesitan ser detectados desde las entradas.

Por ejemplo, puede haber 5 objetos a, b, c, d, e, pero su ordenamiento parcial forma dos gráficos desconectados:

a ≤ b ≤ c
d ≤ e
pero ninguno de {a, b, c}es incomparable con ninguno de {d, e}.

Estos conjuntos mutuamente incomparables deben detectarse primero, antes de que los objetos puedan almacenarse en una estructura de datos adecuada. Esto se puede hacer con un algoritmo de búsqueda de unión

Para mayor eficiencia, la inserción de un nuevo objeto debe tener una manera eficiente de encontrar "la lista de objetos existentes que son comparables con este nuevo objeto".

Ahora, dentro de cada subconjunto (respectivamente {a, b, c}y {d, e}), los mínimos deben estar bien definidos. (Para cada subconjunto puede haber uno o más mínimos, debido a un pedido parcial).

Veo esto como un gráfico acíclico dirigido . Intentar encajarlo en un montón parece desastroso.

Para extraer los mínimos de esta estructura de datos compuesta, el siguiente paso es obtener la lista de todos los mínimos de todos los subconjuntos, elegir el que tenga la marca de tiempo más temprana y eliminar y devolver este objeto.

rwong
fuente

Desafortunadamente, no veo la manera de encontrar eficientemente la lista de objetos comparables.

El conjunto parcialmente ordenado puede verse como un gráfico acíclico dirigido. Pero uno dado por la tabla de adyacencia (función, en realidad) en lugar de la lista de adyacencia. Encontrar mínimos de poset dados por la lista de adyacencia es fácil, pero para la tabla de adyacencia es un problema.

Los mínimos también están bien definidos en el conjunto original. No veo cómo encontrar los componentes conectados podría ayudar, ya que no son gráficos completos.

1

Parece suponer que el diagrama de Hasse es un bosque de árboles unarios (equivalentes gráficas de ruta), pero la pregunta ya indica que es un pedido de producto, por lo que es una red multidimensional.

Peter Taylor

0

Un proyecto en el que estoy trabajando implica un problema similar (por cierto, también estoy usando el orden parcial de los vectores). Ya teníamos un algoritmo de tiempo cuadrático para ordenar una lista ordenada aleatoriamente, y desarrollé un algoritmo de inserción al observar su comportamiento cuando solo un objeto estaba fuera de servicio. No sabemos si esta es o no la implementación más rápida posible.

Aquí hay un 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)

Jeremy List
fuente

-1

El comportamiento habitual del montón es agregar el nuevo valor a la parte posterior y luego tamizarlo mientras se compara más que su padre.

Si escribe una comparación que devuelve lo mismo para el padre y el hijo, el caso no es comparable , ya que el padre es mayor que el hijo , la separación aún debe terminar en el punto correcto.

¿Eso cuenta como un pedido suficientemente estable para sus propósitos?

Para aclarar, tome el ejemplo de su comentario: a> b , y c no es comparable a una o b :

a luego b luego c => a, b, c ... esto ya está en orden de almacenamiento dinámico, y nada se mueve en el cribado
b, a, c => a, b, c ... a se tamiza en su lugar correcto, y nuevamente estamos en el orden correcto de almacenamiento dinámico
a, c, b => a, c, b ... b no puede filtrarse porque no es comparable con c, pero esto los deja en el orden FIFO como usted pidió
c, b, a => c, a, b ... a y b están en el orden relativo correcto, pero ninguno puede adelantarse a c porque no se pueden comparar con él

por lo tanto, el resultado depende del orden de inserción; esto parece coincidir con lo que solicita, pero no estoy seguro de si realmente es lo que desea. Si no es así, ¿podría mostrar el resultado que esperaba ver?

De acuerdo, por su comentario (y la edición de su pregunta), desea elementos "comparables" para saltar los "no comparables" y encontrar el lugar correcto bajo el pedido, si hay uno. Pregunté sobre esto porque no estaba seguro de cómo interpretar

Si algunos elementos son incomparables, los devuelve en el orden en que se insertaron

(d y b son incomparables por pares en su edición, pero usted no los quiere en el orden en que se insertaron).

Mi siguiente pregunta habría sido sobre la relación entre los elementos "comparables" y "no comparables", pero veo que ahora has revelado que son vectores en orden de producto (no estaba claro si algunos elementos eran pares) incomparable con todo , como NaN, o qué).

Entonces, si tomo su nuevo ejemplo y asigno valores de vectores, ¿es correcto que este sea un ejemplo en el que b no sea comparable a ninguna otra cosa?

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

y debería ordenar esto:

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

?

Inútil
fuente

Mencioné explícitamente en la pregunta que no funcionará, porque pensé que tenía un contraejemplo, pero ahora no estoy tan seguro. ¿Puede probar que esa cola sería buena (para deletemin, insertar y actualizar también)? Y recuerde que es posible que a ≤ b , pero c no es comparable (y, por lo tanto, compararía "igual" con la regla anterior) a cualquiera de ellos.

Bueno, eso aún no es una prueba. No se preocupe aún por el pedido y pruebe que dicho montón siempre tiene un elemento mínimo en la parte superior (nota: (más) convención común y la necesidad real del algoritmo es mínima en la parte superior, por lo que si a> b , b es lo primero )

En realidad sospecho que hay un contraejemplo. Supongamos un , b y c están en el montón, a ≤ b y a ≤ c , una es la parte superior, b es hijo izquierdo, c es hijo derecho. Ahora viene d que d ≤ c e incomparable con a y b . Se inserta como hijo de b , no es menos y se queda allí. Ahora viene e que es c ≤ e (por lo tanto también a ≤ e ) e incomparable a b . Así e entra como hijo derecho de by se queda. Ahora extraiga a (OK, a es mínimo), e se intercambia en su lugar y se tamiza. Es incomparable con b , pero menor que c , por lo que se intercambia con c . Ahora extraiga c , INCORRECTO , d ≤ c .

Si encuentra un error en el comentario anterior (que necesitaría tener una forma de desigualdad que debe mantenerse debido a la transitividad y lo perdí), aún tendría una oportunidad. De lo contrario, no funcionará.

1

Ok, un contraejemplo aún más simple. Supongamos un , b y c están en el montón, a ≤ c , b es incomparable con cualquiera. a es superior, b es hijo secundario, c es hijo secundario. d entra de modo que d ≤ a (por lo tanto d ≤ c ) e incomparable con b . Ranura libre al lado es como hijo izquierdo de b y d es incomparable, por lo que se queda allí. Ahora extraer un , INCORRECTO , d ≤ a . Tenga en cuenta que si a ≤ co no importa, la situación es la misma si fueran incomparables.

Cola de prioridad para prioridades parcialmente ordenadas con infima

Respuestas: