Problem zadowolenia z ograniczeń - Constraint satisfaction problem

Nie mylić z Komunikowaniem procesów sekwencyjnych .

Problemy spełniania ograniczeń ( CSP ) to pytania matematyczne definiowane jako zbiór obiektów, których stan musi spełniać szereg ograniczeń lub ograniczeń . CSP reprezentują jednostki w problemie jako jednorodny zbiór skończonych ograniczeń nad zmiennymi , który jest rozwiązywany za pomocą metod spełniania ograniczeń . CSP są przedmiotem badań zarówno w zakresie sztucznej inteligencji, jak i badań operacyjnych , ponieważ prawidłowość ich formułowania stanowi wspólną podstawę do analizy i rozwiązywania problemów wielu pozornie niespokrewnionych rodzin. CSP często cechuje duża złożoność , wymagająca połączenia heurystyk i kombinatorycznych metod wyszukiwania w rozsądnym czasie. Programowanie z ograniczeniami (CP) to dziedzina badań, która w szczególności koncentruje się na rozwiązywaniu tego rodzaju problemów. Dodatkowo, problem spełnialności Boole'a (SAT), teorie modulo spełnialności (SMT), programowanie mieszane całkowitoliczbowe (MIP) i programowanie zbioru odpowiedzi (ASP) to pola badawcze skupiające się na rozwiązywaniu poszczególnych postaci problemu spełniania ograniczeń.

Przykłady problemów, które mogą być modelowane jako problem spełniania ograniczeń, obejmują:

Są one często dostarczane z samouczkami solwerów CP , ASP, Boolean SAT i SMT. W ogólnym przypadku problemy z ograniczeniami mogą być znacznie trudniejsze i mogą nie być wyrażalne w niektórych z tych prostszych systemów. Przykłady „z życia wzięte” obejmują zautomatyzowane planowanie , ujednoznacznienie leksykalne , muzykologię , konfigurację produktu i alokację zasobów .

Istnienie rozwiązania CSP może być postrzegane jako problem decyzyjny . Można o tym zdecydować, znajdując rozwiązanie lub nie znajdując rozwiązania po wyczerpującym wyszukiwaniu (algorytmy stochastyczne zazwyczaj nigdy nie dochodzą do wyczerpujących wniosków, podczas gdy wyszukiwanie ukierunkowane często to robi, w przypadku wystarczająco małych problemów). W niektórych przypadkach CSP może być znany z tego, że wcześniej ma rozwiązania, poprzez inny proces wnioskowania matematycznego.

Formalna definicja

Formalnie problem spełnienia ograniczeń definiuje się jako trójkę , gdzie

  • to zbiór zmiennych,
  • jest zbiorem ich odpowiednich domen wartości, oraz
  • to zestaw ograniczeń.

Każda zmienna może przyjmować wartości z niepustej domeny . Każde ograniczenie jest z kolei parą , gdzie jest podzbiorem zmiennych i jest relacją -arną na odpowiednim podzbiorze dziedzin . Oceny zmiennych jest funkcją z podzbioru zmiennych dla danego zbioru wartości w odpowiadającej podgrupie domen. Ocena spełnia ograniczenie, jeśli wartości przypisane do zmiennych spełniają relację .

Ocena jest spójna, jeśli nie narusza żadnego z ograniczeń. Ocena jest kompletna, jeśli zawiera wszystkie zmienne. Ewaluacja jest rozwiązaniem, jeśli jest spójna i kompletna; mówi się, że taka ocena rozwiązuje problem spełnienia ograniczeń.

Rozwiązanie

Problemy z satysfakcją z ograniczeń w domenach skończonych są zazwyczaj rozwiązywane przy użyciu formy wyszukiwania . Najczęściej stosowanymi technikami są warianty cofania , propagacji ograniczeń i wyszukiwania lokalnego . Techniki te są również często łączone, jak w metodzie VLNS , a obecne badania obejmują inne technologie, takie jak programowanie liniowe .

