928100428

Autorzy: kulfoniasty& switch486 Źródło: wykłady dr Haliny Kwaśnickiej.

07. Zdefiniuj problem spełniania ograniczeń. Jakie znasz metody jego rozwiązywania wymień je i omow jedna z nich(@ work)

•    CSP charakteryzowany jest przez trzy składowe (liczba zmiennych jest wymiarem CPS):

zmienne: V1,V2,...,Vn

-    ich dziedziny (odpowiednio): Dl ,D2.....Dn

-    ograniczenie qk dla k=

•jest zdefiniowane na iloczynach kartezjańskich zbiorów wartości

• jest j-relacją. jG{ 1 n}: qGDxDx...xD

• Binarne ograniczenia można przedstawiać na grafie ograniczeń. Wielowymiarowe ograniczenia rzecz jasna w hipergrafie lub w sieci ograniczeń,

1. Przegląd wszystkich możliwych wartości zmiennych -

przegląd zupełny zapewnia znalezienie rozwiązania -złożoność obliczeniowa: DlxD2x...xDn.\E (Di,E - liczności zbiorów)

I. Algorytm z powrotami

zmniejsza liczbę sprawdzanych kombinacji dla złożonych problemów - nie są wystarczające

3