Miesiąc: październik 2021

Centralnym składnikiem agenta opartego na wiedzy jest jego baza wiedzy (KB). Baza wiedzy to zbiór zdań. (Tutaj „zdanie” jest używane jako termin techniczny. Jest ono powiązane, ale nie identyczne ze zdaniami w języku angielskim i innych językach naturalnych.) Każde zdanie jest wyrażone w języku zwanym językiem reprezentacji wiedzy i reprezentuje pewne twierdzenie o świecie. Gdy zdanie przyjmuje się jako dane bez wyprowadzania z innych zdań, nazywamy je aksjomatem. Musi istnieć sposób na dodawanie nowych zdań do bazy wiedzy oraz sposób na zapytanie o to, co jest znane. Standardowe nazwy tych operacji to odpowiednio TELL i ASK. Obie operacje mogą obejmować wnioskowanie, czyli wyprowadzanie nowych zdań ze starych. Wnioskowanie musi być zgodne z wymogiem, że kiedy zadaje się pytanie dotyczące bazy wiedzy, odpowiedź powinna wynikać z tego, co zostało powiedziane (lub PRZEKAZANE) wcześniej bazie wiedzy. W dalszej części tego rozdziału dokładniej omówimy kluczowe słowo „podążać”. Na razie potraktuj to tak, że proces wnioskowania nie powinien zmyślać rzeczy w miarę postępu. Rysunek przedstawia zarys programu agenta opartego na wiedzy. Jak wszyscy nasi agenci, przyjmuje percept jako dane wejściowe i zwraca akcję. Agent utrzymuje bazę wiedzy KB, która początkowo może zawierać pewną wiedzę podstawową.

Za każdym razem, gdy program agenta jest wywoływany, robi trzy rzeczy. Po pierwsze, MÓWI bazie wiedzy, co postrzega. Po drugie, PYTA bazę wiedzy, jakie działania powinna wykonać. W procesie odpowiadania na to pytanie można przeprowadzić obszerne rozumowanie na temat aktualnego stanu świata, wyników możliwych sekwencji działań i tak dalej. Po trzecie, program agenta MÓWI bazie wiedzy, która akcja została wybrana i zwraca akcję, aby można ją było wykonać. Szczegóły języka reprezentacji są ukryte w trzech funkcjach, które implementują interfejs między czujnikami i elementami wykonawczymi z jednej strony a podstawowym systemem reprezentacji i rozumowania z drugiej. MAKE-PERCEPT-SENTENCE konstruuje zdanie stwierdzające, że podmiot postrzegał dany percept w określonym czasie. MAKE-ACTION-QUERY konstruuje zdanie, które pyta, jakie działanie należy wykonać w danym momencie. Na koniec MAKE-ACTIONSENTENCE konstruuje zdanie stwierdzające, że wybrane działanie zostało wykonane. Szczegóły mechanizmów wnioskowania są ukryte wewnątrz TELL i ASK. Późniejsze sekcje ujawnią te szczegóły. Agent na rysunku 7.1 wygląda dość podobnie do agentów ze stanem wewnętrznym opisanych w rozdziale 2 . Jednak ze względu na definicje TELL i ASK agent oparty na wiedzy nie jest arbitralnym programem do obliczania działań. Można go opisać na poziomie wiedzy, gdzie wystarczy określić tylko to, co agent wie i jakie są jego cele, aby określić jego zachowanie. Na przykład zautomatyzowana taksówka może mieć na celu przewiezienie pasażera z San Francisco do hrabstwa Marin i może wiedzieć, że most Golden Gate jest jedynym połączeniem między tymi dwiema lokalizacjami. Wtedy możemy się spodziewać, że przekroczy most Golden Gate, ponieważ wie, że to osiągnie swój cel. Zauważ, że ta analiza jest niezależna od sposobu działania taksówki na poziomie wdrożenia. Nie ma znaczenia, czy jego wiedza geograficzna jest zaimplementowana jako połączone listy lub mapy pikseli, czy też rozumuje, manipulując ciągami symboli przechowywanymi w rejestrach, czy też propagując zaszumione sygnały w sieci neuronów. Agenta opartego na wiedzy można zbudować po prostu, przekazując mu to, co musi wiedzieć. Zaczynając od pustej bazy wiedzy, projektant agenta może MÓWIĆ zdania jeden po drugim, dopóki agent nie będzie wiedział, jak działać w swoim środowisku. Nazywa się to deklaratywnym podejściem do budowania systemu. Natomiast podejście proceduralne koduje pożądane zachowania bezpośrednio jako kod programu. W latach 70. i 80. zwolennicy obu podejść toczyli gorące debaty. Rozumiemy teraz, że skuteczny agent często łączy w swoim projekcie zarówno elementy deklaratywne, jak i proceduralne, a wiedzę deklaratywną można często skompilować w bardziej wydajny kod proceduralny. Możemy również dostarczyć agentowi opartemu na wiedzy mechanizmy, które pozwolą mu uczyć się samodzielnie. Agent uczący się może być w pełni autonomiczny.

