Ograniczona satysfakcja - Constraint satisfaction

W sztucznej inteligencji i badań operacyjnych , ograniczenie satysfakcja jest proces znalezienia rozwiązania zestawu ograniczeń , które nakładają warunki, które zmienne muszą spełniać . Rozwiązaniem jest zatem zbiór wartości dla zmiennych, który spełnia wszystkie ograniczenia — czyli punkt w obszarze wykonalnym .

Techniki stosowane w spełnianiu ograniczeń zależą od rodzaju rozważanych ograniczeń. Często używane są ograniczenia na skończonej dziedzinie , do tego stopnia, że problemy spełnienia ograniczeń są zwykle identyfikowane z problemami opartymi na ograniczeniach na skończonej dziedzinie. Takie problemy są zwykle rozwiązywane za pomocą wyszukiwania , w szczególności w formie wycofywania się lub wyszukiwania lokalnego . Propagacja ograniczeń to inne metody stosowane w takich problemach; większość z nich jest generalnie niekompletna, to znaczy mogą rozwiązać problem lub udowodnić, że jest on niezadowalający, ale nie zawsze. Metody propagacji ograniczeń są również używane w połączeniu z wyszukiwaniem, aby uprościć rozwiązanie danego problemu. Inne rozważane rodzaje ograniczeń dotyczą liczb rzeczywistych lub wymiernych; rozwiązywanie problemów na tych ograniczeniach odbywa się poprzez eliminację zmiennych lub algorytm simpleks .

Satysfakcja z ograniczeń powstała w dziedzinie sztucznej inteligencji w latach 70. (patrz na przykład ( Laurière 1978 )). W latach 80. i 90. opracowano osadzanie ograniczeń w języku programowania . Języki często używane do programowania z ograniczeniami to Prolog i C++ .

Problem zadowolenia z ograniczeń

Jak pierwotnie zdefiniowano w sztucznej inteligencji, ograniczenia wyliczają możliwe wartości, jakie zbiór zmiennych może przyjąć w danym świecie. Świat możliwy to całkowite przypisanie wartości do zmiennych reprezentujących sposób, w jaki mógłby wyglądać świat (rzeczywisty lub urojony). Nieformalnie domena skończona to skończony zbiór dowolnych elementów. Problem spełnienia ograniczeń w takiej domenie zawiera zbiór zmiennych, których wartości można pobrać tylko z tej dziedziny, oraz zbiór ograniczeń, przy czym każde ograniczenie określa dozwolone wartości dla grupy zmiennych. Rozwiązaniem tego problemu jest ocena zmiennych, która spełnia wszystkie ograniczenia. Innymi słowy, rozwiązanie to sposób na przypisanie wartości do każdej zmiennej w taki sposób, aby wszystkie ograniczenia były spełnione przez te wartości.

W pewnych okolicznościach mogą istnieć dodatkowe wymagania: można być zainteresowanym nie tylko rozwiązaniem (i najszybszym lub najbardziej wydajnym obliczeniowo sposobem dotarcia do niego), ale także sposobem, w jaki zostało osiągnięte; np. można chcieć „najprostszego” rozwiązania („najprostszego” w logicznym, nieobliczeniowym sensie, który musi być precyzyjnie zdefiniowany). Dzieje się tak często w grach logicznych, takich jak Sudoku.

W praktyce ograniczenia są często wyrażane w zwięzłej formie, zamiast wyliczania wszystkich wartości zmiennych, które spełniają ograniczenia. Jednym z najczęściej używanych ograniczeń jest (oczywiste) ustalenie, że wartości zmiennych, których to dotyczy, muszą być różne.

Problemy, które mogą być wyrażone jako ograniczającego problemów satysfakcji są puzzle osiem królowych The Sudoku rozwiązywania problemów i wiele innych zagadek logicznych The problem spełnialności , harmonogramów problemy, estymacji ograniczonego-błędach problemy i różne problemy na wykresach takich jak kolorowanie grafów problemu.

Chociaż zwykle nie są uwzględnione w powyższej definicji problemu spełnienia ograniczeń, równania arytmetyczne i nierówności wiążą wartości zawartych w nich zmiennych i dlatego można je uznać za formę ograniczeń. Ich domeną jest zbiór liczb (całkowitych, wymiernych lub rzeczywistych), który jest nieskończony: zatem relacje tych ograniczeń mogą być również nieskończone; na przykład ma nieskończoną liczbę par satysfakcjonujących wartości. Równania arytmetyczne i nierówności często nie są uwzględniane w definicji „problemu spełnienia ograniczeń”, który ogranicza się do skończonych dziedzin. Są jednak często używane w programowaniu z ograniczeniami . ${\ Displaystyle X = Y + 1}$

