Přejít na cvičení:
Doplňování textu
Přejít na téma:
Splňování podmínek
Zobrazit na celou obrazovku
Procvičujte neomezeně

Váš denní počet odpovědí je omezen. Pro navýšení limitu či přístup do svého účtu s licencí se přihlaste.

Přihlásit se
Zobrazit shrnutí tématu
NKF
Sdílet

QR kód

QR kód lze naskenovat např. mobilním telefonem a tak se dostat přímo k danému cvičení nebo sadě příkladů.

Kód / krátká adresa

Tříznakový kód lze napsat do vyhledávacího řádku, také je součástí zkrácené adresy.

Zkopírujte kliknutím.

NKF
umime.to/NKF

umime.to/NKF

Splňování podmínek

Mnoho úloh umělé inteligence lze formulovat jako splňování podmínek. Úloha splňování podmínek je zadaná sadou proměnných, jejich doménami (možné hodnoty) a sadou podmínek na kombinace hodnot proměnných. Ohodnocení (přiřazení hodnot některým proměnným) je řešením úlohy, pokud je úplné (přiřazuje hodnotu všem proměnným) a konzistentní (neporušuje žádnou podmínku). Někdy je navíc zadána účelová funkce určující hodnotu řešení, kterou chceme optimalizovat.

Oblast informatiky zabývající se touto úlohou se označuje jako programování s omezujícími podmínkami. Splňování podmínek je podstatou mnohých logických úloh (např. problém 8 dam, Einsteinova hádanka, algebrogram). Na Umíme si můžete vyzkoušet sudoku, ploty a binární křížovku. Praktickou aplikací je třeba sestavování konfigurací produktu splňující zadaná omezení nebo tvorba rozvrhů (školní rozvrhy, jízdní řády, logistika výroby, rozpis zápasů na turnaji).

Problém 8 dam

Úkol rozestavit na šachovnici 8 dam tak, aby se žádné dvě vzájemně neohrožovaly. (Dáma se může pohybovat o libovolný počet polí vodorovně, svisle i diagonálně.) Úlohu lze zobecnit na „problém N dam“, které máme umístit na šachovnici velikosti N×N.

Einsteinova hádanka

Úkol odvodit vlastnosti několika objektů na základě omezených informací. Nejznámější zadání popisuje pět domů, které stojí vedle sebe, liší se barvou, národností majitelů, jejich oblíbeným nápojem, značkou cigaret a domácím mazlíčkem. K dispozici máme 15 informací typu „Angličan žije v červeném domě.“

Algebrogram

Úkol nahradit písmena za různé číslice tak, aby byl splněný zadaný vzorec. Příklad: SEND + MORE = MONEY.

Řešení úloh splňování podmínek

Jakmile nějaký problém namodelujeme jako úlohu splňování podmínek, lze využít obecné postupy pro jejich řešení. Naivní zkoušení všech možných ohodnocení (generuj a testuj) většinou bude příliš pomalé, protože počet možných ohodnocení roste exponenciálně k počtu proměnných. K řešení se proto typicky používá postupné budování řešení s propagací omezení, nebo postupné zlepšování úplného ohodnocení.

Které problémy jsou těžké?

Obtížnost úloh s omezujícími podmínkami závisí na poměru počtu omezení ku počtu proměnných. Pokud je tento poměr hodně vysoký, nebo naopak hodně nízký, pak bude snadné nějaké řešení nalézt (nebo zjistit, že žádné neexistuje). Představte si sudoku, které má téměř všechna pole vyplněná (je snadné určit zbývající čísla), nebo naopak má vyplněných polí jen pár (existuje mnoho různých řešení).

Postupné budování řešení

Tento přístup spočívá v systematickém zkoušení možných ohodnocení. Na rozdíl od „generuj a testuj“ však ohodnocujeme jednotlivé proměnné postupně a průběžně kontrolujeme, zda nedošlo k porušení některé podmínky. Pokud ano, vyzkoušíme jinou hodnotu. Pokud jsme už vyzkoušeli všechny možné hodnoty dané proměnné, vracíme se k předchozí proměnné a zkusíme změnit její hodnotu (těchto návratů může být libovolné množství). Tomuto algoritmu se říká prohledávání s návratem (backtracking).

Splňování podmínek vs. plánování

Úlohu splňování podmínek lze formulovat jako úlohu plánování, v němž stavy představují různá ohodnocení proměnných, počáteční stav je prázdné ohodnocení, akce odpovídají přiřazení hodnoty do jedné proměnné a cílovým stavem je úplné konzistentní ohodnocení. (Všechna řešení jsou tedy ve stejné hloubce dané počtem proměnných.)

Rozdíl od obecné plánovací úlohy spočívá v tom, že stavy a cíl mají vnitřní strukturu – stav se skládá z hodnot více proměnných, cíl se skládá z více podmínek. Díky této vnitřní struktuře lze úlohy splňování podmínek řešit výrazně efektivněji než obecnými technikami prohledávání stavového prostoru. Můžeme například poznat, že jsme ve slepé větvi, když není některá podmínka splněná. Druhý rozdíl spočívá v tom, že nás nezajímá plán (posloupnost akcí vedoucí do cíle, např. pořadí vyplňování políček sudoku), ale cílový stav (ohodnocení proměnných, např. vyplněné sudoku).