Cofanie się to algorytm rekurencyjny. Zachowuje częściowe przypisanie zmiennych. Początkowo wszystkie zmienne są nieprzypisane. Na każdym kroku wybierana jest zmienna, której kolejno przypisywane są wszystkie możliwe wartości. Dla każdej wartości sprawdzana jest zgodność przypisania częściowego z ograniczeniami; w przypadku spójności wykonywane jest wywołanie rekurencyjne . Po wypróbowaniu wszystkich wartości algorytm cofa się. W tym podstawowym algorytmie cofania spójność definiuje się jako spełnienie wszystkich ograniczeń, których wszystkie zmienne są przypisane. Istnieje kilka wariantów cofania się. Backmarking poprawia efektywność sprawdzania spójności. Backjumping umożliwia w niektórych przypadkach zapisanie części wyszukiwania przez cofnięcie "więcej niż jednej zmiennej". Uczenie się ograniczeń wyprowadza i zapisuje nowe ograniczenia, które można później wykorzystać, aby uniknąć części wyszukiwania. Look-ahead jest również często używany w śledzeniu wstecznym, aby spróbować przewidzieć skutki wyboru zmiennej lub wartości, a tym samym czasami określić z góry, kiedy podproblem jest satysfakcjonujący, a kiedy nie.

Techniki propagacji ograniczeń są metodami używanymi do modyfikowania problemu spełniania ograniczeń. Dokładniej, są to metody wymuszające pewną formę spójności lokalnej , czyli warunki związane ze spójnością grupy zmiennych i/lub ograniczeń. Propagacja ograniczeń ma różne zastosowania. Po pierwsze, zamienia problem w taki, który jest równoważny, ale zwykle łatwiejszy do rozwiązania. Po drugie, może świadczyć o spełnianiu lub niezaspokojeniu problemów. Generalnie nie ma gwarancji, że tak się stanie; jednak zawsze dzieje się tak w przypadku niektórych form propagacji ograniczeń i/lub niektórych rodzajów problemów. Najbardziej znane i stosowane formy lokalnej spójności są łuk konsystencji , konsystencji hiper-łukowego i konsystencji ścieżki . Najpopularniejszą metodą propagacji ograniczeń jest algorytm AC-3 , który wymusza spójność łuku.

Lokalne metody wyszukiwania są niekompletnymi algorytmami spełnialności. Mogą znaleźć rozwiązanie problemu, ale mogą ponieść porażkę, nawet jeśli problem jest satysfakcjonujący. Pracują przez iteracyjne ulepszanie pełnego przypisania zmiennych. Na każdym kroku niewielka liczba zmiennych jest zmieniana pod względem wartości, mając na celu zwiększenie liczby ograniczeń spełnianych przez to przypisanie. Algorytm min-konflikty to lokalny algorytm wyszukiwania specyficzne dla CSP i jest oparty na tej zasadzie. W praktyce wyszukiwanie lokalne wydaje się działać dobrze, gdy na te zmiany mają również wpływ losowe wybory. Opracowano integrację wyszukiwania z wyszukiwaniem lokalnym, prowadząc do algorytmów hybrydowych .

Aspekty teoretyczne

Problemy decyzyjne

CSP są również badane w teorii złożoności obliczeniowej i teorii modeli skończonych . Ważnym pytaniem jest, czy dla każdego zbioru relacji zbiór wszystkich CSP, które mogą być reprezentowane przy użyciu tylko relacji wybranych z tego zbioru, ma charakter P lub NP-zupełny . Jeśli takie twierdzenie o dychotomii jest prawdziwe, to CSP zapewniają jeden z największych znanych podzbiorów NP, który pozwala uniknąć problemów NP-pośrednich , których istnienie zostało wykazane przez twierdzenie Ladnera przy założeniu, że P ≠ NP . Twierdzenie o dychotomii Schaefera obsługuje przypadek, gdy wszystkie dostępne relacje są operatorami boolowskimi , to znaczy dla rozmiaru domeny 2. Twierdzenie o dychotomii Schaefera zostało niedawno uogólnione na większą klasę relacji.

Większość klas CSP, o których wiadomo, że są wykonalne, to te, w których hipergraf ograniczeń ma ograniczoną szerokość drzewa (i nie ma ograniczeń dotyczących zbioru relacji ograniczeń) lub w których ograniczenia mają dowolną formę, ale istnieją zasadniczo niejednoargumentowe polimorfizmy zbiór relacji więzów.

Każdy dostawca CSP może być również traktowany jako problem zawierania zapytań połączonych .

