Algorytm minimalnych konfliktów
W informatyce algorytm min-konfliktów jest algorytmem wyszukiwania lub heurystyczną metodą rozwiązywania problemów spełniania ograniczeń .
Biorąc pod uwagę początkowe przypisanie wartości wszystkim zmiennym problemu spełniania ograniczeń, algorytm losowo wybiera zmienną ze zbioru zmiennych z konfliktami naruszającymi jedno lub więcej jego ograniczeń. Następnie przypisuje tej zmiennej wartość, która minimalizuje liczbę konfliktów. Jeśli istnieje więcej niż jedna wartość z minimalną liczbą konfliktów, wybierana jest losowo. Ten proces losowego wyboru zmiennej i przypisywania wartości minimalnego konfliktu jest powtarzany aż do znalezienia rozwiązania lub osiągnięcia wcześniej wybranej maksymalnej liczby iteracji.
Ponieważ problem spełniania ograniczeń można interpretować jako problem wyszukiwania lokalnego , gdy wszystkie zmienne mają przypisaną wartość (nazywaną stanem pełnym), algorytm minimalnych konfliktów można postrzegać jako heurystykę naprawy, która wybiera stan z minimalną liczbą konfliktów.
Algorytm
jest algorytm MIN-KONFLIKTY : konsola. csp , Problem spełnienia ograniczeń. max_steps , Dozwolona liczba kroków przed poddaniem się. stan_bieżący , Początkowe przypisanie wartości do zmiennych w pliku csp. dane wyjściowe: Zestaw rozwiązań wartości dla zmiennej lub niepowodzenia . dla i ← 1 do max_steps zrobić jeśli stan_bieżący jest rozwiązaniem csp wtedy
return current_state set var ← losowo wybrana zmienna ze zbioru zmiennych będących w konflikcie KONFLIKT[ csp ] set value ← wartość v dla var minimalizująca KONFLIKTY( var , v , current_state , csp ) set var ← wartość w current_state return niepowodzenie
Chociaż nie jest to określone w algorytmie, dobre wstępne przypisanie może mieć kluczowe znaczenie dla szybkiego podejścia do rozwiązania. Użyj zachłannego algorytmu z pewnym poziomem losowości i pozwól, aby przypisanie zmiennych przełamało ograniczenia, gdy żadne inne przypisanie nie będzie wystarczające. Losowość pomaga minimalnym konfliktom uniknąć lokalnych minimów utworzonych przez początkowe przypisanie algorytmu zachłannego. W rzeczywistości problemy spełniania ograniczeń, które najlepiej reagują na rozwiązanie z minimalnymi konfliktami, dobrze sobie radzą tam, gdzie zachłanny algorytm prawie rozwiązuje problem. Kolorowanie mapy problemy radzą sobie słabo z Algorytmem Chciwym oraz Min-Konfliktami. Podobszary mapy mają tendencję do utrzymywania swoich kolorów na stałym poziomie, a minimalne konflikty nie mogą wspinać się po wzgórzach, aby wyrwać się z lokalnego minimum. Funkcja KONFLIKTY zlicza liczbę ograniczeń naruszonych przez określony obiekt, przy założeniu, że znany jest stan pozostałej części przypisania.
Historia
Chociaż sztuczna inteligencja i optymalizacja dyskretna znały problemy spełniania ograniczeń i uzasadniały je od wielu lat, dopiero na początku lat 90. ten proces rozwiązywania dużych CSP został skodyfikowany w formie algorytmicznej. Na początku Mark Johnston z Space Telescope Science Institute poszukiwał metody planowania obserwacji astronomicznych za pomocą Kosmicznego Teleskopu Hubble'a . We współpracy z Hansem-Martinem Adorfem z Europejskiego Centrum Koordynacyjnego Teleskopu Kosmicznego stworzył sieć neuronową zdolną do rozwiązywania zabawek n -problem hetmanów (dla 1024 hetmanów). Steven Minton i Andy Philips przeanalizowali algorytm sieci neuronowej i podzielili go na dwie fazy: (1) wstępne przypisanie przy użyciu algorytmu zachłannego i (2) fazy minimalizacji konfliktów (później nazwane „min-konfliktami”). Artykuł został napisany i przedstawiony na AAAI-90; Philip Laird przedstawił matematyczną analizę algorytmu.
Następnie Mark Johnston i personel STScI wykorzystali min-konflikty do zaplanowania czasu obserwacji astronomów na Kosmicznym Teleskopie Hubble'a.
Przykład
Min-Conflicts rozwiązuje problem N -Queens, losowo wybierając kolumnę z szachownicy do zmiany przypisania hetmana. Algorytm przeszukuje każdy potencjalny ruch pod kątem liczby konfliktów (liczby atakujących hetmanów), pokazanej na każdym kwadracie. Algorytm przesuwa hetmana na pole z minimalną liczbą konfliktów, losowo rozwiązując remisy. Zauważ, że liczba konfliktów jest generowana przez każdy nowy kierunek, z którego hetman może zaatakować. Jeśli dwie królowe zaatakowałyby z tego samego kierunku (rzędu lub po przekątnej), konflikt liczy się tylko raz. Należy również zauważyć, że jeśli hetman znajduje się w pozycji, w której ruch spowodowałby większy konflikt niż jego obecna pozycja, nie wykonuje ruchu. Wynika z tego, że jeśli hetman jest w stanie minimalnego konfliktu, nie musi się ruszać.
Czas działania tego algorytmu przy rozwiązywaniu N -Queens jest niezależny od rozmiaru problemu. Algorytm ten rozwiąże nawet problem miliona hetmanów średnio w 50 krokach. To odkrycie i obserwacje doprowadziły do wielu badań w 1990 roku i zapoczątkowały badania nad lokalnymi problemami wyszukiwania oraz rozróżnieniem między łatwymi i trudnymi problemami. N -Queens jest łatwy do wyszukiwania lokalnego, ponieważ rozwiązania są gęsto rozmieszczone w przestrzeni stanów. Jest również skuteczny w przypadku trudnych problemów. Na przykład był używany do planowania obserwacji dla Kosmicznego Teleskopu Hubble'a , skracając czas potrzebny do zaplanowania tygodniowych obserwacji z trzech tygodni do około 10 minut.
Zobacz też
Linki zewnętrzne
- [1] Mikroforma heurystyczna min-konfliktów: eksperyment i wyniki teoretyczne / Steven Minton… [i in.]. NASA, Ames Research Center, Oddział Badań nad Sztuczną Inteligencją. Rozesłane do bibliotek depozytowych w mikrofiszach.