niekto tu vysvetloval tento algoritmus...
ak by bol taky dobry a vysvetlil to este raz? lebo som si to neskopiroval...
Algoritmus spätného zreťazenia:
function SPäTNÉ-ZREŤAZENIE-PRAVIDIEL (BP, cieľ)
returns úspech alebo neúspech
inputs: BP, báza pravidiel
cieľ, hypotéza, ktorú interpret pravidiel preukazuje
static: PP, pracovná pamäť
MAP, množina aplikovateľných pravidiel
aktuálne_pravidlo, pravidlo
if cieľ platí then return úspech
MAP <- VYTVOR-KONFLIKTOVÚ-MNOŽINU (cieľ, BP, PP)
loop do
if MAP je prázdna then return neúspech
aktuálne_pravidlo <- RIEŠENIE_KONFLIKTOV (MAP)
MAP <- MAP / { aktuálne_pravidlo }
if SPäTNÉ-ZREŤAZENIE-PRAVIDIEL (BP, PODMIENKA (aktuálne_pravidlo))
then return úspech
end
tak znova.. algoritmus dokazuje jeden ciel, preto je vstupom dokazovana hypoteza - ciel.. dalej samozrejme potrebuje Bazu pravidiel BP..
1. ako prve zisti, ci ciel nahodou nie je dokazatelny (t.j. ci napr. nie je axiomou systemu), ak ano , nie je co riesit, vracia uspech
2. inak vytvori MAP - mnozinu aplikovatelnych pravidiel, analyzou pracovnej pamäte PP, principialne je aplikovatelne pravidlo take pravidlo z bazy pravidiel, ktore ma v dosledkovej casti vyskyt dokazovaneho ciela, hypotezy, teda MAP bude obsahovat vsetky pravidla s cielom v pravej casti pravidla
3. ak je MAP prazdna (t.j. nie je pravidlo, ktorym by sa dal ciel dokazat), koniec alg. a vracia sa neuspech
4. vyberie sa aktualne pravidlo podla nejakej logiky riesenia konfliktov (napr. nahodne, alebo prve v poradi)
5. aktualne pravidlo sa odstrani z MAP (tymto sa MAP vyprazdnuje, ak sa v cykle vyprazdni uplne, tak 3. krok ohlasi ze ciel nie je dokazatelny)
6. tu sa testuje podmienkova cast aktualneho pravidla, ta sa samozrejme moze skladat zo zlozitejsich logickych vyrazov ako len jednej hypotezy, v jeho algoritme je to vyjadrene iba principialne.. v skutocnosti moze ist napr. o testovanie vsetkych hypotez v podmienkovej casti a teda o akysi cyklus. implementacia vsak nie je podstatna, ide o to ze vezmes podmienkovu cast a pouzitim rekurzivneho volania spatneho zretazenia sa ju pokusis dokazat
7. ak sa ti podmienkovu cast aktualneho pravidla podari dokazat tak si vlastne dokazal ze hypoteza je dokazatelna pouzitim daneho pravidla a vracias uspech
8. inak pokracujes 3. krokom (tj skusis dalsie pravidlo, ak este nejake pouzitelne je)
ak chces, mozem ti poslat, resp. niekde zavesit program na vizualizaciu ZS na baze pravidiel, co sme mali ako zadanie, myslim ze ten to dost dobre ukazuje (aj ked nas alg. ten 6. krok konkretnejsie, aby sme to vedeli vizualizovat, ale princip je ten isty)