№1 Зертханалыќ ж±мыс



жүктеу 208 Kb.
бет8/17
Дата20.01.2022
өлшемі208 Kb.
#33755
түріПрограмма
1   ...   4   5   6   7   8   9   10   11   ...   17
ЖИ зертханалык жумыс

Тапсырма:

  1. Рекурсия мехнизімінің жұмысын талдау

  2. Тұрақты сандар арқылы рекурсия механизмін жүргізу

  3. cdr функциясына тізбек құру

4, 5 Зертханалық жұмыс



Концептуализация

Пролог тіліндегі рекурсивті іздеу. Жоғарыда қарастырылған «Атпен жүру» мысалында предикаттар теориясындағы бейнеленуін келтірейік. Ат жүрісін өлшемі 3х3 болатын келесі тақтада бейнелейміз.

1

2

3

4

5

6

7

8

9

Пролог тіліндегі мүмкін болатын ат жүрісін move – предикаты көмегімен жазуға болады. path -предикаты аргументтер арасындағы 0-ден көп жүрістер санын белгілейтін жол санын анықтайтын алгоритмдерді білдіреді. path предикаты рекурсивті түрде анықталған.

move(1, 6) . move(3, 4) .move(6, 7) .move(8, 3)

move(1, 8) . move(3, 8) .move(6, 1) .move(8, 1)

move(2, 7) . move(4, 3) .move(7, б) .move(9, 4)

move(2, 9) . move(4, 9) .move(7, 2) .move(9, 2)

path(Z, Z).

path(Х, Y) : — move(Х, W), not(been(W)), assert(been(W)), path(W, Y)

Соңғы белгіленген path предикатының анықтамасы оның пролог тіліндегі іске асуы. Жоғарыда келтірілген assert — пролог тіліндегі ішкі предикат, ол өз аргументтерін спецификациялар дерек қорына орналастырады және үнемі "шын" деген мәнге ие. Been –предикаты бұрынғы болған алдыңғы күйлерді жазуға және циклдерді болдырмауға пайдаланылады.

been предикатын бұлай пайдалану глобалды айнымалыларды қолданбай предикаттар логикасында спецификациялар жасау жөніндегі программа құру мақсатына қайшы келеді. Мысалы been (3 ) деректер қорына қосқан соң, ол глобалды мағынаға ие факт бола алады. Бұл фактіні осы деректер қорына кез келеген процедура қолдана алады.

Программаны басқаруда глобалды құрылымдар жасау продукциял лық жүйелерде есеп логикасы (есеп спецификациясы) программа басқарудан бөлек сақтанады. ық жүйелерді үлгілейтін негізгі принципіне қайшы келеді. Подукция жоғарыдағы мысалда been құрылымы программа орындалуын модификациялауға арналған глобальды специфика ретінде құрылған.

path – предикатын шақырғанда жүріп өткен күйлерді есепке алу үшін және циклдарды болдырмау үшін тізімді пайдалануға болады. Ұқсас күйлерді (циклдарды ) анықтау үшін member предикатын пайдалануға болады. Бұндай тәсіл been (W) – глобалды тұжырымын қолдану проблемасын айналып өтуге мүмкіндік береді.

Пролог тіліндегі тереңнен іздеу әдісінің қайталау алгоритмі көмегімен шешімі былайша іске асады:

а1Ь(Е Z, L) .

а~1«(Х, У, Ь): — move (Х, Е), not (member (Z, Ь) ), path(Z, Y, [Z ~ Ь] )

Мұндағы member — жоғарыда анықталған предикат.

