Ordenando elementos para que alguns elementos não fiquem entre outros

Dado um número inteiro e um conjunto de trigêmeos de números inteiros distintos encontre um algoritmo que encontre uma permutação do conjunto modo que ou determina corretamente que não existe tal permutação. Menos formalmente, queremos reordenar os números de 1 a ; cada triplo em indica que deve aparecer antes no novo pedido, mas não deve 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$ e .

k

$k$

Exemplo 1

Suponha que e . Então $n=5$ $S = \{(1,2,3), (2,3,4)\}$

$\pi = (5, 4, 3, 2, 1)$ não é uma permutação válida, porque , mas . $(1, 2, 3)\in S$ $\pi(1) > \pi(3)$
$\pi = (1, 2, 4, 5, 3)$ não é uma permutação válida, porque mas . $(1, 2, 3) \in S$ $\pi(1) < \pi(3) < \pi(5)$
$(2, 4, 1, 3, 5)$ é uma permutação válida.

Exemplo 2

Se e , não há permutação válida. Da mesma forma, não há permutação válida se e ( Eu acho que pode ter cometido um erro aqui). $n=5$ $S = \{(1, 2, 3), (2, 1, 3)\}$ $n=5$ $S = \{(1,2,3), (3,4,5), (2,5,3), (2,1,4)\}$

Bônus: Quais propriedades de determinam se existe uma solução viável? $S$

algorithms optimization scheduling Patrick87
fonte

Por que não reformular a segunda condição como ? Então você tem um problema direto, mais ou menos, de satisfação com restrições. (Note que eu simplificou a condição com base nos outros pressupostos.)

(σ_{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

BTW: Qual é a motivação para este problema?

Dave Clarke

@DaveClarke Veja minha edição. Esse problema foi extraído de uma discussão em torno de um problema de agendamento que eu estava discutindo com alguns outros alunos do laboratório. Basicamente, a idéia é que você tenha muitos trabalhos, alguns dos quais precisam ser executados em uma determinada ordem. No entanto, você não deseja que alguns trabalhos sejam agendados entre trabalhos em uma sequência, possivelmente por motivos muito sutis.

Patrick87

Por que os sigmas? Basta definir . Inscritos aninhados fazem o menino Jesus chorar.

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

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

Jeffe

@ Jeffe Honestamente, eu só gosto da desculpa de brincar com a coisa da equação. Há algo visceralmente satisfatório em escrever código que se compila aos pequenos 's. Não tire isso de mim, cara.

σ

$\sigma$

precisa saber é o seguinte

Respostas:

Aqui está um algoritmo ingênuo. Em última análise, depende de força bruta, mas pode funcionar bem algumas vezes.

Cada restrição consiste em dois conjuntos; vamos chamá-los de tipo , e tipo , . Cada restrição do tipo pode ser escrita de forma equivalente como uma disjunção , baseando-se no fato 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$

Colete todas as restrições do tipoChame isso de . Verifique se eles são consistentes, ou seja, se essa é uma linearização da ordem. Isso leva tempo no número de restrições usando a classificação topológica. $A$ $\Theta$ $O(|S|)$
Para cada um dos disjuntores na restrição de tipo , verifique se é consistente com a ordem parcial . Se não for consistente, remova o disjuntor. Se os dois disjuntores forem inconsistentes com , falhe. Sempre que apenas uma restrição do tipo for removida, adicione a restante a . Esta etapa é . $B$ $\Theta$ $\Theta$ $B$ $\Theta$ $O(|S|^2)$
Agora, existe um algoritmo óbvio para encontrar uma solução, ou seja, considerar todas as combinações dos pares de disjunção do tipo e testar sua consistência com , mas isso é claramente exponencial em. Uma heurística para melhorar o desempenho seria tratar os pares de disjunção tipo como os galhos de uma árvore - um par forma a raiz, seus filhos são dados pelo segundo par, seus filhos pelo terceiro e assim por diante. Usando essa estrutura de dados, é encontrada uma solução percorrendo a árvore de maneira profunda. Cada vez que uma nova restrição é adicionada (usando o rótulo em uma ramificação), a consistência pode ser verificada. Subárvores inconsistentes podem ser removidas. $B$ $\Theta$ $|S|$
$B$
Se uma folha da árvore for alcançada, teremos um conjunto consistente de restrições consistindo em todas as restrições do tipo e um disjuntor das restrições do tipoLinearize o resultado para obter a ordem desejada. $A$ $B$

Minha abordagem preferida seria, na verdade, codificá-la em um conjunto de restrições e usar um solucionador de restrições como o Choco. Eu introduziria variáveis inteiras no intervalo e exigiria que todas fossem distintas. Então eu codificaria cada uma das restrições acima diretamente como restrições e deixaria a Choco fazer negócios. $n$ $x_i$ $[0,n-1]$

Dave Clarke
fonte

Aqui está uma resposta parcial:

Se você remover a restrição em cada triplo, seu problema se tornará o problema Sem-Interesse, que é -completo e não há algoritmos eficientes conhecidos para tais problemas. Mas com a restrição , pode forçar uma estrutura agradável que pode ser explorada para encontrar um algoritmo de tempo polinomial para o seu problema. $i \lt k$ $NP$ $i \lt k$

Mohammad Al-Turkistany
fonte