Redukce

Předložená úloha je dekomponována na řadu dílčích podúloh (podcílů), které se dále mohou strukturovat v ještě jednodušší úlohy. Celý proces je rekurzivně opakován až do okamžiku, kdy je celá úloha rozdělena na řešení triviálních elementárních úloh, na jejichž vyřešení má výpočetní systém k dispozici prostředky.

Tyto metody je možné použít na řadu praktických úloh, jako je například dokazování vět, symbolické integrování jako formálních manipulací s výrazy, redukci hledání výhry u řady her na hledání dalšího vhodného tahu, např. u šachů, dámy apod.

Operátory redukce úloh na množinu podúloh

Operátory redukce jsou v konkrétních implementacích navrhovány tak, aby umožnily rozdělení (transformaci) předloženého popisu úlohy na množinu podúloh, a transformují popis dané úlohy na množinu rezultujících popisů úloh. Uvažovaná transformace musí být taková, že řešení všech rezultujících úloh zaručuje řešení původní úlohy. Je-li rezultující množina jednoprvková, potom jde o záměnu úlohy za úlohu s ní ekvivalentní.

V praktických aplikacích je možné, že existuje více alternativ redukce předložené úlohy na podúlohy. Některé z těchto redukcí se mohou ukázat jako neperspektivní, protože některé z dílčích úloh mohou být neřešitelné.

Popis elementárních úloh

Cílem redukce je předložit k řešení takové elementární úlohy, jejichž řešení je zřejmé. Takovými úlohami mohou být úlohy odpovídající jednomu kroku ve stavovém prostoru, případně i úlohy složitější, jejichž řešení je ovšem známo. Úroveň elementárních úloh hraje roli při ukončení procesu redukce nebo i při výběru vhodné alternativy redukce. Do mechanismu redukce je možno zahrnout i proces určení, v němž některé často se opakující řešitelné úlohy lze po úspěšném vyřešení zahrnout mezi elementární úlohy.

Příklad: zobrazení řešených problémů redukcí na alternativní množiny rezultujících problémů je užitečné používat grafové struktury.

Uzly M, N, F jsou příklady uzlů typu NEBO (OR-node). Úlohu N lze převést na množinu podúloh B a C, přičemž obě musí být vyřešeny. Uzly B, C jsou příklady uzlu typu A (AND-node) a hrany k nim vedoucí jsou spojeny v transformačním grafu obloučkem. Tyto grafy se též nazývají AND/OR grafy.

Důkazy vět

Pro důkazy vět platí následující obecné schéma. Nechť se má dokázat tvrzení S za předpokladu platnosti podmínek T - schématicky S/T. Princip redukce na podproblémy spočívá v tom, že nelze většinou tento důkaz provést přímo. Je nutné zformulovat řadu nových tvrzení X₁, X_{2, ...} X_n tak, že postupně dokážeme:

X₁ / T

X₂ / T, X₁

_...

Xn / T, X_1, X_{2, ...,} X_n-1

S/ T, X₁, ..., X_n

přičemž v každém kroku vlastně dostáváme nové dílčí tvrzení.

Hry

Metoda redukce problémů na podproblémy může být úspěšně použita i pro jisté typy her; speciálně u antagonistických her dvou hráčů, soupeři se střídají v tazích a je jim známo, jaké jsou jejich možnosti v této hře. Půjde nám o hry, v nichž jeden z hráčů vyhraje (a druhý prohraje), případně se hráči shodnou na remíze. Příkladem mohou být hry typu piškvorky, go, dáma nebo šachy. Neuvažujeme zde hry, v nichž se projevuje prvek náhody, např. hry v kostky či karetní hry.

Proces redukce problému je prováděn za účelem toho, abychom procesu důkazu ukázali, že daná hra může být vyhrána. Při popisu problému je tedy nutno popsat počáteční stav hry (též konfigurace), pro kterou se má dokázat, že ji lze vyhrát. Například u šachů musí být známo rozestavení figurek na šachovnici a to, který soupeř je na tahu. Aplikace operátorů (tj. tahů) ve hře vede k vytvoření struktury, zvané graf hry. Elementárními úlohami jsou pravidla ukončení hry a proces důkazu je realizován do té doby, dokud nejsou nalezeny elementární úlohy. Ve většině her není možné explicitně generovat strom hry vzhledem k jeho rozsahu.

Podrobnější informace v [16, 2].