path — предикатының үшінші аргументі жүріп өткен күйлерден тұратын тізімді көрсететін локалды айнымалы . Жаңа күй генерацияланғанда (move предикатын пайдалана отырып ол [Z ( Ь] – күйлер тізімінің басында болады да қайтадан path – шақырады. Бұл шақыру егер осы уақытқа дейін айнымалы жүріп өткен күйлер тізімінде болмаса, not (member (Z, Ь) ) path – предикатының барлық параметрлері локалды болады және олардың ағымдағы мәні іздеу графын шақыру орнына тәуелді. Әр рекурсивтік шақыруда бұл тізімге жаңа күй қосылады. Егер берілген күйдің туындылары сәтсіз болса, path шақыруы да сәтсіз болады. Егер интерпретатор аталық шақыруға қайтса, онда жүріп өткен күйлерден тұратын тізімді беретін үшінші параметр өзінің алдыңғы мәнін қабылдайды.

Осылайша, графтағы қайталап іздеу процесінде күйлер тізімге қосылып және өшіріліп отырады.

path – шақыруы сәтті аяқталғанда, алғашқы екі параметр бірден мән қабылдайды. Үшінші параметр - шешім жолындағы жүріп өткен күйлерден тұратын тізім. Бұл жолда аталған күйлер кері тәртіпте беріледі. Осылайша шешім табудың барлық кезеңдерін басып шығаруға болады. Сонымен тізімдерді және графтағы қайталап іздеу көмегімен «Ат жүрісі»есебіне арналған Пролог спецификациясын path және move,member предикаттарын пайдаланып құруға болады. .

рath(X, Y, [Х] ) командасын Пролог интерпретаторымен шақыру, мұндағы Х және Y — 1-ден 9 саны аралығындағысандар. Х күйінен У –күйіне көшетін жолды табуға мүмкіндік береді. Егер әрине мұндай жол болса. Үшінші параметр Х алғашқы күйінің жүріп өткен күйлерден тұратын тізімін инициализациялайды. Пролог тілінде таңбалар регистрі есепке алынбайды. Алғашқы екі параметр есептің анықталу аумағындағы кез-келгенкүйлерді бейнелейді, ал үшінші параметр –күйлер тізімін көрсетеді. Унификация көмегімен барлық мүмкін болатын деректер типтерінің шаблондарға сәйкестігінің жалпылама тексерілуі оырндалады.

Осылайша рath –кез келген графқа қолдануға болатын тереңнене іздеудің жалпылама алгоритмі.

ЗХЗ – тақтасында берілген "ат жүрісі"есебіне қайтадан оралайық. Осы мысалдың Зх8 тақтасына арналаған түрінің РROLOG тіліндегі шешімін қарастырайық. Ол үшін path – алгоритмінің екі жағын нөмірлейік.

1. is path(Е, Е, ь) .

2. is path(X, Y, Ь): — move(Х, Z), not(member(Z, Ь) ), path(Z, Y, [Е (Ь] )

?- path(1, 3, [1] ) .

Мысалдың трассировкасы мынадай болады.

path(1, 3, [1] ) attempts to match 1. fail 1 Ф 3.

path(1, 3, [1] ) matches 2. Х is 1, Y is 3, L is [1]

move(1, Е) matches Z as б, not(member(6, [1] ) ) is true,

call path(6, 3, [6,1] )

path(6, 3, [6,1]) attempts to match 1. fail б ~ 3.

path(6, 3, [6,1]) matches 2. Х is б, Y is 3, ? is [6,1].

move(6,Е) matches Z as 7, not(member(7,[6, 1])) is true,

path(7, 3, [7, б, 1] )

path(7,3,[7,6,1]) attempts to match 1. fail 7 Ф 3.

path(7,3,[7,6,1]) matches 2. Х is 7, Y is 3, L is [7,6,1].

move(7,Z) is Е=б, not(member(6,[7,6, 1])) fails, backtrack!

move(7,Z) is Z=2, not(member(2,[7,б,1])) true,

path(23,[2,7,б,1])

path call attempts 1, fail, 2 Ф 3.

path matches 2, Х is 2, Y is 3, ? is [2,7,6,1]

move matches Z as 7, not(member(...)) fails, backtrack!

move matches Z as 9, not(member(...)) true,

path(9,3,[9,2,7,б,1])

path fails 1, 9 Ф 3.

path matches 2, Х is 9, Y is 3, L is [9,2,7,6,1]

move is Z = 4, not(member(...)) true,

path(4, 3,[4,9,2,7,6,1])

path fails 1, 4 Ф 3.

path matches 2, Х is 4, Y is 3, ? is [4,9,2,7,6,1]

move Z = 3, not(member( )) true,

path(3 3,[3,4,9,2,7,6,1])

path attempts 1, true, 3 = 3, yes

yes

yes


yes

yes


yes

yes


Қорытындылай келе, мынаны атап өтелік. рath — рекурсивттік шақыруы графтағы іздеуге арналған жалпы басқару құрылымы немесе қабықша (shell). path (X, Y, L) Х — ағымдағы күйі, Y — мақсатты күйі. Егер Х және Y дәл келсе, рекурсия тоқталады. L —Х баратын ағымдағы жол бойындағы күйлер тізімі. Z – жаңа күйі табылғанда move (Х, Z) шақыруы көмегімен, бұл күй [Z ~ L]тізіміне орналасады. Тізімдегі күйдің бар болуы not (member (Z, L)) шақыруы арқылы тексеріледі. Бұл тексеру табылған жолда циклдер болмауына кепілдік береді. Жоғарыда аталған жолды іздеу алгоритміндегі күйлердің L – тізімі мен с/osed/ тұйық жиынының арасындағыайырмашылық мынадай: жиын барлық жүріп өткен күйлерді қамтиды, ал L – тізімінде тек ағымдағы жол болады. Айырмашылықта жоюүшін path – шақыруы кезіндегі жазбаны кеңейтіп, онда барлық жүріп өткен күйлерді сақтау керек.

жүктеу 208 Kb.

Достарыңызбен бөлісу:
1   ...   4   5   6   7   8   9   10   11   ...   17




©g.engime.org 2024
әкімшілігінің қараңыз

    Басты бет
рсетілетін қызмет
халықаралық қаржы
Астана халықаралық
қызмет регламенті
бекіту туралы
туралы ережені
орталығы туралы
субсидиялау мемлекеттік
кеңес туралы
ніндегі кеңес
орталығын басқару
қаржы орталығын
қаржы орталығы
құрамын бекіту
неркәсіптік кешен
міндетті құпия
болуына ерікті
тексерілу мемлекеттік
медициналық тексерілу
құпия медициналық
ерікті анонимді
Бастауыш тәлім
қатысуға жолдамалар
қызметшілері арасындағы
академиялық демалыс
алушыларға академиялық
білім алушыларға
ұйымдарында білім
туралы хабарландыру
конкурс туралы
мемлекеттік қызметшілері
мемлекеттік әкімшілік
органдардың мемлекеттік
мемлекеттік органдардың
барлық мемлекеттік
арналған барлық
орналасуға арналған
лауазымына орналасуға
әкімшілік лауазымына
инфекцияның болуына
жәрдемдесудің белсенді
шараларына қатысуға
саласындағы дайындаушы
ленген қосылған
шегінде бюджетке
салығы шегінде
есептелген қосылған
ұйымдарға есептелген
дайындаушы ұйымдарға
кешен саласындағы
сомасын субсидиялау