Porządkowanie elementów, aby niektóre elementy nie znajdowały się między innymi

Biorąc pod uwagę liczbę całkowitą $n$ i zestaw trojaczków różnych liczb całkowitych

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\},$ znajdź algorytm, który albo znajduje permutację

π

$\pi$ zbioru

{1, 2, \dots, n}

$\{1, 2, \dots, n\}$ taką, że

(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))$ lub poprawnie określa, że taka permutacja nie istnieje. Mniej formalnie chcemy zmienić kolejność liczb od 1 do

n

$n$ ; każdy potrójne

(i, j, k)

$(i,j,k)$ w

S

$S$ wskazuje, że

i

$i$ musi pojawić się przed

k

$k$ w nowej kolejności, ale nie może występować między a .

j

$j$

i

$i$

k

$k$

Przykład 1

Załóżmy, że i . Następnie $n=5$ $S = \{(1,2,3), (2,3,4)\}$

jestnieważne permutacji, ponieważ , ale . $\pi = (5, 4, 3, 2, 1)$ $(1, 2, 3)\in S$ $\pi(1) > \pi(3)$
jestnieważne permutacji, ponieważ ale . $\pi = (1, 2, 4, 5, 3)$ $(1, 2, 3) \in S$ $\pi(1) < \pi(3) < \pi(5)$
jest prawidłową permutacją. $(2, 4, 1, 3, 5)$

Przykład 2

Jeśli i , nie ma prawidłowej permutacji. Podobnie nie ma ważnej permutacji, jeśli i $n=5$ $S = \{(1, 2, 3), (2, 1, 3)\}$ $n=5$ (myślę, że popełniłem tutaj błąd). $S = \{(1,2,3), (3,4,5), (2,5,3), (2,1,4)\}$

Premia: Jakie właściwości określają, czy istnieje możliwe rozwiązanie? $S$

algorithms optimization scheduling Patrick87
źródło

Dlaczego nie przeformułować drugiego warunku jako

? Masz wtedy prosty, mniej lub bardziej, problem satysfakcji z ograniczeń. (Zwróć uwagę, że uprościłem ten warunek w oparciu o inne założenia).

(σ_{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: Jaka jest motywacja tego problemu?

Dave Clarke

@DaveClarke Zobacz moją edycję. Problem ten został wyodrębniony z dyskusji wokół problemu planowania, o którym rozmawiałem z kilkoma innymi studentami w laboratorium. Zasadniczo chodzi o to, że masz wiele zadań, z których niektóre muszą być wykonywane w określonej kolejności. Jednak nie chcesz, aby niektóre zadania były planowane między zadaniami w sekwencji, być może z bardzo subtelnych powodów.

Patrick87

Dlaczego sigma? Wystarczy zdefiniować

. Zagnieżdżone indeksy dolne powodują, że mały Jezus płacze.

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

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

JeffE

@JeffE Szczerze mówiąc, po prostu lubię wymówkę, żeby grać z równaniem. Jest coś po prostu bardzo satysfakcjonującego w pisaniu kodu, który kompiluje się do tych małych

. Nie bierz tego ode mnie, stary.

σ

$\sigma$

Patrick87

Odpowiedzi:

Oto naiwny algorytm. Ostatecznie opiera się na brutalnej sile, ale czasami może działać dobrze.

Każde ograniczenie składa się z dwóch spójników; nazwijmy je typ- , oraz typ- , . Każdeograniczenietypu można zapisać w równoważny sposób jako rozłączenie , opierając się na fakcie, że . $(\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$

Zbierz wszystkie ograniczenia typu Nazwij to . Sprawdź, czy są one spójne, a mianowicie czy jest to linearyzacja uporządkowania. Wymaga to czasu w liczbie ograniczeń przy użyciu sortowania topologicznego. $A$ $\Theta$ $O(|S|)$
Dla każdego z rozłączników w wiązaniu typu sprawdź, czy jest on zgodny z częściowym porządkiem . Jeśli nie jest spójny, usuń środek rozdzielający. Jeśli oba rozłączenia są niezgodne z , to zawodzą. Ilekroć usuwane jest tylko jedno wiązanie typu , dodaj pozostałe do . Ten krok to . $B$ $\Theta$ $\Theta$ $B$ $\Theta$ $O(|S|^2)$
Teraz istnieje oczywisty algorytm znajdowania rozwiązania, a mianowicie wzięcie pod uwagę wszystkich kombinacji par rozłącznych typu i przetestowanie ich zgodności z , ale jest to wyraźnie wykładnicze w . Jedną heurystyczną poprawą wydajności byłoby traktowanie par rozłącznych typu jako gałęzi drzewa --- jedna para tworzy korzeń, jego dzieci są przekazywane przez drugą parę, ich dzieci przez trzecią i tak dalej. Korzystając z tej struktury danych, można znaleźć rozwiązanie, przechodząc przez drzewo w pierwszej kolejności. Za każdym razem, gdy dodawane jest nowe ograniczenie (przy użyciu etykiety na gałęzi), można sprawdzić spójność. Niespójne poddrzewa mogą być przycinane. $B$ $\Theta$ $|S|$
$B$
Po osiągnięciu liścia drzewa mamy spójny zestaw ograniczeń składający się ze wszystkich wiązań typu i jednego rozłącznika wiązań typu Zlinearyzuj wynik, aby uzyskać pożądane uporządkowanie. $A$ $B$

Moim preferowanym podejściem byłoby zakodowanie go w zestawie ograniczeń i użycie solvera ograniczenia, takiego jak Choco. Wprowadziłbym zmiennych całkowitych w zakresie i wymagam, aby wszystkie były odrębne. Następnie kodowałbym każde z powyższych ograniczeń bezpośrednio jako ograniczenia, a następnie pozwalałem Choco robić to samo. $n$ $x_i$ $[0,n-1]$

Dave Clarke
źródło

Oto częściowa odpowiedź:

Jeśli usunąć ograniczenia na siebie potrójne wtedy problem staje się problemem dla Betweeness który jest -Complete i tam nie są znane efektywne algorytmy dla takich problemów. Ale z ograniczeniem może wymusić jakąś ładną strukturę, którą można wykorzystać do znalezienia algorytmu czasu wielomianowego dla twojego problemu. $i \lt k$ $NP$ $i \lt k$

Mohammad Al-Turkistany
źródło