Elemente so anordnen, dass einige Elemente nicht zwischen anderen stehen

Gegeben sei eine ganze Zahl und eine Menge von Tripletts unterschiedlicher Ganzzahlen finde einen Algorithmus, der entweder eine Permutation der Menge so dass oder bestimmt korrekt, dass keine solche Permutation existiert. Weniger formal wollen wir die Zahlen 1 bis neu ordnen ; Jedes Tripel in zeigt an, dass in der neuen Reihenfolge vor erscheinen muss , aber darf nicht zwischen erscheinen $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$ und .

k

$k$

Beispiel 1

Angenommen, und . Dann $n=5$ $S = \{(1,2,3), (2,3,4)\}$

$\pi = (5, 4, 3, 2, 1)$ ist keine gültige Permutation, weil , sondern . $(1, 2, 3)\in S$ $\pi(1) > \pi(3)$
$\pi = (1, 2, 4, 5, 3)$ ist keine gültige Permutation, da aber . $(1, 2, 3) \in S$ $\pi(1) < \pi(3) < \pi(5)$
$(2, 4, 1, 3, 5)$ ist eine gültige Permutation.

Beispiel 2

Wenn und , gibt es keine gültige Permutation. Ebenso gibt es keine gültige Permutation, wenn und ( Ich denke, vielleicht hat hier ein Fehler gemacht. $n=5$ $S = \{(1, 2, 3), (2, 1, 3)\}$ $n=5$ $S = \{(1,2,3), (3,4,5), (2,5,3), (2,1,4)\}$

Bonus: Welche Eigenschaften von bestimmen, ob eine praktikable Lösung existiert? $S$

algorithms optimization scheduling Patrick87
quelle

Warum formulieren Sie die zweite Bedingung nicht als ? Dann haben Sie ein einfaches, mehr oder weniger problematisches Problem. (Beachten Sie, dass ich die Bedingung basierend auf den anderen Annahmen vereinfacht habe.)

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

Übrigens: Was ist die Motivation für dieses Problem?

Dave Clarke

@ DaveClarke Siehe meine Bearbeitung. Dieses Problem wurde aus einer Diskussion über ein Planungsproblem, das ich mit einigen anderen Studenten im Labor besprochen habe, abstrahiert. Grundsätzlich besteht die Idee darin, dass Sie viele Jobs haben, von denen einige in einer bestimmten Reihenfolge ausgeführt werden müssen. Sie möchten jedoch nicht, dass einige Jobs zwischen Jobs in einer Sequenz geplant werden, möglicherweise aus sehr subtilen Gründen.

Patrick87

Warum die Sigmas? Definieren Sie einfach . Verschachtelte Indizes bringen das Jesuskind zum Weinen.

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

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

JeffE

@ JeffE Ehrlich gesagt, ich mag nur die Ausrede, mit der Gleichungssache zu spielen. Das Schreiben von Code, der zu diesen kleinen kompiliert wird, ist nur viszeral befriedigend . Nehmen Sie nicht , dass von mir, Mann.

σ

$\sigma$

Patrick87

Antworten:

Hier ist ein naiver Algorithmus. Es beruht letztendlich auf roher Gewalt, kann aber manchmal in Ordnung sein.

Jede Einschränkung aus zwei Konjunktionen besteht; Nennen wir sie Typ , und Typ , . Jede Einschränkung vom Typ kann äquivalent als Disjunktion , wobei auf die Tatsache zurückgegriffen wird, dass . $(\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$

Sammeln Sie alle Einschränkungen vom TypNennen Sie das . Überprüfen Sie, ob sie konsistent sind, nämlich dass dies eine Linearisierung der Reihenfolge ist. Dies benötigt -Zeit für die Anzahl der Einschränkungen unter Verwendung der topologischen Sortierung. $A$ $\Theta$ $O(|S|)$
Überprüfen Sie für jedes der Disjunkte in der Einschränkung vom Typ , ob es mit der Teilreihenfolge übereinstimmt . Wenn es nicht konsistent ist, entfernen Sie das Disjunct. Wenn beide Disjunkte nicht mit übereinstimmen, fehl. Wenn nur eine Einschränkung vom Typ entfernt wird, fügen Sie die verbleibende zu . Dieser Schritt ist . $B$ $\Theta$ $\Theta$ $B$ $\Theta$ $O(|S|^2)$
Nun gibt es einen offensichtlichen Algorithmus, um eine Lösung zu finden, nämlich alle Kombinationen der Typ- Disjunktionspaare zu berücksichtigen und ihre Konsistenz mit testen , aber dies ist in eindeutig exponentiell . Eine Heuristik zur Verbesserung der Leistung wäre, die Typ- Disjunktionspaare als Zweige eines Baumes zu behandeln - ein Paar bildet die Wurzel, seine Kinder werden vom zweiten Paar gegeben, ihre Kinder vom dritten und so weiter. Unter Verwendung dieser Datenstruktur wird eine Lösung gefunden, indem der Baum in der Tiefe zuerst durchlaufen wird. Jedes Mal, wenn eine neue Einschränkung hinzugefügt wird (mithilfe der Beschriftung eines Zweigs), kann die Konsistenz überprüft werden. Inkonsistente Teilbäume können beschnitten werden. $B$ $\Theta$ $|S|$
$B$
Wenn ein Blatt des Baums erreicht ist, haben wir einen konsistenten Satz von Einschränkungen, der aus allen Einschränkungen vom Typ und einem Disjunkt der Einschränkungen vom Typ . Linearisieren Sie das Ergebnis, um die gewünschte Reihenfolge zu erhalten. $A$ $B$

Mein bevorzugter Ansatz wäre es, ihn in eine Reihe von Einschränkungen zu codieren und einen Einschränkungslöser wie Choco zu verwenden. Ich würde ganzzahlige Variablen im Bereich einführen und verlangen, dass sie alle verschieden sind. Dann würde ich jede der oben genannten Einschränkungen direkt als Einschränkungen codieren und dann Choco das Geschäft machen lassen. $n$ $x_i$ $[0,n-1]$

Dave Clarke
quelle

Hier ist eine teilweise Antwort:

Wenn Sie die Einschränkung für jedes Tripel entfernen, wird Ihr Problem zum Non-Betweeness-Problem, das vollständig ist, und es sind keine effizienten Algorithmen für solche Probleme bekannt. Mit der Einschränkung kann jedoch eine nette Struktur erzwungen werden, die ausgenutzt werden kann, um einen Polynomzeitalgorithmus für Ihr Problem zu finden. $i \lt k$ $NP$ $i \lt k$

Mohammad Al-Turkistany
quelle