Лекции по логическо програмиране
Дърво на търсене за хорнова цел при хорнова програма
Изтегляне 2.18 Mb.
|
Дърво на търсене за хорнова цел при хорнова програманека P е множество; нека T е непразно множество от крайни редици с елементи от P (допускаме празната редица); казваме, че T е дървовидно, ако от (p1, p2, …, pn) T (p1, …, pk) T за всяко k = 0, 1, …, n-1, т.е. T съдържа началата на всички свои редици; естествено () T, тъй като () е начало на всяка редица; образуваме следния граф: GT (T, E), E = { ((p1, …, pn), (p1, …, pn+1)), (p1, …, pn+1) T } ; ясно е, че GT е свързан граф, тъй като съществува път от () до всеки елемент на T; при това този път е единствен: ако (p1, …, pn) T, то (), (p1), …, (p1, …, pn) е единственият път от () до (p1, …, pn); така GT е дърво; например при P = { a, b, c, d, e } и T = { (), (a), (b), (a, c), (a, d), (b, e) } дървото GT можем да изобразим по следния начин:   
a b c d e върховете съответстват на елементите на T – коренът на дървото съответства на празната редица (); редицата, съответна на даден връх се получава по следния начин : образуваме единствения път от () до тази редица, но вместо самите ребра записваме етикетите им, които са елементи на P; нека P е хорнова програма; нека G е хорнова цел; нека T е множеството от онези крайни редици от клаузи от P, такива че G има резолвента с тези редици; T е дървовидно : нека (C1, C2, …, Cn) T, т.е. съществува редица от хорнови цели G = G0, G1, …, Gn, такива че Gi е непосредствена резолвента на Gi-1 и Ci, i = 1, …, n; тогава за k = 0, …, n-1 имаме, че (C1, C2, …, Ck) T, тъй като G0, G1, …, Gk е редица от хорнови цели, такава че Gi е непосредствена резолвента на Gi-1 и Ci, i = 1, 2, …, k; дървото GT наричаме дърво на търсенето за G при програмата P; ясно е, че разклонеността на GT е по-малка или равна на броя на клаузите в P; една цел G наричаме успяваща в програмата P, ако дървото GT съдържа лист, който е надписан с празната цел true; в противен случай, казваме че G е пропадаща в програмата P; ясно е, че ако G е успяваща в програмата P, то G е изпълнима при P; при това, ако при построяването на GT се използват само най-общи резолвенти, то от пълнотата на резолюцията при използване на канонични резолвентни редици получаваме, че ако G е изпълнима при P, то G е успяваща в P; при построяване на дървото GT ще използваме само най-общи резолвенти; изобразяваме го по следния начин: във върховете на дървото записваме целта, която е канонична резолвента на G с редицата, получена от единствения път от корена на дървото до съответния връх като проследим етикетите на ребрата; при това, ако при образуване на съответната резолвента използваме частен случай на целта в етикета на реброто отбелязваме субституцията, която е използвана; пример: да разгледаме следната хорнова програма P = { p (a, f (a)), p (X, a) :– p (X, f (X)), p (f (X), f (Y)) :– p (X, Y), q (X, Y) :– p (X, Y), p (Y, X) }; за удобство номерираме клаузите в реда в който са дадени с 1, 2, 3, 4; нека G = q (a, Z); строим дървото на търсене на хорновата цел G при програмата P, при това използваме само най-общи резолвенти; 
q (a, Z) 
4 
p (a, Z), p (Z, a)   
p (a, f (a)), p (a, a) 2 [Z/a] 
p (f (a), a)
2 1 [Z/f (a)] 
p (f (a), f (f (a)))
3
p (a, f (a))
1
true
1
p (a, a)
2
p (a, f (a))
1
true така целта G = q (a, Z) е успяваща в програмата P G е изпълнима при P; при това частните случаи q (a, Z)[Z/f (a)] = q (a, f (a)) и q (a, Z)[Z/a] = q (a, a) на q (a, Z) са вярни във всеки модел на P;
получаваме, че дървото на търсенето на целта G при програмата P е безкрайно; целта G = q (Z, a) е успяваща в P G е изпълнима при P; при това частните случаи q (Z, a)[Z/a] = q (a, a) и q (Z, a)/[Z/f (x)][X/a] = q (f (a), a) на q (Z, a) са вярни във всеки модел на програмата P; ясно е, че изобразените две листа на GT са единствените, надписани с true в GT;
така целта G е пропадаща в P; при това, тя е напълно пропадаща, тъй като дървото на търсенето е крайно; ще разгледаме още един пример; нека P = { p (X) :– p (Y), p (a) }; за удобство номерираме клаузите в реда, в който са посочени с 1, 2; нека G = p (X); строим дървото на търсене на хорновата цел G при програмата P, при това използваме само най-общи резолвенти;
така целта G = p (X) е успяваща в P, но тя не е напълно успяваща; при това положение PROLOG не може да разбере дали G е успяваща;
Каталог: fmi fmi -> Софтуерни технологии fmi -> Лекции и семинарни занятия по аналитична геометрия fmi -> 3d-алгоритъм на Chaikin fmi -> Лекции по увод в програмирането fmi -> Лекции и семинарни занятия по линейна алгебра fmi -> Конкурентно Програмиране fmi -> Лекции по компютърни мрежи и комуникации fmi -> Ще предпочетеш да наблюдаваш света отстрани или ще се присъединиш към най-голяма студентска организация? fmi -> Лекции по обектно-ориентирано програмиране Изтегляне 2.18 Mb. Сподели с приятели:
|