Można wykazać, że nierówności arytmetyczne lub równania występujące w niektórych typach łamigłówek logicznych skończonych, takich jak Futoshiki lub Kakuro (znanych również jako sumy krzyżowe), można traktować jako ograniczenia niearytmetyczne (patrz : Satysfakcja z ograniczeń opartych na wzorcach i zagadki logiczne ) .

Rozwiązywanie

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ą używane w problemach z ograniczeniami nieliniowymi .

Eliminacja zmiennych oraz algorytm simpleks służą do rozwiązywania równań i nierówności liniowych i wielomianowych oraz problemów zawierających zmienne o dziedzinie nieskończonej. Są one zazwyczaj rozwiązywane jako problemy optymalizacyjne , w których zoptymalizowaną funkcją jest liczba naruszonych ograniczeń.

Złożoność

Rozwiązanie problemu spełniania ograniczeń na skończonej dziedzinie jest problemem NP zupełnym ze względu na rozmiar dziedziny. Badania wykazały szereg uległy subcases niektóre ograniczenia dozwolony stosunki ograniczeń, niektórzy z nich wymagają zakresy ograniczeń, postać drzewa, ewentualnie w o zmienionej wersji tego problemu. Badania wykazały również związek problemu spełniania ograniczeń z problemami w innych dziedzinach, takich jak teoria modeli skończonych .

Programowanie ograniczeń

Programowanie z ograniczeniami to wykorzystanie ograniczeń jako języka programowania do kodowania i rozwiązywania problemów. Odbywa się to często poprzez osadzenie ograniczeń w języku programowania , zwanym językiem hosta. Programowanie z ograniczeniami wywodzi się z sformalizowania równości terminów w Prologu II , prowadząc do ogólnych ram do osadzania ograniczeń w języku programowania logicznego . Najpopularniejszymi językami hostów są Prolog , C++ i Java , ale używane są również inne języki.

Programowanie logiki ograniczeń

Program logiki ograniczeń to program logiczny, który zawiera ograniczenia w treści klauzul. Na przykład klauzula A(X):-X>0,B(X)jest klauzulą zawierającą ograniczenie X>0w treści. Ograniczenia mogą być również obecne w celu. Ograniczenia w celu iw klauzulach używanych do udowodnienia celu są gromadzone w zbiorze zwanym magazynem ograniczeń . Ten zestaw zawiera ograniczenia, które tłumacz uznał za spełnione, aby kontynuować ocenę. W rezultacie, jeśli ten zestaw zostanie wykryty jako niezadowalający, tłumacz wycofuje się. Równania terminów używane w programowaniu logicznym są uważane za szczególną formę ograniczeń, które można uprościć za pomocą unifikacji . W rezultacie magazyn ograniczeń można uznać za rozszerzenie koncepcji podstawienia, która jest używana w zwykłym programowaniu logicznym. Najczęstszymi rodzajami ograniczeń używanych w programowaniu w logice z ograniczeniami są ograniczenia dotyczące liczb całkowitych/wymiernych/rzeczywistych oraz ograniczenia dotyczące dziedzin skończonych.

Opracowano również współbieżne języki programowania z logiką ograniczeń . Różnią się one znacząco od niewspółbieżnego programowania w logice ograniczeń tym, że mają na celu programowanie procesów współbieżnych, które nie mogą się zakończyć. Reguły obsługi ograniczeń mogą być postrzegane jako forma współbieżnego programowania logiki ograniczeń, ale czasami są również używane w niewspółbieżnym języku programowania logiki ograniczeń. Pozwalają na przepisanie ograniczeń lub wywnioskowanie nowych na podstawie prawdziwości warunków.

Zestawy narzędzi do ograniczania satysfakcji

Zestawy narzędzi do spełniania ograniczeń to biblioteki oprogramowania dla imperatywnych języków programowania, które są używane do kodowania i rozwiązywania problemu spełniania ograniczeń.

