come ordinare un set quando gli elementi hanno più relazioni tra loro

Question

Sto cercando un algoritmo per eseguire una sorta di ordinamento di array esteso quando le relazioni tra gli elementi possono contraddirsi l'una con l'altra.

quindi abbiamo un set di I (voci), composto da n articoli i1 ... in

V'è una serie R (relazioni) che consiste di m relazioni definite tra articoli in I

le relazioni possono contraddirsi a vicenda in modo che, ad esempio, una relazione dice che A>B e l'altra th allo A<B.

ad es.

r1:i1<i35 

r2:i100<i4 

... 

rm:i45>i3 

generalmente, r e m (dimensioni di insiemi) può essere qualsiasi interi positivi.

il compito è quello di ordinare I così le voci di andare in modo tale che preferibilmente quelle inferiori (sulla base di rapporti) vanno prima di quelli più alti ...

Sto cercando un algoritmo che ordinerà l'insieme in modo che sia il più vicino possibile all'ordine "ottimale". Immagino che ci debba essere un algoritmo ben noto per risolvere problemi come questo.

Grazie!

Answer 1

Penso che il modo più ragionevole per misurare la qualità di un determinato ordinamento è il numero di determinati rapporti che esso viola. Se si decide di utilizzare questa misura, il problema è equivalente a (Minimum) Feedback Arc Set. Sfortunatamente, questo problema è NP-difficile, quindi è probabile che non esista un algoritmo efficiente (tempo polinomiale).

Nel problema Arco di feedback, viene fornito un grafico diretto e viene chiesto di trovare un set di bordi di dimensioni minime che, se cancellato, distruggerebbe tutti i cicli del grafico.

Per vedere come questo corrisponde al tuo problema, osserva che possiamo rappresentare ogni elemento come un vertice in un grafico, e ogni relazione come un bordo diretto tra due vertici (puntando a, diciamo, quello più piccolo). C'è un conflitto se e solo se v'è una ciclo in questo grafico - cioè, se v'è un elenco ordinato di 2 o più distinti vertici v_1, V_2, ..., v_k tale che v_i < V_ (i +1) per tutti i i < k e anche v_k < v_1. È impossibile ordinare questi k vertici senza violare almeno un vincolo. Viceversa, se non esiste alcun ciclo - cioè, se il grafico è un directed acyclic graph - allora topological sort può rapidamente (in tempo lineare) trovare un ordine valido che non violi vincoli. Quindi la dimensione di un arco di feedback impostato è il più piccolo numero di spigoli che dovresti rimuovere per ottenere un grafico che può essere ordinato senza violare alcun vincolo - o, in modo equivalente, il più piccolo numero di spigoli che deve essere violato in qualsiasi ordinamento.