Presná definícia
Čo znamená splnenie obmedzení?
Splnenie obmedzení je riešenie úlohy, v ktorej sa každej premennej priradí hodnota z jej domény tak, aby boli súčasne splnené všetky tvrdé obmedzenia. Trojica premenné-domény-obmedzenia tvorí problém splnenia obmedzení (CSP); riešením je úplné konzistentné priradenie. Na rozdiel od bežného hľadania často nezáleží na poradí krokov. Ak sa hľadá najlepšie prípustné riešenie, ide už o obmedzenú optimalizáciu.
Skúsenosť a kontext
Ako sa pojem používa v praxi
Pri tvorbe rozvrhu sú premennými skúšky, doménami termíny a miestnosti a obmedzeniami kapacita, dostupnosť a zákaz kolízie študentov. Modelovanie začína oddelením tvrdých požiadaviek od mäkkých preferencií; nesplniteľný model potrebuje diagnostiku konfliktnej množiny, nie nekonečné hľadanie. Riešič používa propagáciu obmedzení, heuristiky poradia premenných a spätné prehľadávanie. Testujú sa malé prípady s ručne známym riešením, hranice domén, symetrie a zámerne nesplniteľné vstupy. Pri zmene pravidla sa kontroluje, ktoré predchádzajúce riešenia prestali byť platné.
Overiteľnosť
Odborné zdroje
Praktické odpovede
Často kladené otázky
Z čoho sa CSP skladá?
Z premenných, domény povolených hodnôt pre každú premennú a obmedzení nad jednou alebo viacerými premennými.
Čo je riešením CSP?
Úplné priradenie hodnôt všetkým premenným, ktoré neporušuje žiadne tvrdé obmedzenie.
Čo robí propagácia obmedzení?
Odstraňuje hodnoty, ktoré nemôžu byť súčasťou riešenia, a tým zmenšuje priestor pred alebo počas hľadania.
Ako sa vysvetlí, že riešenie neexistuje?
Hľadaním malej konfliktnej množiny obmedzení a prekladom konfliktu do doménového vysvetlenia.
Ako sa CSP líši od obmedzenej optimalizácie?
CSP hľadá ľubovoľné prípustné priradenie; optimalizácia medzi prípustnými riešeniami vyberá najlepšie podľa cieľa.