Ordenar elementos para que algunos elementos no se interpongan entre otros.

Dado un entero y un conjunto de tripletes de enteros distintos encuentre un algoritmo que encuentre una permutación del conjunto tal que o determina correctamente que no existe tal permutación. Menos formalmente, queremos reordenar los números del 1 al ; cada Triple en indica que debe aparecer antes de en el nuevo orden, pero no debe aparecer entre $n$

S \subseteq {(i, j, k) ∣ 1 \leq i, j, k \leq n, i \neq j, j \neq k, i \neq k},

$S \subseteq \{(i, j, k) \mid 1\le i,j,k \le n, i \neq j, j \neq k, i \neq k\},$

π

$\pi$

{1, 2, \dots, n}

$\{1, 2, \dots, n\}$

(i, j, k) \in S ⟹ (π (j) < π (i) < π (k)) \lor (π (i) < π (k) < π (j))

$(i,j,k) \in S \implies (\pi(j)<\pi(i)<\pi(k)) ~\lor~ (\pi(i)<\pi(k)<\pi(j))$

n

$n$

(i, j, k)

$(i,j,k)$

S

$S$

i

$i$

k

$k$

j

$j$

i

$i$ y .

k

$k$

Ejemplo 1

Supongamos que y . Luego $n=5$ $S = \{(1,2,3), (2,3,4)\}$

$\pi = (5, 4, 3, 2, 1)$ no es una permutación válida, porque , pero . $(1, 2, 3)\in S$ $\pi(1) > \pi(3)$
$\pi = (1, 2, 4, 5, 3)$ no es una permutación válida, porque pero . $(1, 2, 3) \in S$ $\pi(1) < \pi(3) < \pi(5)$
$(2, 4, 1, 3, 5)$ es una permutación válida.

Ejemplo 2

Si y , no hay permutación válida. Del mismo modo, no hay permutación válida si y ( Creo que puede haber cometido un error aquí). $n=5$ $S = \{(1, 2, 3), (2, 1, 3)\}$ $n=5$ $S = \{(1,2,3), (3,4,5), (2,5,3), (2,1,4)\}$

Bonificación: ¿Qué propiedades de determinan si existe una solución factible? $S$

algorithms optimization scheduling Patrick87
fuente

¿Por qué no reformular la segunda condición como ? Entonces tiene un problema de satisfacción de restricciones más o menos sencillo. (Tenga en cuenta que he simplificado la condición en función de los otros supuestos).

(σ_{m_{i}}, σ_{m_{j}}, σ_{m_{k}}) \in S ⟹ (i > j \lor j > k)

$(\sigma_{m_i},\sigma_{m_j},\sigma_{m_k})\in S\Longrightarrow (i>j \vee j>k)$

Dave Clarke

Por cierto: ¿Cuál es la motivación para este problema?

Dave Clarke el

@DaveClarke Vea mi edición. Este problema se ha extraído de una discusión en torno a un problema de programación que estaba discutiendo con otros estudiantes en el laboratorio. Básicamente, la idea es que tenga muchos trabajos, algunos de los cuales deben ejecutarse en un orden determinado. Sin embargo, no desea que se programen algunos trabajos entre trabajos en una secuencia, posiblemente por razones muy sutiles.

Patrick87

¿Por qué las sigmas? Simplemente defina . Los subíndices anidados hacen llorar al niño Jesús.

Σ = {1, 2, \dots, n}

$\Sigma = \{1,2,\dots,n\}$

JeffE

@JeffE Honestamente, me gusta la excusa para jugar con la ecuación. Hay algo simplemente visceralmente satisfactorio sobre escribir código que se compila a esos pequeños 's. No me quites eso , hombre.

σ

$\sigma$

Patrick87

Respuestas:

Aquí hay un algoritmo ingenuo. En última instancia, depende de la fuerza bruta, pero a veces puede funcionar bien.

Cada restricción consta de dos conjuntos; llamémoslos tipo- , , y tipo- , . Cada restricción de tipo se puede escribir de manera equivalente como una disyunción , basándose en el hecho de que . $(\sigma_{m_i}, \sigma_{m_j}, \sigma_{m_k}) \in S \implies i < k \wedge \neg(i < j < k)$ $A$ $i < k$ $B$ $\neg(i < j < k)$ $B$ $i>j \vee j>k$ $i\neq j,j\neq k$

Recoge todas las restricciones de tipoLlama a esto . Compruebe si son consistentes, es decir, que se trata de una linealización de la ordenación. Esto toma -time en el número de restricciones usando la ordenación topológica. $A$ $\Theta$ $O(|S|)$
Para cada uno de los disyuntos en la restricción de tipo , verifique si es consistente con el orden parcial . Si no es consistente, elimine la disyunción. Si ambos disjuntos son inconsistentes con , entonces falla. Siempre que se elimine una restricción de tipo , agregue la restante a . Este paso es . $B$ $\Theta$ $\Theta$ $B$ $\Theta$ $O(|S|^2)$
Ahora hay un algoritmo obvio para encontrar una solución, a saber, considerar todas las combinaciones de los pares de disyunción tipo y probar su consistencia con , pero esto es claramente exponencial en. Una heurística para mejorar el rendimiento sería tratar los pares de disyunción tipo como las ramas de un árbol: un par forma la raíz, sus hijos son dados por el segundo par, sus hijos por el tercero y así sucesivamente. Usando esta estructura de datos, se encuentra una solución atravesando el árbol de una manera profunda primero. Cada vez que se agrega una nueva restricción (usando la etiqueta en una rama), se puede verificar la consistencia. Los subárboles inconsistentes pueden ser podados. $B$ $\Theta$ $|S|$
$B$
Si se alcanza una hoja del árbol, entonces tenemos un conjunto consistente de restricciones que consisten en todas las restricciones de tipo y una disyunción de las restricciones de tipoLinealice el resultado para obtener el orden deseado. $A$ $B$

Mi enfoque preferido sería codificarlo en un conjunto de restricciones y usar un solucionador de restricciones como Choco. Introduciría variables enteras en el rango y requeriría que todas fueran distintas. Luego codificaría cada una de las restricciones anteriores directamente como restricciones y luego dejaría que Choco haga su negocio. $n$ $x_i$ $[0,n-1]$

Dave Clarke
fuente

Aquí hay una respuesta parcial:

Si elimina la restricción en cada triple, entonces su problema se convierte en el problema de No-Betweeness, que es completo y no se conocen algoritmos eficientes para tales problemas. Pero con la restricción , puede forzar alguna estructura agradable que puede ser explotada para encontrar un algoritmo de tiempo polinómico para su problema. $i \lt k$ $NP$ $i \lt k$

Mohammad Al-Turkistany
fuente