Пример 1. Нека P и Q са програмата и целта, разгледани съответно в пример 1 и в пример 4 от предходния въпрос. Схемата, изобразена във втория от тези два примера. може да се разглежда като дърво на търсене за Q при P, ако приемем за върхове и за ребра на дървото съответно големите и малките правоъгълници с уславянето, че начало и край на едно ребро са съответно правоъгълникът непосредствено над него и правоъгълникът непосредствено под него, и счетем, че всеки от правоъгълниците е маркиран с това, което е записано в него.

    Дървото на търсене от горния пример е с краен брой върхове. Сега ще посочим и пример за дърво на търсене с безбройно много върхове.

    Пример 2. Да разгледаме програмата P₁ от пример 5 от предходния въпрос. Нека Q е целта [p(X,X)], разгледана там. Да разгледаме едно дърво T с безбройно много върхове, всеки от които е маркиран с целта Q, и други безбройно много върхове, всеки от които е маркиран с целта [q(X,X)]. Нека всеки от върховете от първия вид да бъде начало на точно две ребра, едното маркирано с числото 9 и имащо за край връх от втория вид, а другото маркирано с числото 10 и имащо за край връх пак от първия вид. Нека никой връх от втория вид не е начало на ребро. Лесно се проверява, че T е дърво на търсене за Q при P₁. Една крайна част от T е изобразена на схемата по-долу, като са приети уславяния както в горния пример (с многоточие е загатната останалата безкрайна част).
 

    За всяка хорнова програма P и всяка хорнова цел Q съществува дърво на търсене за Q при P. Такова дърво може да бъде построено като обединение на една растяща крайна или безкрайна редица от последователно построени крайни дървета, всяко от които удовлетворява условията а) и б) от дефиницията за дърво на търсене за Q при P, а също условието, получено като в условието в) от същата дефиниция думата "точно" се замени с "най-много" (това, че редицата е растяща, в случая означава, че всеки неин член след началния се получава от предходния си чрез добавяне на нови ребра и върхове). За начален член на тази редица може да се вземе дърво с един единствен връх, маркиран с Q. След като даден член на редицата е построен, ако условието в) от споменатата дефиниция се окаже нарушено за него, то строим следващ член на редицата, като към построеното дърво добавим най-малкия възможен брой маркирани както е нужно нови ребра и върхове, с който да можем отстраним наличните нарушения на условието в), евентуално с цената на възникване на нови негови нарушения (за някои от новите върхове).

    Пример 3. На схемата по-долу са изобразени първите три члена от редицата от крайни дървета, съответстваща на безкрайното дърво от пример 2.
 

    Нека са дадени една хорнова програма P, състояща се от n клаузи, и една хорнова цел Q. Може и директно да се опише математически обект, който е дърво на търсене за Q при P. За да дадем такова описание, първо се уславяме да казваме, че една крайна редица (i₁,...,i_m) от положителни цели числа, никое от които не надминава n, води при P от Q до дадена хорнова цел G, ако съществува такава редица от хорнови цели (G₀,G₁,...,G_m), че да имаме равенствата G₀=Q, G_m=G и за всяко цяло число k, удовлетворяващо неравенствата 0Јk<m, целта G_k+1 да бъде канонична резолвента на G_k с i_k-тата клауза на P (допуска се да имаме d=0 и тогава условието се свежда до равенството Q=G).

    Пример 4. В условията на пример 2 редицата (10,10,9) води от целта [p(X,X)] до целта [q(X,X)] - това се вижда, като се разгледа редицата от цели

    Да наречем допустима за Q при P всяка крайна редица от положителни цели числа, ненадминаващи n, която води при P от Q до някоя цел. Нека T е дърво, построено по следния начин: върхове на T са всички допустими за Q при P крайни редици от положителни числа, ненадминаващи n, ребра на T са непразните измежду току-що споменатите редици, начало на всяко ребро е върхът, получен чрез премахване на последния член на реброто, край на всяко ребро е върхът, с който то съвпада, всеки връх на T е маркиран с цел, до която той води при P от G, а всяко ребро е маркирано с последния си член. Лесно се проверява, че така дефинираното дърво T удовлетворява изискванията а), б) и в) от дефиницията за дърво на търсене. Ще го наричаме стандартно дърво на търсене за Q при P.

    Пример 5. В условията на пример 2 върхове на дефинираното по-горе дърво ще бъдат празната редица, всички непразни крайни редици, съставени от десетки, и всички непразни крайни редици, съставени от известен (евентуално нулев) брой десетки и една деветка след тях. Върховете, завършващи с 9, ще бъдат маркирани с целта [q(X,X)], а всички останали - с целта [p(X,X)].

    Забележка 1. Изложената преди малко конструкция на дърво има особеността, че множеството на ребрата на дървото се съдържа в множеството на върховете му. В случай, че искаме тези две множества да нямат общи елементи, би могло да изменим малко конструкцията, взимайки вместо множеството на допустимите редици и множеството на непразните допустими редици подходящи други две множества, намиращи се във взаимно еднозначно съответствие с тях.

    Дървото на търсене за една цел при една програма не е eдинствено - поне заради това, че имаме свободата за върхове и за ребра на дървото да избираме каквито искаме обекти. Друга причина за неединственост може да бъде неединствеността на каноничната резолвента в по-често срещаните случаи. Лесно се вижда обаче, че различните дървета на търсене за дадена цел при дадена програма в определен смисъл не се различават съществено едно от друго. И наистина, ако T е произволно дърво на търсене за дадена цел Q при дадена програма P, да наречем адрес на кой да е от върховете на T редицата от числата, с които са маркирани последователните ребра по пътя, водещ от корена на T до дадения връх. Тогава лесно се вижда, че адреси на върхове на T са точно допустимите за Q при P редици от числа и че различните върхове на T имат различни адреси. Това позволява да се установи взаимно еднозначно съответствие между върховете на T и върховете на избрано от нас стандартно дърво на търсене за Q при P. Използвайки взаимно еднозначното съответствие между ребрата на T и върховете на T, различни от корена му, веднага установяваме и взаимно еднозначно съответствие между ребрата на T и ребрата на стандартното дърво на търсене. Проверява се, че двете съответствия - между върховете и между ребрата определят един изоморфизъм между двете дървета. При това лесно се вижда, че маркировките на съответните едно на друго ребра съвпадат. Колкото до маркировките на съответните един на друг върхове, съвпадане не винаги е налице, но тези маркировки винаги са варианти една на друга. Това е така благодарение на известните ни връзки между канонични резолвенти и варианти на цели (вж. следствие 3 от въпроса "Пълнота на резолюцията между хорнови цели и хорнови клаузи").

    Да предположим, че T е дърво на търсене за дадена хорнова цел Q при дадена хорнова програма P. Ако разгледаме произволен път в T, започващ от корена на T, то редицата от целите, с които са маркирани последователните върхове по този път, ще бъде основана на P канонична резолвентна верига с начален член Q. Обратно, всяка основана на P канонична резолвентна верига с начален член Q би могла да бъде получена от някоя такава редица с евентуално заменяне на нейни членове с техни варианти. В този смисъл дървото T дава информация за всички основани на P канонични резолвентни вериги с начален член Q (всъщност то дава за всяка такава верига и допълнителна информация чрез какви конкретни канонични резолюции с клаузи на P може да бъде получена въпросната верига).

    Като вземем пред вид връзката между изпълнимост на дадена цел при P и канонична резолвентна достижимост на празната цел от дадената при P (следствие 4 от въпроса "Пълнота на резолюцията между хорнови цели и хорнови клаузи"), заключаваме, че целта Q е изпълнима при P точно тогава, когато дървото T има поне един връх, маркиран с празната цел (значи изследването дали Q е изпълнима при P може да се извърши като се изследва дали T има такъв връх).

    Пропадането на Q при P също може да се охарактеризира просто с помощта на T. А именно, за да бъде целта Q пропадаща при P, необходимо и достатъчно е дървото T да бъде с краен брой върхове и никой от тях да не е маркиран с празната цел. Това следва лесно от характеризационната теорема за пропадащите цели. Според нея целта Q е пропадаща при P точно тогава, когато съществува горна граница за дължините на основаните на P крайни канонични резолвентни вериги, на които Q е начален член, и никоя от споменатите вериги не завършва с празната цел. Второто от тези условия очевидно е еквивалентно с изискването никой от върховете на T да не е маркиран с празната цел. Остава да покажем, че първото от условията е еквивалентно пък с изискването броят на върховете на T да е краен. Да предположим най-напред, че споменатото първо условие е изпълнено. Тогава ще съществува горна граница за дължините на пътищата в T, започващи от корена на T, а последното гарантира, че броят на върховете на T е краен (той не може да надминава сумата 1+n+n²+...+n^d, където n е броят на клаузите в P, а d е горна граница за броя на ребрата в кой да е от споменатите пътища). Обратно, ако броят на върховете на T е краен, то такъв ще е и броят на пътищата в T, започващи от корена на T, следователно, ще има горна граница за техните дължини, а значи и за дължините на основаните на P крайни канонични резолвентни вериги, на които Q е начален член.

    Както споменахме преди малко, можем да изследваме дали целта Q е изпълнима при P като изследваме дали дървото на търсене T има връх, маркиран с празната цел. Когато дървото T е с краен брой върхове, няма принципни пречки (освен евентуалния голям обем на работата) за това да извършим такова изследване докрай и да проверим дали има или няма такъв връх. Доста по-сложно е положението, когато T има безбройно много върхове. Ако някой от тях е маркиран с празната цел, отново няма други принципни пречки освен евентуалния голям обем на работата за това да намерим такъв връх - ако самата цел Q не е празна, търсенето му би могло да стане например като се започне с преглеждане на върховете на T, имащи едночленни адреси, след това, ако все още въпросният връх не е намерен, да се продължи с върховете на T, имащи двучленни адреси, и т.н. (такъв начин на търсене обикновено се нарича търсене в широчина). Ако обаче никой от безбройно многото върхове на T не е маркиран с празната цел, търсенето по този начин ще продължи безкрайно без някога да стигнем до резултат. По-задълбочени изследвания показват, че в някои случаи има непреодолими принципни пречки за изчерпателното решаване на въпроса и чрез какъвто и да е друг алгоритъм.

    Всъщност търсенето в широчина, за което стана дума преди малко, обикновено се избягва и в случаите, когато би дало резултат. Това се прави заради често прекалено големия обем на работата при такова търсене. При изпълнението на програми на Пролог вместо това се извършва тъй нареченото търсене в дълбочина с евентуален възврат. При този друг начин на търсене далеч не винаги при съществуването на връх, маркиран с празната цел, намирането на такъв връх е гарантирано, дори и ако не обръщаме внимание на обема на работата. Причината въпреки това да се предпочете търсенето в дълбочина с евентуален възврат е в това, че не са малко случаите, когато все пак това търсене е успешно и резултатът се получава при приемлив обем на работата.

    Ще дадем накратко математическо описание на търсенето в дълбочина с евентуален възврат. Можем да считаме, че всъщност при него върхове на T се преглеждат последователно при тъй наречената лексикографска подредба на техните адреси. За два адреса (i₁,...,i_m) и (j₁,...,j_l) ще казваме, че първият предхожда лексикографски втория или че вторият следва лексикографски първия, ако е налице някой от следните два случая: а) m<l и имаме равенствата i₁=j₁, ...,i_m=j_m; б) съществува положително цяло число k, ненадминаващо както m, така и l, за което i_k е различно от j_k, и за най-малкото такова k е изпълнено неравенството i_k< j_k (за празния адрес се счита, че предхожда лексикографски всеки друг, като е налице първият от двата случая). От гледна точка на съответните на адресите пътища в дървото T случаят а) е налице, когато пътят, съответен на първия адрес, е същинско начало на пътя, съответен на втория, а случаят б) е налице, когато след някаква обща начална част на двата пътя (евентуално празна) вторият се отклонява по-надясно от първия (като думата "по-надясно" се разбира от наша гледна точка, а не от гледната точка на някакво въображаемо същество, движещо се по пътя; освен това предполагаме, че, както в примерите в началото, от две ребра с общо начало онова, което е маркирано с по-голямо число, винаги е изобразено по-надясно от другото). За означаване на лексикографското предхождане ще използваме обикновения знак за неравенство. Лесно се проверява, че лексикографската подредба на адресите е транзитивна и че от всеки два различни адреса единият предхожда лексикографски другия.

    Пример 6. В условията на пример 1 имаме освен празния адрес още 19 други и те се подреждат по следния начин:  (1) < (2) < (2,1) <(3) < (3,6) < (3,6,4) < (3,7) < (4) < (4,3) < (4,3,6) < (4,3,7) < (5) < (6) < (6,4) < (6,4,3) < (7) < (8) < (8,4) < (8,4,3).

    Пример 7. В условията на пример 2 имаме

    За един адрес ще казваме, че е последен, ако той не предхожда лексикографски никой друг адрес (пример 6 показва, че в условията на пример 1 е последен адресът (8,4,3), а пример 7 показва, че в условията на пример 2 няма последен адрес). Може да се докаже, че когато един адрес не е последен, винаги сред онези адреси, които го следват лексикографски, има един пръв, т.е. такъв, който предхожда лексикографски всички останали измежду тях (той се получава от дадения адрес или чрез добавяне на още един число накрая, което трябва да се избере възможно най-малко, или, ако не съществува адрес, който е продължение на дадения, чрез замяна на последното число в някое начало на дадения адрес с по-голямо число, като началото трябва да се избере възможно най-дълго и след това числото, с което заменяме - с възможно най-малко).

    Забележка 2. Твърдението за съществуване на пръв сред адресите, следващи лексикографски даден адрес, който не е последен, не допуска обобщението, че във всяко непразно множество от адреси има пръв. Ще дадем пример, който показва това.

    Пример 8. Да разгледаме следната програма, където a е нулместен функционален символ, f е едноместен функционален символ и p е едноместен предикатен символ:

