Hlavní navigace

Answer Set Programming

7. 2. 2014 19:12 zboj

Nikdo jistě nepochybuje o užitečnosti logického programování. Znalost většiny vývojářů ovšem končí u Prologu (pokud vůbec), což je sice velmi elegantní a propracovaný jazyk, ale má i pár nevýhod. Moderní implementace nabízejí tabling, čímž zaručují vyvarování se nekonečné smyčky, pokud program splňuje „bounded term-depth property“, ale až na nečetné výjimky nepodporují disjunkci (protože trvají na Hornových klauzulích). Řešení poskytuje až ASP (dříve nazývané „stable models programming“).

Na první pohled vypadá program v ASP jako program v Prologu. Jedním z hlavních rozdílů je, že umožňuje disjunkci v hlavě pravidla. Výsledkem programu jsou pak všechny stabilní modely, jež odpovídají daným faktům a pravidlům. Typické použití je pro řešení kombinatorických problémů, například barvení grafu.

Z programu v ASP se nejdříve odstraní proměnné, tj. logicky se pravidla převedou na výrokovou logiku. Následně se použije SAT solver, jenž zkonstruuje model (nebo modely), pokud je množina formulí splnitelná. U nedisjunktních programů je tedy výsledek stejný, jako v Prologu (který používá SLD rezoluci).

Jednoduchý příklad:

borders(czechia,slovakia). borders(czechia,poland). borders(X,Y) :- borders(Y,X).

Prolog korektně vydá čtyři výsledky, stejně jako ASP, nicméně Prolog k nim dojde směrem od dotazu, kdežto v případě ASP se vybuduje celý model „odspodu“.

Z uvedeného vyplývá, že bez disjunkce je efektivnější použít Prolog. Pokud však charakter problému vyžaduje disjunkci, je ASP lepší volbou.

Sdílet