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).

Ř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í.

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).

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 optimemem 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í.)