p(f(X)) :- p(X).	% 1
p(a).	% 2

Да разгледаме и целта
       ?- p(X).
Едно безкрайно дърво на търсене за тази цел при дадената програма е изобразено по-долу чрез подходяща своя крайна част, като са възприети уславянията от пример 1 и пример 2 и освен това празните правоъгълници се считат маркирани с празната цел.
 

Вижда се, че адресите на върховете, различни от корена, са непразните редици, съставени само от единици, и непразните редици, съставени от известен (евентуално нулев) брой единици и една двойка накрая. Множеството на адресите от втория вид (завършващите с двойка) не е празно, но в него няма пръв елемент относно лексикографската подредба поради това, че никой адрес от този вид не предхожда по-дългите от него адреси от същия вид.

    Казахме, че при търсенето в дълбочина с евентуален възврат върховете на дървото на търсене се преглеждат при лексикографската подредба на техните адреси. Това означава, че се започва с върха с празен адрес, т.е. с корена на дървото, след това се разглежда върхът, чийто адрес е първият от останалите адреси, след това онзи връх, чийто адрес е първият измежду лексикографски следващите адреси, и т.н. Във връзка с това се уславяме да казваме, че един връх на дървото на търсене предхожда друг, ако адресът на първия предхожда лексикографски адреса на втория.

    Пример 9. В условията на пример 8 след корена на дървото ще се разгледа върхът с адрес (1), след това върхът с адрес (1,1), след него върхът с адрес (1,1,1) и т.н. Ясно е, че при това преглеждане на върховете никога няма да се стигне до връх, чийто адрес завършва с 2, въпреки че такива върхове има даже безбройно много. Причината фактически е в това, че всеки такъв връх се предхожда от безбройно многото върхове, чиито адреси не съдържат 2.

    За един връх на дървото на търсене ще казваме, че е достижим при търсенето в дълбочина с евентуален възврат (или по-кратко, че е достижим), ако този връх се предхожда от най-много краен брой други върхове на дървото. Горният пример показва, че понякога може да са налице върхове, които не са достижими. Особено неприятно е, че освен това може някой от тези недостижими върхове да е маркиран с празната цел, а измежду достижимите никой да не е маркиран с нея (точно такова е положението в разглеждания пример). В такъв случай се оказва, че макар целта, на която съответства дървото, да е изпълнима при разглежданата програма, това не може да се установи при възприетия алгоритъм на търсене. В по-благоприятния случай, когато в дървото на търсене има достижим връх, маркиран с празната цел, ще казваме, че разглежданата цел е успяваща при дадената програма. Разбира се всяка хорнова цел, успяваща при дадена хорнова програма, е изпълнима при нея, но обратното, както се вижда от пример 9, не е вярно (противоречащ пример е целта от пример 8 при програмата от същия пример - целта е изпълнима при въпросната програма, но не е успяваща при нея). При използването на Пролог не всички изпълними цели водят до отговор "Yes", а само успяващите (по-точно онези от тях, при които не възникват допълнителни пречки поради голям обем на работата). Например при изпълнение на програмата от пример 8 върху целта от този пример Strawberry Prolog процесът завършва безрезултатно със съобщение за препълване на стека.

    Може да се покаже, че дадената по-горе дефиниция за хорнова цел, успяваща при дадена хорнова програма, е еквивалентна на следната индуктивна дефиниция:
    1. Празната цел е успяваща.
    2. Ако дадена цел и дадена клауза от програмата имат успяваща канонична резолвента, а всички резолвенти на дадената цел с предхождащи клаузи от програмата са пропадащи, то и тази цел е успяваща.

    Пример 10. Нека P е програмата от пример 3 от въпроса "Хорнови цели, хорнови клаузи, хорнови програми" и нека Q е разгледаната там цел
        ?- q(X,Y), q(Y,Z), q(Z,X).