Wydaje się, że ludzie wiedzą różne rzeczy; a to, co wiedzą, pomaga im robić różne rzeczy. W sztucznej inteligencji agenci bazujący na wiedzy wykorzystują proces rozumowania nad wewnętrzną reprezentacją wiedzy, aby zdecydować, jakie działania podjąć. Agenci rozwiązujący problemy z wiedzą wszystko, ale tylko w bardzo ograniczonym, nieelastycznym sensie. Wiedzą, jakie akcje są dostępne i jaki będzie wynik wykonania konkretnej akcji z określonego stanu, ale nie znają ogólnych faktów. Agent odnajdywania tras nie wie, że droga nie może mieć ujemnej liczby kilometrów. Agent składający się z 8 puzzli nie wie, że dwie płytki nie mogą zajmować tej samej przestrzeni. Wiedza, którą posiadają, jest bardzo przydatna do znalezienia drogi od początku do celu, ale nie do niczego innego. Reprezentacje atomowe używane przez agentów rozwiązujących problemy również są bardzo ograniczające. Na przykład w częściowo obserwowalnym środowisku jedynym wyborem agenta rozwiązującego problemy do reprezentowania tego, co wie o bieżącym stanie, jest wymienienie wszystkich możliwych konkretnych stanów. Mógłbym dać człowiekowi cel dojechania do amerykańskiego miasta o populacji poniżej 10 000, ale mówiąc to agentowi rozwiązującemu problemy, mógłbym formalnie opisać cel tylko jako wyraźny zbiór około 16 000 miast, które spełniają wymagania opis. Wcześniej wprowadzono naszą pierwszą reprezentację podzieloną na czynniki, w której stany są reprezentowane jako przypisania wartości do zmiennych; jest to krok we właściwym kierunku, umożliwiający niektórym częściom agenta pracę w sposób niezależny od domeny i pozwalający na bardziej wydajne algorytmy. Tu podejmujemy ten krok do logicznego zakończenia, że ​​tak powiem – rozwijamy logikę jako ogólną klasę reprezentacji wspierających agentów opartych na wiedzy. Te środki mogą łączyć i rekombinować informacje, aby dopasować je do niezliczonych celów. Może to być dalekie od potrzeb chwili – jak wtedy, gdy matematyk udowadnia twierdzenie lub astronom oblicza oczekiwaną długość życia na Ziemi. Agenci bazujący na wiedzy mogą akceptować nowe zadania w postaci wyraźnie opisanych celów; mogą szybko osiągnąć kompetencje dzięki informacjom lub uczeniu się nowej wiedzy o środowisku; i potrafią dostosowywać się do zmian w środowisku, aktualizując odpowiednią wiedzę. Logika zdań jest reprezentacją podzieloną na czynniki; chociaż mniej wyrazista niż logika pierwszego rzędu , która jest kanoniczną ustrukturyzowaną reprezentacją, logika zdań ilustruje wszystkie podstawowe pojęcia logiki. Zawiera również dobrze rozwinięte technologie wnioskowania.

* Problemy ze spełnieniem ograniczeń (CSP) reprezentują stan ze zbiorem par zmienna/wartość i reprezentują warunki rozwiązania przez zbiór ograniczeń na zmiennych. Wiele ważnych rzeczywistych problemów można opisać jako CSP.

* Szereg technik wnioskowania wykorzystuje ograniczenia, aby wykluczyć pewne przypisania zmiennych. Należą do nich węzeł, łuk, ścieżka i -spójność.

* Wyszukiwanie z wycofywaniem się, forma wyszukiwania w głąb, jest powszechnie używane do rozwiązywania CSP. Wnioskowanie można przeplatać z wyszukiwaniem.

* Minimalne pozostałe wartości i heurystyka stopni to niezależne od domeny metody decydowania, którą zmienną wybrać jako następną w wyszukiwaniu wstecznym. Heurystyka najmniej ograniczającej wartości pomaga w podjęciu decyzji, którą wartość należy wypróbować jako pierwszą dla danej zmiennej. Cofanie się występuje, gdy nie można znaleźć przypisania prawnego dla zmiennej. Skierowane na konflikt wsteczne tory cofają się bezpośrednio do źródła problemu. Uczenie się ograniczeń rejestruje konflikty napotykane podczas wyszukiwania w celu uniknięcia tego samego konfliktu w późniejszym wyszukiwaniu.