Rozwiązywanie ograniczeń Cassowary , projekt open source do spełniania ograniczeń (dostępny z C, Java, Python i innych języków).
Comet , komercyjny język programowania i zestaw narzędzi
Gecode , przenośny zestaw narzędzi open source napisany w języku C++, opracowany jako produkcyjne i wysoce wydajne wdrożenie pełnego zaplecza teoretycznego.
Gelisp , przenośne opakowanie typu open source Gecode to Lisp . http://gelisp.sourceforge.net/
IBM ILOG CP Optimizer : biblioteki C++, Python , Java, .NET (zastrzeżone, bezpłatne do użytku akademickiego ). Następca firmy ILOG Solver/Scheduler, która od 2006 roku została uznana za lidera rynku komercyjnego oprogramowania do programowania z ograniczeniami
JaCoP , narzędzie do rozwiązywania ograniczeń Java typu open source.
OptaPlanner , kolejny program do rozwiązywania ograniczeń Java typu open source.
Koalog , komercyjne narzędzie do rozwiązywania ograniczeń oparte na Javie.
logilab-constraint , narzędzie do rozwiązywania ograniczeń typu open source napisane w czystym Pythonie z algorytmami propagacji ograniczeń.
Minion , open-source solver napisany w C++, z małym językiem do określania modeli/problemów.
ZDC, program open source opracowany w ramach Computer-Aided Constraint Satisfaction Project do modelowania i rozwiązywania problemów spełniania ograniczeń.

Inne języki programowania z ograniczeniami

Zestawy narzędzi do ograniczania są sposobem na osadzenie ograniczeń w imperatywnym języku programowania . Jednak są one używane tylko jako biblioteki zewnętrzne do kodowania i rozwiązywania problemów. Podejście, w którym ograniczenia są zintegrowane z imperatywnym językiem programowania, jest stosowane w języku programowania Kaleidoscope .

Ograniczenia zostały również wbudowane w funkcjonalne języki programowania .

Zobacz też

Bibliografia

Apt, Krzysztof (2003). Zasady programowania z ograniczeniami . Wydawnictwo Uniwersytetu Cambridge. Numer ISBN 978-0-521-82583-2.
Dechtera, Riny (2003). Przetwarzanie ograniczeń . Morgana Kaufmanna. Numer ISBN 978-1-55860-890-0.
Dincbas, M.; Simonis, H.; Van Hentenryck, P. (1990). „Rozwiązywanie dużych problemów kombinatorycznych w programowaniu logicznym” . Dziennik programowania logicznego . 8 (1–2): 75–93. doi : 10.1016/0743-1066(90)90052-7 .
Freudera, Eugeniusza; Mackworth, Alan, wyd. (1994). Rozumowanie oparte na ograniczeniach . MIT Naciśnij. Numer ISBN 978-0-262-56075-7.
Frühwirth, Thom; Slim Abdennadher (2003). Podstawy programowania z ograniczeniami . Skoczek. Numer ISBN 978-3-540-67623-2.
Guesguen, Hans; Hertzberg Joachim (1992). Perspektywa rozumowania opartego na ograniczeniach . Skoczek. Numer ISBN 978-3-540-55510-0.
Jaffar, Joxan; Michael J. Maher (1994). "Programowanie w logice z ograniczeniami: ankieta" . Dziennik programowania logicznego . 19/20: 503–581. doi : 10.1016/0743-1066(94)90033-7 .
Laurière, Jean-Louis (1978). „Język i program do określania i rozwiązywania problemów kombinatorycznych”. Sztuczna inteligencja . 10 (1): 29–127. doi : 10.1016/0004-3702(78)90029-2 .
Lecoutre, Christophe (2009). Sieci z ograniczeniami: techniki i algorytmy . ISTE/Wiley. Numer ISBN 978-1-84821-106-3.
Marriott, Kim; Peter J. Stuckey (1998). Programowanie z ograniczeniami: Wprowadzenie . MIT Naciśnij. Numer ISBN 978-0-262-13341-8.
Rossi, Francesca; Petera van Beeka; Toby Walsh, wyd. (2006). Podręcznik programowania z ograniczeniami . Elsevier. Numer ISBN 978-0-444-52726-4. Zarchiwizowane od oryginału 04.10.2012 . Źródło 2006-10-13 .
Tsang, Edward (1993). Podstawy zadowolenia z ograniczeń . Prasa akademicka. Numer ISBN 978-0-12-701610-8.
Van Hentenryck, Pascal (1989). Satysfakcja z ograniczeń w programowaniu logicznym . MIT Naciśnij. Numer ISBN 978-0-262-08181-8.
Rashidi, Hassan; Tsang, Edwardzie. (2012). "Nowe modele spełniania ograniczeń dla problemów optymalizacyjnych w terminalach kontenerowych" . Journal of Applied Mathematical Modeling . 37 (6): 3601-34. doi : 10.1016/j.apm.2012.07.042 .

Linki zewnętrzne

Samouczek CSP

Languages

In other projects