(същата програма, но във връзка с прилагането й към други цели, беше разгледана и в пример 1 от предходния въпрос). По-долу е изобразена такава част от дърво на търсене за Q при P, че само въз основа на тази част вече се вижда, че Q е успяваща при P (с многоточия са загатнати неизобразените части на дървото). А именно, вижда се, че върхът с адрес (3,6,4) е маркиран с празната цел и този връх се предхожда само от краен брой върхове - от корена на дървото и от върховете с адреси (1), (2),(2,1), (3), (3,6) (това, че споменатият връх се предхожда само от краен брой върхове, можеше да се предвиди и без те да се намират, като се вземе пред вид, че дървото на търсене в случая е с краен брой върхове, тъй като при тази цел и програма не са възможни резолвентни вериги с повече от четири члена).
 

Сега ще покажем как обстоятелството, че целта Q е успяваща при P, може да се установи и въз основа на индуктивната дефиниция. Въпросната цел има с първата от клаузите на P канонична резолвента [q(a50,Z),q(Z,a26)] и тя е директно пропадаща при P. С втората от клаузите на P целта Q има канонична резолвента [q(a26,Z),q(Z,a26v)] и тя също е пропадаща при P, макар и не директно (единствената й канонична резолвента с клауза на P е [q(a50,a26v)], която цел е директно пропадаща при P). Това показва, че са пропадащи при P всички канонични резолвенти на Q с клаузи на P преди третата. С третата от клаузите на P целта Q има канонична резолвента [q(a78,Z),q(Z,a46)]. От своя страна тя няма резолвента с никоя от първите пет клаузи на P, а с шестата има канонична резолвента [q(a47,a46)]. Тя пък няма резолвента с никоя от първите три клаузи на P, а с четвъртата има празна канонична резолвента. По т. 1 от индуктивната дефиниция по-горе получаваме, че празната цел е успяваща при P, оттук по т. 2 от дефиницията получаваме, че целта [q(a47,a46)] също е успяваща. Използвайки още два пъти т. 2 от дефиницията, последователно получаваме, че са успяващи целта [q(a78,Z),q(Z,a46)] и първоначалната цел.

    Понеже при дефиницията на понятието успяваща цел играе роля подредбата на клаузите в програмата, не е чудно, че една и съща цел може да се окаже успяваща при една подредба на клаузите и неуспяваща при друга.

    Пример 11. Да разменим реда на двете клаузи в програмата от пример 8, т.е. да разгледаме програмата

p(a).	% 1
p(f(X)) :- p(X).	% 2

Неуспяващата по-рано цел
       ?- p(X).
след тази промяна в реда на клаузите става успяваща, защото тя има празна канонична резолвента с първата клауза на новата програма. За тази цел и новата програма можем да получим дърво на търсене от онова, което имахме в пример 8, като разменим числата 1 и 2 в маркировката на ребрата; при изобразяването на дървото би следвало да се погрижим още за разполагане на реброто, маркирано с 1, по-наляво от реброто, маркирано с 2, когато тези две ребра имат общо начало. Ако постъпим така, получаваме следното дърво:
 

В него всеки връх е достижим. В частност достижими са безбройно многото върхове, маркирани с празната цел. При изпълнението на програмата върху целта с помощта на Пролог това дава своето отражение чрез възможността последователно да бъдат намирани безбройно многото субституции, преобразуващи целта в нейни частни случаи, тъждествено изпълнени при програмата:

Последно изменение: 22.05.2001 г.
 

Previous  Next  Contents