* Lokalne wyszukiwanie przy użyciu heurystyki mini-konfliktów zostało również z dużym sukcesem zastosowane do problemów spełniania ograniczeń.

* Złożoność rozwiązywania CSP jest silnie związana ze strukturą jego grafu ograniczeń. Problemy o strukturze drzewa można rozwiązywać w czasie liniowym. Kondycjonowanie zestawów może zredukować ogólny CSP do struktury drzewa i jest dość wydajne (wymaga tylko pamięci liniowej), jeśli można znaleźć mały zestaw elementów. Techniki dekompozycji drzewa przekształcają CSP w drzewo podproblemów i są wydajne, jeśli szerokość drzewa grafu ograniczeń jest mała; jednak potrzebują wykładniczej pamięci w szerokości drzewa grafu ograniczeń. Połączenie kondycjonowania cutsetów z rozkładem drzewa może pozwolić na lepszy kompromis pamięci w stosunku do czasu.

Do tej pory przyjrzeliśmy się strukturze grafu ograniczeń. Ważna struktura może również występować w wartościach zmiennych lub w samej strukturze relacji ograniczeń. Rozważ problem kolorowania mapy z kolorami. Dla każdego spójnego rozwiązania istnieje zestaw d! rozwiązań utworzonych przez permutację nazw kolorów. Na przykład na mapie Australii wiemy, że WA, NT i SA muszą mieć różne kolory, ale jest ich 3! = 6 sposobów na przypisanie trzech kolorów do trzech regionów. Nazywa się to symetrią wartości. Chcielibyśmy zmniejszyć przestrzeń poszukiwań o współczynnik d! łamiąc symetrię w zadaniach. Robimy to, wprowadzając ograniczenie łamiące symetrię. W naszym przykładzie możemy narzucić arbitralne ograniczenie kolejności, NT < SA < WA , które wymaga, aby trzy wartości były w porządku alfabetycznym. To ograniczenie zapewnia, że ​​tylko jedno z d! możliwe rozwiązania:

{NT = niebieski, SA = zielony, WA = czerwony}

W przypadku kolorowania mapy łatwo było znaleźć ograniczenie eliminujące symetrię. Ogólnie rzecz biorąc, NP-trudno jest wyeliminować całą symetrię, ale złamanie symetrii wartości okazało się ważne i skuteczne w wielu problemach.

Drugi sposób zredukowania grafu ograniczeń do drzewa opiera się na konstruowaniu dekompozycji drzewa grafu ograniczeń: przekształcenie oryginalnego grafu w drzewo, w którym każdy węzeł w drzewie składa się z zestawu zmiennych, jak na rysunku:

Rozkład drzewa musi spełniać te trzy wymagania:

* Każda zmienna w pierwotnym zadaniu pojawia się w co najmniej jednym z węzłów drzewa.

*Jeżeli dwie zmienne są połączone ograniczeniem w pierwotnym zadaniu, muszą występować razem (wraz z ograniczeniem) w co najmniej jednym z węzłów drzewa.

* Jeśli zmienna pojawia się w dwóch węzłach w drzewie, musi pojawić się w każdym węźle na ścieżce łączącej te węzły.

Pierwsze dwa warunki zapewniają, że wszystkie zmienne i ograniczenia są reprezentowane w dekompozycji drzewa. Trzeci warunek wydaje się dość techniczny, ale pozwala nam powiedzieć, że każda zmienna z pierwotnego problemu musi mieć tę samą wartość, gdziekolwiek się pojawi: ograniczenia w drzewie mówią, że zmienna w jednym węźle drzewa musi mieć taką samą wartość jak odpowiednia zmienna w sąsiednim węźle w drzewie. Na przykład SA pojawia się we wszystkich czterech połączonych węzłach na rysunku 6.13, więc każda krawędź w dekompozycji drzewa zawiera ograniczenie, że wartość SA w jednym węźle musi być taka sama jak wartość SA w następnym. Możesz sprawdzić na rysunku 6.12, że ta dekompozycja ma sens. Gdy mamy już graf o strukturze drzewa, możemy zastosować TREE-CSP-SOLVER, aby uzyskać rozwiązanie w czasie O(nd2), gdzie n jest liczbą węzłów drzewa i rozmiarem największej domeny. Zauważ jednak, że w drzewie domena jest zbiorem krotek wartości, a nie tylko pojedynczymi wartościami. Na przykład lewy górny węzeł na rysunku 6.13 reprezentuje, na poziomie pierwotnego problemu, podproblem ze zmiennymi {WA, NT SA} , domeną {czerwony, zielony, niebieski} i ograniczeniami WA ≠ NT, SA ≠ NT, WA ≠ SA . Na poziomie drzewa węzeł reprezentuje pojedynczą zmienną, którą możemy nazwać SANTWA, której wartością musi być trójka kolorów, np. {czerwony, zielony, niebieski}, ale nie {czerwony, czerwony, niebieski} , ponieważ naruszyłoby to ograniczenie SA ≠ NT z pierwotnego problemu. Następnie możemy przejść z tego węzła do sąsiedniego, ze zmienną, którą możemy nazwać SANTQ i stwierdzić, że istnieje tylko jedna krotka, {czerwona, zielona, ​​niebieska}, która jest zgodna z wyborem dla SANTWA. Dokładnie ten sam proces powtarzamy dla kolejnych dwóch węzłów i niezależnie możemy dokonać dowolnego wyboru dla T . Możemy rozwiązać każdy problem rozkładu drzewa w czasie O(nd2) za pomocą TREE-CSP-SOLVER, który będzie wydajny tak długo, jak d pozostanie małe. Wracając do naszego przykładu ze 100 zmiennymi boolowskimi, jeśli każdy węzeł ma 10 zmiennych, to d = 2¹⁰ i powinniśmy być w stanie rozwiązać problem w kilka sekund. Ale jeśli istnieje węzeł z 30 zmiennymi, zajęłoby to wieki.