Problemy funkcjonalne

Podobna sytuacja występuje między klasami funkcjonalnymi FP i #P . Uogólniając twierdzenie Ladnera , nie ma również problemów ani w FP, ani w #P-zupełny, o ile FP ≠ #P. Podobnie jak w przypadku decyzyjnym, problem w #CSP jest definiowany przez zbiór relacji. Każdy problem przyjmuje jako dane wejściowe formułę Boole'a, a zadaniem jest obliczenie liczby satysfakcjonujących zadań. Można to dalej uogólnić, stosując większe rozmiary domen i przypisując wagę do każdego satysfakcjonującego przypisania i obliczając sumę tych wag. Wiadomo, że każdy złożony, ważony problem #CSP dotyczy albo FP, albo #P-trudnego.

Warianty

Klasyczny model Constraint Satisfaction Problem definiuje model statycznych, nieelastycznych więzów. Ten sztywny model jest wadą, która utrudnia łatwe przedstawianie problemów. Zaproponowano kilka modyfikacji podstawowej definicji CSP w celu dostosowania modelu do szerokiej gamy problemów.

Dynamiczni dostawcy CSP

Dynamiczne CSP ( DCSP ) są przydatne, gdy oryginalne sformułowanie problemu zostało w jakiś sposób zmienione, zazwyczaj dlatego, że zestaw ograniczeń do rozważenia ewoluuje z powodu środowiska. DCSP są postrzegane jako sekwencja statycznych CSP, z których każdy jest transformacją poprzedniego, w którym zmienne i ograniczenia mogą być dodawane (ograniczenie) lub usuwane (relaksacja). Informacje znalezione w początkowych sformułowaniach problemu mogą posłużyć do doprecyzowania kolejnych. Metodę rozwiązywania można sklasyfikować według sposobu, w jaki informacje są przekazywane:

  • Wyrocznie: rozwiązanie znalezione dla poprzednich dostawców CSP w sekwencji jest używane jako heurystyka do prowadzenia od zera rozwiązania obecnego dostawcy CSP.
  • Naprawa lokalna: każdy CSP jest obliczany od częściowego rozwiązania poprzedniego i naprawiania niespójnych ograniczeń za pomocą wyszukiwania lokalnego .
  • Rejestrowanie ograniczeń: nowe ograniczenia są definiowane na każdym etapie wyszukiwania, aby odzwierciedlić uczenie się niespójnej grupy decyzji. Ograniczenia te zostały przeniesione na nowe problemy CSP.

Elastyczni dostawcy CSP

Klasyczni dostawcy CSP traktują ograniczenia jako twarde, co oznacza, że ​​są imperatywne (każde rozwiązanie musi je wszystkie spełniać) i nieelastyczne (w tym sensie, że muszą być całkowicie spełnione, w przeciwnym razie są całkowicie naruszone). Elastyczne CSP rozluźniają te założenia, częściowo rozluźniając ograniczenia i pozwalając, aby rozwiązanie nie spełniało wszystkich z nich. Jest to podobne do preferencji w planowaniu opartym na preferencjach . Niektóre rodzaje elastycznych dostawców CSP obejmują:

  • MAX-CSP, w którym dopuszcza się naruszenie pewnej liczby ograniczeń, a jakość rozwiązania mierzy się liczbą spełnionych ograniczeń.
  • Weighted CSP , MAX-CSP, w którym każde naruszenie ograniczenia jest ważone zgodnie ze wstępnie zdefiniowaną preferencją. Dlatego preferowane jest zaspokojenie ograniczenia większą wagą.
  • Ograniczenia modelu rozmytego CSP jako relacje rozmyte, w których spełnienie ograniczenia jest ciągłą funkcją wartości jego zmiennych, przechodząc od w pełni spełnionego do w pełni naruszonego.

Zdecentralizowani dostawcy CSP

W DCSP każda zmienna ograniczająca jest traktowana jako posiadająca oddzielną lokalizację geograficzną. Na wymianę informacji między zmiennymi nakładane są silne ograniczenia, wymagające użycia algorytmów w pełni rozproszonych do rozwiązania problemu spełnienia ograniczeń.

Zobacz też

Bibliografia

Dalsza lektura