Algorytm zamienności

W informatyce algorytm zamienności jest techniką stosowaną do bardziej efektywnego rozwiązywania problemów spełniania ograniczeń (CSP). CSP to problem matematyczny, w którym obiekty reprezentowane przez zmienne podlegają ograniczeniom dotyczącym wartości tych zmiennych; celem w CSP jest przypisanie wartości do zmiennych, które są zgodne z ograniczeniami. Jeśli dwie zmienne A i B w CSP mogą być zamienione na siebie (to znaczy, A jest zastępowane przez B i B jest zastępowane przez A ) bez zmiany charakteru problemu lub jego rozwiązań, wówczas A i B są wymiennymi zmiennymi. Wymienne zmienne reprezentują symetrię CSP i wykorzystując tę ​​symetrię, przestrzeń poszukiwań rozwiązań problemu CSP. Na przykład, jeśli wypróbowano rozwiązania z A = 1 i B = 2, to przy symetrii wymiany rozwiązania z B = 1 i A = 2 nie muszą być badane.

Pojęcie wymienności i algorytm wymienności w problemach spełniania ograniczeń zostały po raz pierwszy wprowadzone przez Eugene'a Freudera w 1991 r. Algorytm wymienności zmniejsza przestrzeń wyszukiwania algorytmów wyszukiwania wstecznego , poprawiając w ten sposób wydajność problemów NP-zupełnych CSP.

Definicje

W pełni zamienna

Wartość a dla zmiennej v jest w pełni zamienna z wartością b wtedy i tylko wtedy, gdy każde rozwiązanie, w którym v = a pozostaje rozwiązaniem, gdy b jest zastąpione a i odwrotnie.

Sąsiedztwo wymienne

Wartość a dla zmiennej v jest sąsiedztwem wymiennym z wartością b wtedy i tylko wtedy, gdy dla każdego ograniczenia na v wartości zgodne z v = a są dokładnie zgodne z v = b.

W pełni zastępowalna

Wartość a dla zmiennej v jest w pełni podstawialne wartością b wtedy i tylko wtedy, gdy każde rozwiązanie, w którym v = a pozostaje rozwiązaniem, gdy b jest podstawione za a (ale niekoniecznie odwrotnie).

Dynamicznie wymienna

Wartość a dla zmiennej v jest dynamicznie wymienna dla b w odniesieniu do zbioru A przypisań zmiennych wtedy i tylko wtedy, gdy są one w pełni wymienne w podproblemie wywołanym przez A.

Pseudo kod

Algorytm zamienności sąsiedztwa

Znajduje wymienne wartości sąsiedztwa w CSP. Powtórz dla każdej zmiennej:

Zbuduj drzewo dyskryminacji poprzez:

Powtórz dla każdej wartości, v:

Powtórz dla każdej sąsiedniej zmiennej W:

Powtórz dla każdej wartości w zgodnej z v:

Przejdź do, jeśli istnieje, skonstruuj, jeśli nie, węzeł drzewa dyskryminacji odpowiadający w|W

K -algorytm zamienności

Algorytmu można użyć do jawnego znalezienia rozwiązań problemu spełnienia ograniczeń. Algorytm można również uruchomić dla k kroków jako preprocesor, aby uprościć późniejsze wyszukiwanie wsteczne.

Znajduje k-wymienne wartości w CSP. Powtórz dla każdej zmiennej:

Zbuduj drzewo dyskryminacji poprzez:

Powtórz dla każdej wartości, v:

Powtórz dla każdej ( k − 1)-krotki zmiennych

Powtórz dla każdej ( k − 1)-krotki wartości w , które razem z v stanowią rozwiązanie podproblemu indukowanego przez W :

Przejdź do, jeśli jest obecny, skonstruuj, jeśli nie, węzeł drzewa dyskryminacji odpowiadający w|W

Analiza złożoności

W przypadku algorytmu wymiennego sąsiedztwa, jeśli do każdej pętli przypiszemy najgorszy przypadek. Następnie dla n zmiennych, które mają co najwyżej d wartości dla zmiennej, mamy granicę: ${\ Displaystyle O (nd (nl )*d)=O(n^{2}d^{2})}$ .

Podobnie, analiza złożoności algorytmu $)} -$ -zamienności ${\ Displaystyle (k-1 ) {\ Displaystyle O (n ^ {$ najgorszego przypadku , z $)$ krotki zmiennych i $)$ dla $\ Displaystyle (k-1)}$ -krotki wartości, to ${\ Displaystyle O (ndn ^ {kl} d ^ {k-1}) = O (n ^ {k} d ^ {k} )}$ .

Przykład

Przykład algorytmu zamienności.

Rysunek przedstawia prosty przykład kolorowania grafu z kolorami jako wierzchołkami, tak że żadne dwa wierzchołki połączone krawędzią nie mają tego samego koloru. Pokazane są dostępne kolory w każdym wierzchołku. Kolory żółty, zielony, brązowy, czerwony, niebieski, różowy reprezentują wierzchołek Y iz definicji są w pełni wymienne. Na przykład, podstawiając bordowy za zielony w roztworze orange|X (pomarańczowy zamiast X), zielony|Y da inne rozwiązanie.

Aplikacje

W informatyce algorytm wymienności był szeroko stosowany w dziedzinie sztucznej inteligencji , problemów z kolorowaniem grafów , ram abstrakcji i adaptacji rozwiązań.