Dany wykres dopuszcza wiele dekompozycji drzewa; przy wyborze rozkładu celem jest jak najmniejsze podproblemy. (Umieszczenie wszystkich zmiennych w jednym węźle jest technicznie drzewem, ale nie jest pomocne). Szerokość drzewa w dekompozycji drzewa grafu jest o jeden mniejsza niż rozmiar największego węzła; szerokość drzewa samego grafu jest zdefiniowana jako minimalna szerokość spośród wszystkich jego dekompozycji drzewa. Jeśli graf ma szerokość drzewa w, to problem można rozwiązać w czasie O(nd^w+1) przy odpowiedniej dekompozycji drzewa. Stąd CSP z grafami ograniczeń o ograniczonej szerokości drzewa są rozwiązywalne w czasie wielomianowym. Niestety znalezienie rozkładu przy minimalnej szerokości drzewa jest NP-trudne, ale są metody heurystyczne, które sprawdzają się w praktyce. Co jest lepsze: dekompozycja zestawu przekrojów w czasie O(dc ∙ (nc) lub dekompozycja drzewa w czasie O(nd^w+1)? Zawsze, gdy masz zestaw przekrojów cyklicznych o rozmiarze , występuje również szerokość drzewa o rozmiarze w < c+1, a w niektórych przypadkach może być znacznie mniejszy. Więc rozważenie czasu sprzyja dekompozycji drzewa, ale zaletą podejścia cykl-cutset jest to, że może być wykonane w pamięci liniowej, podczas gdy dekompozycja drzewa wymaga pamięci wykładniczej w w

Pierwszy sposób zredukowania wykresu ograniczeń do drzewa polega na przypisaniu wartości niektórym zmiennym, tak aby pozostałe zmienne utworzyły drzewo. Rozważmy wykres ograniczeń dla Australii, ponownie pokazany na rysunku 6.12(a). Bez Australii Południowej wykres stałby się drzewem, jak w (b). Na szczęście możemy usunąć Australię Południową (na wykresie, a nie kraj) poprzez ustalenie wartości dla SA i usunięcie z domen pozostałych zmiennych wszelkich wartości, które są niezgodne z wartością wybraną dla SA. Teraz każde rozwiązanie dla CSP po usunięciu SA i jego ograniczeń będzie zgodne z wartością wybraną dla SA. (Działa to dla binarnych dostawców CSP; sytuacja jest bardziej skomplikowana z ograniczeniami wyższego rzędu.) Dlatego możemy rozwiązać pozostałe drzewo za pomocą algorytmu podanego powyżej, a tym samym rozwiązać cały problem. Oczywiście w ogólnym przypadku (w przeciwieństwie do kolorowania mapy) wartość wybrana dla SA może być niewłaściwa, więc musielibyśmy wypróbować każdą możliwą wartość. Ogólny algorytm wygląda następująco:

1. Wybierz podzbiór S zmiennych CSP tak, aby wykres ograniczeń stał się drzewem po usunięciu S . S to tzw. cutset cyklu.
2. Dla każdego możliwego przypisania do zmiennych w S, które spełnia wszystkie ograniczenia na S,
3. usunąć z dziedzin pozostałych zmiennych wszelkie wartości niezgodne z przypisaniem dla S , oraz
4. jeśli pozostały CSP ma rozwiązanie, zwróć je wraz z przypisaniem dla S.

Jeśli cutset cyklu ma rozmiar c , to całkowity czas działania wynosi O(dc ∙ (nc)d² : musimy wypróbować każdą z kombinacji wartości d² dla zmiennych w , a dla każdej kombinacji musimy rozwiązać problem drzewa size (nc) Jeśli wykres jest „prawie drzewem”, to c będzie małe, a oszczędności w porównaniu z prostym śledzeniem wstecznym będą ogromne – dla naszego przykładu ze 100-zmiennymi boolowskimi, gdybyśmy mogli znaleźć zbiór o rozmiarze c = 20 , to sprowadziłoby nas z czasu życia Wszechświata do kilku minut.W najgorszym przypadku jednak może być tak duży jak (n-2).Znalezienie najmniejszego zestawu cyklicznego jest NP-trudne, ale kilka wydajnych algorytmów aproksymacyjnych Ogólne podejście algorytmiczne nosi nazwę warunkowania zestawu przekrojów.

W tej sekcji zbadamy, w jaki sposób struktura problemu, reprezentowana przez wykres ograniczeń, może być wykorzystana do szybkiego znalezienia rozwiązań. Większość z przedstawionych tutaj podejść ma również zastosowanie do innych problemów poza CSP, takich jak rozumowanie probabilistyczne. Jedynym sposobem, w jaki możemy mieć nadzieję na poradzenie sobie z ogromnym światem rzeczywistym, jest rozłożenie go na podproblemy. Patrząc ponownie na wykres ograniczeń dla Australii (rysunek 6.1(b), powtórzony jako rysunek 6.12(a) ), jeden fakt rzuca się w oczy: Tasmania nie jest połączona z lądem. Intuicyjnie jest oczywiste, że pokolorowanie Tasmanii i pokolorowanie lądu są niezależnymi podproblemami – każde rozwiązanie dla lądu połączone z dowolnym rozwiązaniem dla Tasmanii daje rozwiązanie dla całej mapy. Niezależność można ustalić po prostu przez znalezienie połączonych składowych grafu ograniczeń. Każdy składnik odpowiada podproblemowi CSPi. Jeśli przypisanie Si jest rozwiązaniem CSP_i , to U_iSⁱ jest rozwiązaniem U_iCSP_i. Dlaczego to jest ważne? Załóżmy, że każdy CSP_i ma c zmiennych z łącznej liczby n zmiennych, gdzie c jest stałą. Następnie są podproblemy n/c, z których rozwiązanie wymaga co najwyżej prądu stałego, gdzie jest rozmiarem domeny. Stąd całkowita praca to O(d^cn/c) , która jest liniowa w ; bez rozkładu całkowita praca to O(dⁿ) , która jest wykładnicza w n . Zróbmy to bardziej konkretnie: dzielenie a Boolean CSP ze 100 zmiennymi w czterech podproblemach skraca czas rozwiązania najgorszego przypadku z okresu istnienia wszechświata do mniej niż sekundy.

Całkowicie niezależne podproblemy są więc pyszne, ale rzadkie. Na szczęście inne struktury grafów są również łatwe do rozwiązania. Na przykład wykres ograniczeń to drzewo, gdy dowolne dwie zmienne są połączone tylko jedną ścieżką. Pokażemy, że każdy CSP o strukturze drzewa można rozwiązać w czasie liniowo pod względem liczby zmiennych. Kluczem jest nowe pojęcie spójności, zwane kierunkową spójnością łuku lub DAC. CSP jest zdefiniowany jako kierunkowy zgodny łukowo zgodnie z porządkiem zmiennych x1,X2…Xn wtedy i tylko wtedy, gdy każdy Xi jest zgodny łukowo z każdym Xj dla j > i .

Aby rozwiązać problem CSP o strukturze drzewa, najpierw wybierz dowolną zmienną, która będzie korzeniem drzewa, i wybierz kolejność zmiennych w taki sposób, aby każda zmienna pojawiała się po swoim rodzicu w drzewie. Takie uporządkowanie nazywa się sortowaniem topologicznym. Rysunek 6.10(a) przedstawia przykładowe drzewo, a (b) jedną z możliwych kolejności.

Każde drzewo z n węzłami ma n-1 krawędzi, więc możemy uczynić ten graf ukierunkowany łukowo w O(n) krokach, z których każdy musi porównywać do możliwych wartości domeny dla dwóch zmiennych, dla łącznego czasu O(nd2 ) . Gdy mamy już skierowany wykres zgodny z łukiem, możemy po prostu przejrzeć listę zmiennych i wybrać dowolną pozostałą wartość. Ponieważ każda krawędź od rodzica do jego dziecka jest spójna łukowo, wiemy, że dla dowolnej wartości, którą wybierzemy dla rodzica, pozostanie poprawna wartość do wyboru dla dziecka. Oznacza to, że nie będziemy musieli się cofać; możemy poruszać się liniowo przez zmienne.

Teraz, gdy mamy wydajny algorytm dla drzew, możemy rozważyć, czy bardziej ogólne grafy ograniczeń można jakoś zredukować do drzew. Można to zrobić na dwa sposoby: usuwając węzły  lub zwijając węzły razem.

Lokalne algorytmy wyszukiwania okazują się bardzo skuteczne w rozwiązywaniu wielu CSP. Używają sformułowania pełnego stanu (przedstawionego w rozdziale 4.1.1), w którym każdy stan przypisuje wartość do każdej zmiennej, a wyszukiwanie zmienia wartość jednej zmiennej na raz. Jako przykład użyjemy problemu 8-królowych. Na rysunku  zaczynamy po lewej stronie od pełnego przypisania do 8 zmiennych; zazwyczaj narusza to kilka ograniczeń.

Następnie losowo wybieramy zmienną powodującą konflikt, która okazuje się być Qs , skrajną prawą kolumną. Chcielibyśmy zmienić wartość na coś, co przybliża nas do rozwiązania; najbardziej oczywistym podejściem jest wybranie wartości, która powoduje minimalną liczbę konfliktów z innymi zmiennymi – heurystyka min – konfliktów.

Na rysunku widzimy dwa wiersze, które naruszają tylko jedno ograniczenie; wybieramy Q_s = 3 (czyli przenosimy hetmana do ósmej kolumny, trzeciego rzędu). W następnej iteracji, na środkowej planszy figury, wybieramy Q6 jako zmienną do zmiany i zauważamy, że przeniesienie hetmana do ósmego rzędu nie powoduje żadnych konfliktów. W tym momencie nie ma już sprzecznych zmiennych, więc mamy rozwiązanie.

Min-konflikty są zaskakująco skuteczne w przypadku wielu dostawców CSP. O dziwo, jeśli chodzi o problem -matek, jeśli nie liczyć początkowego rozmieszczenia hetmanów, czas trwania minikonfliktów jest z grubsza niezależny od rozmiaru problemu. Rozwiązuje nawet problem miliona królowych w średnio 50 krokach (po wstępnym zadaniu). Ta godna uwagi obserwacja była bodźcem prowadzącym do wielu badań w latach 90. nad wyszukiwaniem lokalnym i rozróżnieniem między łatwymi i trudnymi problemami. Z grubsza mówiąc, -queens jest łatwe do wyszukiwania lokalnego, ponieważ rozwiązania są gęsto rozmieszczone w przestrzeni stanów. Minkonflikty sprawdzają się również w przypadku trudnych problemów. Na przykład został wykorzystany do planowania obserwacji dla Kosmicznego Teleskopu Hubble’a, skracając czas potrzebny na zaplanowanie tygodniowych obserwacji z trzech tygodni (!) do około 10 minut. Wszystkie lokalne techniki wyszukiwania są kandydatami do zastosowania w CSP, a niektóre z nich okazały się szczególnie skuteczne. Krajobraz CSP w ramach heurystyki minikonfliktów zwykle ma szereg płaskowyżów. Mogą istnieć miliony przypisań zmiennych, od których dzieli tylko jeden konflikt od rozwiązania. Wyszukiwanie na płaskowyżu, które umożliwia przechodzenie na boki do innego stanu z tym samym wynikiem, może pomóc wyszukiwaniu lokalnemu w odnalezieniu drogi poza tym płaskowyżem. Tę wędrówkę po płaskowyżu można pokierować techniką zwaną wyszukiwaniem tabu: utrzymywanie małej listy ostatnio odwiedzanych stanów i zabranianie algorytmowi powrotu do tych stanów. Symulowane wyżarzanie może być również wykorzystane do ucieczki z płaskowyżów. Inna technika, zwana wagą ograniczeń, ma na celu skoncentrowanie poszukiwań na ważnych ograniczeniach. Każdemu ograniczeniu przypisywana jest waga liczbowa, początkowo równa 1. Na każdym etapie wyszukiwania algorytm wybiera parę zmienna/wartość do zmiany, która da w wyniku najniższą całkowitą wagę wszystkich naruszonych ograniczeń. Wagi są następnie dostosowywane przez zwiększenie wagi każdego ograniczenia, które jest naruszone przez bieżące przypisanie. Ma to dwie zalety: dodaje topografię do płaskowyżów, upewniając się, że można poprawić stan obecny, a także dodaje naukę: z czasem trudnym ograniczeniom przypisuje się wyższe wagi. Kolejną zaletą wyszukiwania lokalnego jest to, że można go używać w trybie online, gdy problem ulegnie zmianie. Rozważ problem z planowaniem tygodniowych lotów linii lotniczych. Harmonogram może obejmować tysiące lotów i dziesiątki tysięcy przydziałów personelu, ale zła pogoda na jednym lotnisku może sprawić, że harmonogram będzie niewykonalny. Chcielibyśmy naprawić harmonogram z minimalną liczbą zmian. Można to łatwo zrobić za pomocą lokalnego algorytmu wyszukiwania, zaczynając od bieżącego harmonogramu. Wyszukiwanie wsteczne z nowym zestawem ograniczeń zwykle wymaga znacznie więcej czasu i może znaleźć rozwiązanie z wieloma zmianami w bieżącym harmonogramie.

Kiedy dochodzimy do sprzeczności, backjumping może nam powiedzieć, jak daleko należy wykonać kopię zapasową, więc nie tracimy czasu na zmianę zmiennych, które nie rozwiążą problemu. Ale chcielibyśmy również uniknąć ponownego napotkania tego samego problemu. Kiedy wyszukiwanie dochodzi do sprzeczności, wiemy, że jakiś podzbiór zbioru konfliktów jest odpowiedzialny za problem. Uczenie się z ograniczeniami polega na znalezieniu minimalnego zestawu zmiennych ze zbioru konfliktu, który powoduje problem. Ten zestaw zmiennych, wraz z odpowiadającymi im wartościami, nazywany jest niedobrą. Następnie rejestrujemy niedobrze, albo dodając nowe ograniczenie do dostawcy usług Kryptograficznych, aby zabronić tej kombinacji przydziałów, albo przechowując osobną pamięć podręczną niedobrów.

Rozważmy na przykład stan {WA = czerwony, NT = zielony, Q = niebieski} w dolnym wierszu rysunku. Sprawdzanie w przód może nam powiedzieć, że ten stan jest zły, ponieważ nie ma prawidłowego przypisania do SA . W tym konkretnym przypadku nagranie tego, co nie jest dobre, nic by nie pomogło, ponieważ gdy usuniemy tę gałąź z drzewa wyszukiwania, nigdy więcej nie spotkamy tej kombinacji. Załóżmy jednak, że drzewo poszukiwań na rysunku 6.6 było w rzeczywistości częścią większego drzewa poszukiwań, które rozpoczęło się od przypisania wartości V i T . Wtedy warto byłoby odnotować {WA = czerwony, NT = zielony, Q = niebieski} jako niedobry, ponieważ ponownie napotkamy ten sam problem dla każdego możliwego zestawu przypisań do V i T . Brak towarów może być skutecznie wykorzystany przez sprawdzanie w przód lub przez backjumping. Uczenie się z ograniczeniami jest jedną z najważniejszych technik stosowanych przez współczesnych rozwiązujących CSP w celu osiągnięcia wydajności w przypadku złożonych problemów.

Algorytm BACKTRACKING-SEARCH na rysunku 6.5 ma bardzo prostą zasadę postępowania, gdy gałąź wyszukiwania nie powiedzie się: cofnij się do poprzedniej zmiennej i wypróbuj jej inną wartość. Nazywa się to wycofywaniem chronologicznym, ponieważ ponownie sprawdzany jest ostatni punkt decyzyjny. W tym podrozdziale rozważamy lepsze możliwości. Rozważmy, co się stanie, gdy zastosujemy proste śledzenie wstecz na rysunku 6.1 z uporządkowaniem stałej zmiennej Q, NSW, V, T, SA, WA, NT. Załóżmy, że wygenerowaliśmy przypisanie częściowe {Q = red , NSW = green, V = blue, T = red} . Kiedy próbujemy następnej zmiennej, SA , widzimy, że każda wartość narusza ograniczenie. Wracamy do T i próbujemy nowego koloru dla Tasmanii! Oczywiście jest to głupie przebarwianie Tasmanii nie może pomóc w rozwiązaniu problemu z Australią Południową. Bardziej inteligentnym podejściem jest cofnięcie się do zmiennej, która może rozwiązać problem – zmiennej, która była odpowiedzialna za uniemożliwienie jednej z możliwych wartości SA. Aby to zrobić, będziemy śledzić zestaw przypisań, które są w konflikcie z pewną wartością SA.

Zbiór (w tym przypadku {{Q = red , NSW = green, V = blue} ) nazywany jest zbiorem konfliktów dla SA. Metoda backjumping cofa się do najnowszego przypisania w zestawie konfliktów; w tym przypadku backjumping przeskoczyłby Tasmanię i spróbowałby nowej wartości dla V . Ta metoda jest łatwo zaimplementowana przez modyfikację BACKTRACK tak, że gromadzi zestaw konfliktów podczas sprawdzania legalnej wartości do przypisania. Jeśli nie zostanie znaleziona żadna prawidłowa wartość, algorytm powinien zwrócić ostatni element zbioru konfliktu wraz ze wskaźnikiem niepowodzenia.

Bystrooki czytelnik mógł zauważyć, że sprawdzanie w przód może dostarczyć zestaw konfliktów bez dodatkowej pracy: za każdym razem, gdy sprawdzanie w przód oparte na przypisaniu X = x usuwa wartość z domeny Y, powinno dodać X = x do zestawu konfliktów Y. Jeśli ostatnia wartość zostanie usunięta z domeny , wtedy przypisania w zbiorze konfliktów Y są dodawane do zbioru konfliktów X. Oznacza to, że teraz wiemy, że X = x prowadzi do sprzeczności (w Y ), a zatem różnica przypisania powinna być wypróbowane dla X . Czytelnik z orlim wzrokiem mógł zauważyć coś dziwnego: backjumping występuje, gdy każda wartość w domenie jest w konflikcie z bieżącym przypisaniem; ale sprawdzanie w przód wykrywa to zdarzenie i zapobiega dotarciu do takiego węzła przez wyszukiwanie! W rzeczywistości można wykazać, że każda gałąź przycinana przez backjumping jest również przycinana przez sprawdzanie w przód. W związku z tym proste cofanie jest zbędne w wyszukiwaniu z sprawdzaniem do przodu lub, w rzeczy samej, w wyszukiwaniu, które wykorzystuje silniejsze sprawdzanie spójności, takie jak MAC – wystarczy wykonać jedno lub drugie. Pomimo obserwacji z poprzedniego akapitu, idea backjumpingu pozostaje dobra: cofać się w oparciu o przyczyny porażki. Backjumping zauważa awarię, gdy domena zmiennej staje się pusta, ale w wielu przypadkach gałąź jest skazana na zagładę na długo przed tym, jak to nastąpi. Rozważmy ponownie przypisanie częściowe {WA = red , NSW = red} (które, z naszej wcześniejszej dyskusji, jest niespójne). Załóżmy, że próbujemy następnie T = czerwony, a następnie przypisujemy NT, Q ,V, SA. Wiemy, że żadne przypisanie nie może działać dla tych czterech ostatnich zmiennych, więc w końcu zabrakło nam wartości do wypróbowania w NT . Teraz pytanie brzmi, gdzie się cofnąć? Backjumping nie może działać, ponieważ NT ma wartości zgodne z poprzednio przypisanymi zmiennymi — NT nie ma pełnego zestawu konfliktów poprzedzających zmiennych, które spowodowały jego awarię. Wiemy jednak, że cztery zmienne NT , Q , V i SA razem wzięte zawiodły z powodu zestawu poprzedzających zmiennych, które muszą być tymi zmiennymi, które bezpośrednio kolidują z tymi czterema. Prowadzi to do innego i głębszego pojmowania zbioru konfliktów dla zmiennej takiej jak NT: jest to ten zbiór poprzedzających zmiennych, który spowodował, że NT, wraz z wszelkimi kolejnymi zmiennymi, nie mają spójnego rozwiązania. W tym przypadku zestaw to WA i NSW, więc algorytm powinien cofnąć się do NSW i pominąć Tasmanię. Algorytm backjumping, który wykorzystuje zdefiniowane w ten sposób zestawy konfliktów, nazywa się backjumpingiem skierowanym na konflikt

Musimy teraz wyjaśnić, jak obliczane są te nowe zbiory konfliktów. Metoda jest w rzeczywistości dość prosta. Błąd „terminalny” gałęzi wyszukiwania zawsze występuje, ponieważ domena zmiennej staje się pusta; ta zmienna ma standardowy zestaw konfliktów. W naszym przykładzie SA zawodzi, a jego zestaw konfliktów to (powiedzmy) {W,A,NT,Q}. Wracamy do Q , a Q absorbuje zbiór konfliktów z SA (oczywiście bez samego Q) do swojego własnego bezpośredniego zbioru konfliktów, którym jest {NT,NSW}; nowy zestaw konfliktów to {WA, NT , NSW} . Oznacza to, że od Q nie ma rozwiązania, biorąc pod uwagę poprzednie przypisanie do {WA, NT, NSW}. Dlatego wracamy do NT, ostatni z tych NT absorbuje {WA, NT, NSW} – {NT} do swojego własnego bezpośredniego zbioru konfliktów {W,A}, dając {WA, NSW} (jak podano w poprzednim akapicie ). Teraz algorytm wraca do NSW, tak jak mamy nadzieję. Podsumowując: niech Xj będzie zmienną bieżącą, a con f(Xj) niech będzie jej zbiorem konfliktu. Jeśli każda możliwa wartość Xj zawiedzie, wróć do ostatniej zmiennej Xi w conf(Xj) i ponownie oblicz konflikt ustawiony dla Xi w następujący sposób: