Современные информационные технологии/ 2.Вычислительная техника и
программирование
Пролог
логикалық тілде оралумен іздеуді (поиск с возвратом) деп бэктрекинг
немесе шегіну (откат) немесе немесе тереңдікте іздеу механизмін (механизм
поиска в глубину)
айтады. Бұл
механизмнің мағынасы: бір неше нұсқалар арасында
таңдау мүмкіндік берілсе бағдарлама ның сол жерінде осы позицияға келесі оралу
үшін Пролог арнайы стекке оралу нүктесін сақтайды. Оралу
нүктесі шегіну (откат) процедурасын кайта бастауына қажетті
ақпаратты сақтайды. Ықтимал нұсқалардан біреуі таңдаланады,
одан ары бағдарламаның орындалуы жалғасады.
Альтернативалар
болатын бағдарламаның
әр нүктесінде, стекке көрсеткіштер енгізіледі. Егер таңдаланған нұсқа
сәттілікке кейіннен әкелмесе, онда
альтернативті нұсқалардан біреуі таңдаланған стектің
бағдарлама нүктелерінің
соңғысына шегіну (откат) орындалады. Келесі нұсқа
таңдаланып, бағдарлама өзінің жұмысын
жалғастырады. Егерде нүктенің барлық нұсқалар
қолданған болса, онда бағдарламаның
нәтижесі сәтсіздік деп есептелініп, оралу нүктесі бар болған жағдайда алдынғысына өтуі орындалады. Осы
нүктеден кейін мәндерге ие болған барлық
байланысқан айнымалылар шегінуде (откатта ) қайта бос болады.
Бэктрекинг
мағынасын түсіндірген кезде жиі лабиринтте жолдан іздестірумен
мысалын келтіреді. Лабиренттен шығу табудың ықтимал
әдістерінің біреуі- бұл әр жол айрығында тұғырыққа
тірелгенше тек бір жаққа бұрылу керек.
Тұғырыққа тірелген соң ең жақын жол айрығына оралу керек. Содан кейін
басқа бағыт таңдаланады. Әр жол айрығында осы бағыт бойынша керекті
бұрылысқа бұру керек.
Мысал. Туыстық
қатынастарды сипаттайтын бағдарламаның мысалы ретінде шегіну
(откат) механизмінің жұмысын қарастырайық.
mother ("Алуа","Назира"). /* "Алуа" және
"Назира" «ана» қатынаспен байланысқан*/
mother("Жазира","Алуа"). /* "Жазира" "Алуа"-
ның анасы */mother("Жазира","Айгүл"). /* "Жазира"
және "Айгүл" «ана» қатынаспен байланысқан */
mother("Алуа","Адия").
/* "Алуа" "Адии"- ның
анасы */
grandmother(X,Y):–
/* X Y – тің апасы, егер табылса мұндай Z, */
mother(X,Z),
/* X Z – тің анасы, ал */
mother(Z,Y). /* Z Y – тің анасы */
Сыртқы мақсат
ретінде бағдарламаны іске
қосқан соң, барлық апа мен немерелердің аттары
туралы сұрақ (grandmother(B,V)) қоямыз.
Біздің
сұраңғымызға жауап іздеуде Пролог – жүйенің
жұмыс процесін қадағалау үшін, бағдарламаның
басында директива компилятор trace жазып,
трассировканы іске қосу қажет.
grandmother(B,V) мақсатты екіге бөлеміз: mother(B,Z) және mother(Z,V). Сонымен,
grandmother(B,V) мақсатты орындау үшін екі mother(B,Z) және
mother(Z,V) «ішкі» мақсаттар орындалу
тиіс. Бірінші «ішкі» мақсат «ана болу» қатынасты сипаттайтын
бірінші сөйлеммен бірыңғайлау. В айнымалы- «Алуа», ал Z
айнымалы- "Назира" аттарымен нақтыланады.
mother(Z,V) екінші «ішкі»
мақсат қанағаттандыратын әрекет жасау керек, және
де Z айнымалының мәні
"Назира" – ға тең.
Бұл «ішкі» мақсат
mother предикатқа қатысты фактілердің біреуімен бірыңғайлау
әрекеті сәтсіздікке әкеледі.
Бұл сәтсіздік Назираның
балалары туралы білім қорыда ешқандай мәлімет болмағандықтан
орындалды.Оралу нүктелері сақталынған стектегі орынға
дейін шегіну (откат) орындалады. Бұл
ретте шегіну (откат) мезетте мәндерге ие болған B және Z
айнымалылыр қайта бос болады. Бұл
ретте В
айнымалы - "Жазира", ал Z айнымалы -
"Алуа" аттарға ие болады.
Екінші «ішкі»
мақсат mother(Z,V) (Z = "Алуа"
кезде) үшін шешім іздестіру талпынысы
жасалынады.
mother
предикатты іске асыратын процедураның бірінші сөйлемі ағымды «ішкі»
мақсатпен бірыңғайланады,
V айнымалы Назира" мәнге ие болады.
Нәтижеде
біздің сұрағымызға жауап айнымалылар келесі
мәндерге тең
болған жағдайда: B=Жазира, V=Назира болу мүмкін. Бұл
жауап сұхбат терезеде бейнеленеді, содан кейін оралу нүктелер
стегінде жазылған соңғы орынға шегіну (откат)
орындалады. Және де "Назира"
атқа ие болған V айнымалы
бос болады. mother(Алуа,V) «ішкі»
мақсат mother предикатты
анықтайтын процедураның соңғы сөйлемнің
тақырыбымен бірыңғайланады.
V айнымалы "Адия" атқа ие болады.
B=Жазира, V=Адия. Сұхбат терезеде
сыртқы мақсат ретінде берілген сұраққа: B=Жазира, V=Адия екінші ықтимал жауап шығады.
mother(Алуа,V) «ішкі» мақсат үшін альтернативті
шешім басқа жоқ.
Сәйкесінше, трассировка
терезесінде жұлдызша жоқ, ал оралу нүктелер стегінде grandmother қатынасты
анықтайтын ереженің екінші «ішкі» мақсатының жаңа
мәндерін таңдау үшін оралуға болатын орынның
көрсеткіші енді жоқ.
«Апа болу» қатынасты анықтайтын ереженің
тұлғасында бірінші «ішкі» мақсаттың айнымалылары
мәндерге ие болатын бағдарлама бөлігінің
көрсеткіші алайда оралу нүктелерінің стегінде әлі
қалды.
Айнымалыларды
жөне-жөнекей бос қалдырып, Пролог- жүйе шегінуді
(откатты) орындайды.
Бірінші «ішкі»
мақсат үшінші факт mother("Жазира","Айгүл")
сәйкестелінеді. Білім қорыдағы фактілердің бірімен mother("Айгүл",V) «ішкі» мақсатты салыстырудың
біртіндеп әрекеттер орындалады. Бірақ
бұл әрекеттер сәттілікке әкелмейді, себебі біздің
бағдарламамызда Айгүлдың балалары туралы ақпарат
жоқ.
Бірінші «ішкі»
мақсаттың шешімін таңдауға болатын орынға бағдарламаның орындалу процесі
кезекті соңғы рет оралды.
Шешелерге
қатысты білімдерді сипаттайтын процедураның соңғы
сөйлеммен «ішкі» мақсат бірыңғайланады.
B айнымалы
"Алуа", ал Z айнымалы -
"Cаша" аттарға ие болады. Бірінші «ішкі» мақсатты
салыстыруға басқа нұсқалар қалмады. Оралу нүктелер стегі бос. Трассировка
терезесінде оралуға болатын альтернативті шешімдер туралы хабар беретін
индикатор жоқ. Пролог - жүйе mother("Адия",V) екінші «ішкі»
мақсатты бір нәрсемен салыстыруға әрекет жасап
көреді, бірақ оны істей алмайды. "Адия" аты бірінші аргумент ретінде бірде- бір фактте жоқ.
Келесі талап - Алуаның немелерін анықтау сәттілікке
әкелмеді.
Бағдарлама
аяқталды. Сұхбат терезеде жұмыс істеу нәтижесі
шығады- табылған екі шешім:
B= Жазира, V=Назира
B=Жазира,V=Адия
2 Solutions
ПАЙДАЛАНҒАН ӘДЕБИЕТТЕР
1.
Хоггер К. “Введение в логическое
программирование”.
2.
Братко И. Программирование на языке Пролог для искусственного интеллекта.
–М.: Мир, 2009.
3.
Агафонов В.Н., Борщев В.Б., Воронков А.А. Логическое программирование в
широком смысле. Пер. с англ. и фр.-М.: Мир, 2005.