Prohledávání s návratem (backtracking) je v podstatě prohledávání do hloubky (DFS) s včasnou kontrolou porušení podmínek. (Druhým rozdílem je, že nezáleží na pořadí akcí – výsledné řešení je stejné, ať jsme nejdříve přiřadili hodnotu proměnné A nebo B. Při prohledávání s návratem proto stačí prohledávat pouze jedno pořadí proměnných.)

Velký vliv na rychlost prohledávání s návratem mají heuristiky pro výběr proměnné a její hodnoty. Pro výběr proměnné se využívá princip brzkého neúspěchu: vybíráme proměnnou, pro kterou je těžké najít hodnotu (např. tu s nejmenší doménou). Naopak, pro výběr hodnot je vhodnější princip brzkého úspěchu, tedy výběr hodnoty, která by nejspíše mohla být součástí řešení (např. tu, která způsobí nejmenší filtraci domén). Důvod k opačným principům pro výběr proměnné a hodnoty spočívá v tom, že proměnné musíme nakonec projít všechny, ale hodnoty nikoliv.

Prohledávání s návratem lze dále výrazně urychlit propagací omezení. Po každé volbě hodnoty provedeme filtrování domén, čímž se zmenší počet hodnot budoucích proměnných, které bude potřeba zkoušet.

Propagace omezení

Z domén proměnných můžeme bezpečně odstranit hodnoty, pro které nelze splnit některou podmínku (neexistují hodnoty ostatních proměnných v podmínce, pro které by podmínka platila). (Sudoku: Když už je někde umístěná číslice, můžeme ji vyškrtnout z domén všech políček na stejném řádku, sloupci a čtverci.) Pokud zbývá v doméně proměnné jediná možná hodnota, známe část řešení.

Podmínky můžeme kontrolovat opakovaně, dokud se nám daří nějaké hodnoty vyškrtávat. V ojedinělých případech (lehká sudoku) lze opakovaným filtrováním získat celé řešení, častěji však pouze úlohu zjednodušíme a pak je potřeba zkoušet různé možné hodnoty (proto se propagace omezení využívá typicky v kombinaci s prohledáváním s návratem).

Výraznějšího filtrování dosáhneme, když budeme kontrolovat současně splnění více podmínek naráz, nikoliv vždy jen jedné (to ale zvyšuje výpočetní náročnost).

Postupné zlepšování

Alternativou k postupnému budování řešení je začít s kompletním ohodnocením (klidně náhodným) a to postupně vylepšovat drobnými úpravami. Ohodnocení je tedy celou dobu úplné, ale nikoliv konzistentní. Vylepšení je taková změna ohodnocení, která zmenší počet porušených podmínek. Algoritmy postupného zlepšování lze rozdělit do dvou kategorií podle toho, jestli pracují v jeden moment s jediným ohodnocením (lokální prohledávání) nebo s více naráz (prohledávání s populací).

Lokální prohledávání pracuje s jedním ohodnocením, které postupně vylepšuje. Množina všech ohodnocení, které se od toho současného lidí jednou změnou, nazýváme okolí. Metoda největšího stoupání (horolezecký algoritmus) vybírá z okolí to ohodnocení, které vede k nejvýraznějšímu zlepšení. Tímto postupem se rychle dostaneme do lokálního optima, kdy všechny okolní stavy jsou horší. Lokální optimum však nemusí být optimem globálním, zejména tedy nemusí jít o přípustné řešení.

Proto je potřeba využít meta-heuristiky, které vnáší do prohledávání prvek náhodnosti a tedy šanci uniknout lokálnímu optimu. Příkladem meta-heuristiky je simulované žíhání, při kterém z okolí vybíráme náhodně; pokud je nové ohodnocení zlepšující, tak ho přijmeme, pokud není zlepšující, tak ho přijmeme s určitou pravděpodobností, která se postupně snižuje. Jednoduchou meta-heuristikou je také opakované spouštění lokálního prohledávání z různých náhodných počátečních ohodnocení.

Při prohledávání s populací vylepšujeme mnoho ohodnocení naráz. To umožňuje vybírat nejlepší ohodnocení z aktuální populace a případně různá ohodnocení kombinovat. Příkladem jsou genetické algoritmy inspirované fungováním evoluce. Ohodnocení pokračující do další generace jsou vybírána podle jejich kvality, kombinována („křížení“) a případně drobně náhodně měněna („mutace“). Do této kategorie patří také další algoritmy inspirované přírodou, které využívají velké množství interagujících agentů reprezentujících úplná ohodnocení. (Například při „optimalizaci mravenčí kolonií“ má každý mravenec přidružené ohodnocení a podle jeho kvality vydává různě silnou feromonovou stopu – čím je ohodnocení lepší, tím spíš budou další mravenci zkoušet podobná ohodnocení.)

Zavřít

Splňování podmínek (střední)

NAPIŠTE NÁM

Děkujeme za vaši zprávu, byla úspěšně odeslána.

Napište nám

Nevíte si rady?

Nejprve se prosím podívejte na časté dotazy:

Čeho se zpráva týká?

Vzkaz Obsah Ovládání Přihlášení Licence