Ойындық тармақтар

Эвристикалық іздеу алгоритмдері. Қарастырылған шешімді іздеу мысалдарда жағдайлар саны көп емес, сондықтан барлық жағдайларды қарастыру қиындық тудырғпн жоқ. Алайда, жағдайлардың едауір санында іздеу уақыты экспоненциалды өседі, бұл жағдайда дұрыс шешім таңдаудың жоғары ықтималдығы бар эвристикалық іздеу алгоритмдері көмектесе алады. Осы алгоритмдердің кейбіреулерін қарастырайық.

1. Шешім ағашы бойынша жылдам түсу алгоритмі. Тар ағашты құру мысалын коммивояжер туралы тапсырма мысалында қарастырамыз. Сатушы картада (сур.19 а) көрсетілген бес қаланың әр біреуінде болуы керек.

Тапсырма А қаладан бастап барлық басқа қалалардан бір-ақ рет өтетін және А қаласына қайта келетін минималды жолды табудан тұрады. Тәсілдің ойы қарапайым – әр қаладан біз әлі болмаған жақынына барамыз. Тапсырманың шешімі 19 б суретінде көрсетілген.

Мұндай шешімді іздеу алгоритмі жылдам түсу алгоритмі атына ие болды (кей жағдайларда – жылдам көтерілу).

2. Бағалау (айыппұл) функциялар алготитмі. Шебер таңдалған функциялар (кей әдебиеттерде – айыппұл функциялар) қиын тапсырмаларды толық қарастыруды едәуір қысқартып және шешімге тез арада жеткізе алады. Біздің людоед және миссионер туралы тапсырмамызда келесі жағдайды таңдау кезінде ең қарапайым мақсат функциясы ретінде мақсаттық жағдайда олардың орналасуын сипаттаумен салыстыру бойынша «орында емес» людоедтер мен миссионерлер санын алуға болады. Мысалы, мына  функцияның мәні шығу жағдайы үшін , ал мақсаттық жағдай үшін .

Сурет 19а                                                    Сурет 19 б

 

Графта іздеудің эвристикалық процедуралары мақсатқа жету жолының құны мен іздеу құнының кейбір комбинациясын минималдауға ұмтылады. Людоед туралы тапсырма үшін бағалау функциясын енгіземіз:

,

мұндағы - іздеу ағашындағы төбесінің тереңдігі және - керек емес орындағы миссионерлер мен людоедтер саны. Эвристика минималды мән таңдауда аяқталады. Эвристикалық процедураларда анықтаушы болып бағалау функциясын таңдау табылады.

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

Кесте1

2	8	3		1	2	3
1	6	4	→	8	*	4
7	*	5		7	6	5

 

Екі бағалау функциясын қарстырайық:

мұндағы - орнында емес текшелер саны; - оның мақсаттық төбедегі орнынан әр текше қашықтығының қосындысы; - орталық текшелер тізбегінің есебі (дұрыс тізбекте текше тұрмаса, онда айыппұл+2 болады; ортадағы текшеге айыппұл+1; басқа жағдайда айыппұл 0).

Осы бағалау функциялары кесте 2 көрсетілген.

 

Кесте 2. Бағалау функцияларын салыстыру

Бағалау функциясы h	Жол құны (ұзындығы) L	Жолды табуда ашылған төбелер саны N	Есептеу үшін керек есептеудің көп еңбекті қажет етуі h S	Ескерту
	5 >18	13 100-8!(=40320)	8	Көлденең бойынша іздеу
	5 18	11 43	8*2+8+1+1	Тереңдік бойынша іздеу

Осы екі бағалау функцияларды салыстыру негізінде қорытындылар жасауға болады.

· Іздеу алгоритмімің негізін минималды бағалау функциясы бар жолды таңдау құрады.

· h ₁ функциясы беретін көлденеңнен іздеу мақсататқа жетер қандай да бір жол табылатындығына кепілдік береді. Көлденеңнен іздеу кезінде төбелер өздері туған реттен ашылады.

· Тереңнен іздеу h ₂ функциясындағы 3 S (n) эвристикалық компонентасымен басқарылады және бағалау функциясы сәтті таңдалған кезде шешімді төте жолмен табуға мүмкіндік береді (ашылатын төбелердің минималды саны бойынша). Тереңнен іздеу соңғы құрылған төбенің бірінші болып ашылатындығымен сипатталады.

· Егер іздеу тиімділігі кішігірім тереңдіктерде негізінен эвристикалық компонент тереңіне бағытталса, ол жоғарлайды, ал тереңдіктің өсуі кезінде ол мақсатқа жетудің қандай да бір жолы бар екендігіне кепілдік беру үшін көлденеңнен іздеуге көбірек ұқсайды. Іздеудің тиімділігін сияқты анықтауға болады, мұндағы K және S (көп еңбекті қажет ету) – бағалау функциясына тәуелді, L – жолдың ұзындығы, N – жолды табу кезінде ашылған төбелер саны. Егер тиімді жолы үшін деп келіссек, онда .

 

Минимакс алгоритмі.

 

Сурет 20. Минимакс алгоритмі

Минимакс әдісін дамыта отыра, миссионерлер мен людоедтер туралы тапсырмадағы орындалатын әрекеттер үшін ықтималдықтарды белгілейік:

   

Екі адамнан гөрі бір людоедті немесе бір миссионерді жіберу, әсіресе бастапқы кезеңдерде, тиімдірек екендігі интуитивті түсінікті. Біз әр деңгейде жағдайды max P_i критериі бойынша таңдайтын боламыз. Тіпті осындай қарапайым тәсіл іздеу процесінде тұйыққа тірелетін жағдайдан қашуға және толық қарастырумен салыстырғанда уақытты үнемдеуге мүмкіндік береді. Айтпақшы, бұл тәсіл сарапшы өнім жүйелерінде жеткілікті тараған.

Альфа-бета-процедура. Теория бойынша, бұл минимаксқа теңбе-тең процедура, оның көмегімен әрқашан дәл сондай нәтиже шығады, бірақ тезірек, өйткені ағаштың бүтін бөліктері талдау жүргізусіз шығарылады. Бұл процедураның негізінде Дж.Маккартидің α және β деп белгіленетін екі айнымалыны пайдалану туралы ойы жатыр (1961 жыл).

Тәсілдің негізгі ойы тармақтарды толық меңгеру үшін алынған ең жақсы бағаларды қалғандары үшін ең жақсы болжалған бағалармен салыстырудан тұрады. Анықталған жағдайларда кейбір есептеулер артық болып табылатынын көрсетуге болады. 21 суреттегі мысалда қиып өту ойының қарастырайық. А позициясы толық талданған және α бағасының мәні табылды деп болжайық. Y позициясынан бір жүріс бағасы минимакс тәсілі бойынша бағасы z тең Z позициясына әкелсін дейік. болсын. Z түйінін талдағаннан кейін қатынасы әділ, Y түйінінен шығатын ағаш тармақтары лақтырылып тасталына алады (альфа-қиып өту).

Сурет 21. Қиып өту ойыны

 

Егер біз еркін тереңдік деңгейінде жатқан, S деңгейі жатқан жаққа ие Z түйініне дейін түскіміз келсе, онда қарсылас жүрісімен алынатын β бағасының минималды мәнін есепке алу қажет.

Қарсылас жүрісінен кейін пайда болатын позиция бағасы β мәнінен асқанда β типті қиып өту орындалады. Іздеу алгоритмі α және β өлшемдері бар ағашты талдау кезінде сәйкесінше өз жүрісі және қарсылас жүрісінің бағасын салыстыру арқылы құрылады. Есептеудің басында бұл өлшемдерге +∞ және -∞ мәндері беріледі, ағаш түбіріне жылжу өлшемі бойынша бастапқы позиция бағасы және қарсыластардың біреуі үшін ең жақсы жүріс табылады.

Іздеу процесінде келесі α және β есептеу ережелері ұсынылады:

а) MАХ төбеде α мәні қазіргі сәттегі оның дочерный төбелері үшін біржола қайтарылған мәндер арасында ең үлкен мәнге тең;

б) MIN төбеде β мәні қазіргі сәттегі оның дочерный төбелері үшін біржола қайтарылған мәндер арасында ең кіші мәнге тең.

Іздеуді тоқтату ережесі:

в) қандай да бір MIN төбеден өсетін, оның барлық аталық MAX төбелерінің β мәні α мәнінен аспайтын ағаш астында іздеу жүргізбеуге болады;

г) қандай да бір MАХ төбеден өсетін, оның барлық аталық MAX төбелерінің α мәні β мәнінен кем болмайтын ағаш астында іздеу жүргізбеуге болады.

22-суретінде нақты мысал үшін α-β қиып көрсетілген. Осылайша, α-β-алгоритмі минимакс тәсіліндегідей нәтиже береді, бірақ тезірек орындалады.

Сурет 22.

 

Эвристикалық іздеу алгоритмін қиынарақ тапсырмалар мен ойындарда (шашки, шахмат) ЖӘНЕ, НЕМЕСЕ графында ұтыс стратегиясын іздеу үшін пайдалану мүмкін емес. Кейбір бағалар бойынша ойындық ағаш шашки ойынында ~ 10⁴⁰ төбеден, шахмат ойынында ~ 10¹²⁰ төбеден тұрады. Егер шашки ойынын ойнаған кезде бір төбе үшін 1/3 наносекунд қажет болса, онда барлық ойын үшін 10²¹ ғасыр уақыт қажет болады. Мұндай жағдайларда іздеу ағашындағы ең көп рұқсат етілген төбелер тереңдігі немесе уақытқа шектеу және жады көлемі сияқты факторларға негізделген тоқтатудың жасанды шарттары енгізіледі.

Жоғарыда қарастырылған ойлардың көбі А.Ньюэллмен, Дж. Шоумен, Г.Саймонмен олардың GPS бағдарламасында пайдаланылған. GPS жұмыс процесі жалпы адаммен қолданылатын тапсырманы шешу әдістерін өндіреді: шешімге жақындататын мақсаттар шығарылады; шешім алынғанша дейін эвристикалық әдіс қолданылады (біреу, келесі және т.б.). Егер шешім алу мүмкін болмаса, ұмтылыс тоқтатылады. 

STRIPS (Stanford Research Institut Problem Solver) бағдарламасы қойылған мақсатқа байланысты робот әрекетінің сәйкес тәртібін өңдейді. Бағдарлама алдыңғы тапсырмаларды шешу тәжірибесінде оқуға қабілетті. Мысалға, Самюэльдің 1974 жылы әлем чемпионын жеңген атақты шашкалық бағдарламасы ұтқан партияларды «жатқа жаттайды» және өткен тәжірибеден пайда алу үшін оларды жалпылайды. Зауссманның робот әрекетін басқаратын HACHER бағдарламасы да осылайша қателерінде оқыған.

Предикаттарды есептеу негізінде шешімді іздеу әдістері. Предикаттарды есептеу семантикасы логикалық қорытындыны формалдау үшін негізді қамтамасыз етеді. Ақиқат тұжырымдар жиынынан жаңа дұрыс пікірлерді логикалық шығару мүмкіндігі өте маңызды. Логикалық шығарылған тұжырымдамалар мүлтіксіз және олар бастапқы пікірлер жиынының барлық интерпритацияларымен үйлесімді. Жоғарыда айтылғанды формалді емес талдайық және сосын қажет формалдауды енгіземіз.

Пікірлерді есептеуде негізгі объект ақиқаттығы мен жалғандығы оған кіретін айнымалылардың мәндеріне тәуелді айнымалылы пікір (предикат) болып табылады. Сонымен, предикаттың ақиқаттығы «х физик болды» х айнымалы мәніне тәуелді. Егер х – П.Капица, онда предикат ақиқат, егер х- М.Лермонтов, онда ол жалған. Предикаттарды есептеу тілінде тұжырымдамасы былай оқылады: «Егер кез келген х үшін Р (х), онда Q (х)-тың да орны бар». Кейде оны былай да жазады: . ақиқаттылығы оларға кіретін пікірлердің ақиқаттылығына байланысты емес көрсетілген теңбе-тең ақиқат формулалар (немесе дұрыс құрастырылған формулалар - ДҚФ) жиыны аксиомалар деп аталады.

Предикаттарды есептеуде қорытынды ережелер жиыны бар. Мысал ретінде «егер А формаласы ақиқат, және А онда В ақиқат болса, онда В формуласы да ақиқат» деп оқылатын классикалық бөлу ережесін, немесе modus ponens келтірейік:

 

Сызықтың үстінде орналасқан формулалар түйін (посылка) деп аталады, ал сызықтың астында – қорытынды. Бұл қорытынды шығару дедуктивті жүйенің негізгі заңын құрайды: ақиқат түйіннен әрқашан ақиқат қорытынды шығады. Аксиомалар және бірінші реттегі предикаттарды есептеу ережелері логикалық бағдарламалауда талдау сызбаларын құру өтетін формальді дедуктивті жүйенің негізін береді. Қорытындының басқа да ережелерін еске түсіруге болады.

Modus tollendo tollens: Егер А онда В және В жалған, онда А да жалған.

Modus ponendo tollens: Егер А және В бір уақытта ақиқат бола алмаса және А ақиқат болса, онда В жалған.

Modus tollendo ponens: Егер немесе А, немесе В ақиқат болса және А қиқат емес, онда В ақиқат.

Шешілетін есеп F ₁, F ₂… F _n бірінші ретті предикаттарды есептеу тұжырымдамалар (аксиомалар) түрінде ұсынылады. В есебінің мақсаты тұжырымдама түрінде жазылады, оның әділдігін формальді жүйелерді шығару ережелері мен аксиомаларын шығаруға немесе терістеуге, сонда есептің шешімі F ₁, F ₂… F _n берілген формалалар жиынынан В мақсатты формуласынан логикалық талдауды анықтауға келтіріледі. Мұндай анықтау жалпымағыналық (теңбе-тең ақиқат) формуласының

F ₁& F ₂&…& F _n

дәлелдеуіненемесе (теңбе-тең жалған) формуласының

F ₁& F ₂&…& F _n

орындалмауына тең.

Тәжірибелік ойлаулардан керіден дәлелдеуді пайдаланған ыңғайлы, яғни орындалмайтын формулаларды дәлелдеу. Кері дәлелдеудің қорытындылау ережесі логикалық бағдарлауда қолданылатын резолюция принципі де негізделген. Робинсан modus ponens— тен күштірек өзі оны резолюциялық принципі деп атаған қорытындылау ережесін ашты. Резолюция принципін пайдалану кезінде қиын емес түрлендіру көмегімен предикаттарды есептеу формулалары дизъюнктивті формаға келтіріледі, яғни дизъюнкттер жиыны түрінде ұсынылады. Сонымен қатар дизъюнкт деп әрбірі немесе предикат, немесе предикаттың терістеуі болып табылатын литералдар дизъюнкциясы түсіндіріледі.

Дизъюнкт мысалын келтірейік:

Р – сыйлау предикаты, с ₁ – Ключевский, Q – білу, с ₂- тарих болсын. Енді берілген дизъюнкт келесі фактіні бейнелейді: «тарихты білетін әрбіреу, ключевскийді сыйлайды».

Дизъюнкттің тағы бір мысалын келтірейік:

&

Р – білу предикаты, с ₁ – физика, с ₂- тарих болсын. Берілген дизъюнкт «физика мен тарихты біруақытта кім біледі» сауалын бейнелейді.

Осылайша, шешілетін есептердің (фактілердің) және есептердің мақсаттық тұжырымдамаларын бірінші ретті логикалық предикаттардың дизъюнктивті формасында білдіруге болады. Дизъюнкттерде әдетте жалпылау кванторлары түсіріледі, ал  байланыстары импликациямен ауыстырылады.

Резолюция принципіне оралайық. Бұл қорытындылау ережесінің басты ойы – дизъюнкттер жиыны R бос (жалған) дизъюнкттен тұратынын тексеру. Әдетте резолюция пайымдаудың тура немесе кері әдісімен қолданылады. түйінінен тура әдіс В қорытындысын шығарады (modus ponens ережесі). Тура әдістің негізгі кемшілігі оның бағытталмағандығында: әдісті қайта пайдалану мақсаттық қорытындымен байланыспаған аралық қорытындылардың күрт өсуіне әкеледі. Кері қорытындылау бағытталған болып табылады: ол қаланған В қорытындысынан және сол түйіндерден жаңа мақсат астылық А қорытындысын шығарады. Бұл жағдайда шешімнің әрбір қадамы әрқашан бастапқы қойылған мақсатпен байланысты. Резолюция әдісінің үлкен кемшілігі шешімнің әрбір қадамында резольвенттер жиынының – жаңа дизъюнкттердің қалыптасуында, олардың көбі артық болып шығады. Осыған байланысты резолюция принципінің іздеудің тиімдірек стратегиясын және бастапқы деректер түріне әр түрлі шектеулерді пайдаланатын түрлі модификациялары өңделген. Бұл мағынада Хорно дизъюнкттері деп аталатын дизъюнкттердің арнайы түрлерін пайдаланатын ПРОЛОГ жүйесі ең сәтті және танымал болып табылады.  

Резолюция әдісімен (керіден) дәлелдеу процесі келесі кезеңдерден тұрады:

1. Пікірлер мен аксиомалар дизъюнктивті нормальді формаға келтіріледі.

2. Аксиомалар жиынына дизъюнктивті формада дәлелденетін тұжырымдама терістеуі қосылады.

3. Бұл дизъюнкттердің біріккен рұқсат етулері орындалады, нәтижесінде осыған негізделген жаңа дизъюнктивті өрнектер (резольвенттер) шығады.

4.  Қарама-қайшылықты білдіретін бос өрнектер генерирленеді.

5. Бос өрнекті алу үшін, пайдаланылған орналастырулар терістеуді терістеу ақиқат екендігі туралы куәландырады.

Шешімді іздеу әдістерін предикаттарды есептеу негізінде қолдану мысалые қарастырайық. [1.1] «қызықты өмір» мысалы кірістірілген. Сонымен, 3 кестенің сол жақ бағанында 1-4 бекітулер берілген. «Қызықты өмір сүретін адам бар ма?» сұрағына жауап беру керек. Предикат түрінде бұл бекітулер кестенің екінші бағанында жазылған. және  жорамалданады. Кестенің үшінші бағанында дизъюнкттер жазылған.

 

 Кесте 3. Қызықты өмір

Бекітулер және қорытынды	Предикаттар	Ұйғарымдар (дизъюнкттер)
1. Барлық кедей емес және ақылды адамдар бақытты		&
2. Кітапты оқушы адам – ақылсыз емес		&
3. Джон оқу біледі және дәулетті адам болып табылады
4. Бақытты адамдар қызықты өмір сүреді		&
5. Қорытынды: Қызықты өмір сүретін адам бар ма?
6.Қорытындыны терістеу

 

Қорытындыны терістеу (6 жол): түрге ие. Мүмкін дәлелдеулердің біреуі (олар бірден көп) резольвенттердің келесі тізбегін береді:

7.                                6 және 4 резольвентасы

8.              7 және 1 резольвентасы

9.                                8 және 2 резольвентасы

10.                              9 және 3b резольвентасы

11. NIL                                         10 және 3а резольвентасы

 

NIL символы деректер базасының өрнектерінің үйлеспеушіліктен тұратынын білдіреді және сондықтан біздің қызықты өмір сүретін адамның жоқ екендігі туралы жорамалымыз қате.

Резолюция әдісінде дизъюнктивті өрнектерді қисындыру тәртібі орнатылмайды. Демек, үлкен есептер үшін мүмкін резолюция процедурасында сондай-ақ іздеу эвристикасы және түрлі стратегиялар үлкен маңызға ие. Егер қарапайым және түсінікті стратегиялардың бірі – бірлік өрнекке ерекше құрмет стратегиясы, ол резольвента ең үлкен ата-аналық өрнекке қарағанда кем болатындығына кепілдік береді. Қорытындыда біз литералы мүлдем жоқ өрнек алуымыз керек қой.

Басқа стратегиялар арасында (көлденеңнен іздеу (breadth-first), «қолдау жиыны» стратегиясы, сызықтық кіру форма стратегиясы) «қолдау жиыны» стратегиясы дизъюнктивті өрнектердің үлкен кеңістігінде іздеу кезінде өте жақсы нәтиже көрсетеді [1.1]. Стратегия мәні мынада. Бастапқы S дизъюнктивті өрнектердің кейбір жиыны үшін Т қолдау жиыны деп аталатын жиын астын көрсетуге болады. Бұл стратегияны жүзеге асыру үшін қолдау жиынында әрбір жоққа шығаруда резольвенттердің тегі болу керек. Егер S – дизъюнкттердің орындалмайтын жиыны, ал S-T – орындалатын, онда қолдау жиыны стратегиясы жоққа шығару мағынасында толық болып табылатынын дәлелдеуге болады.

Теорияларды дәлелдеу және резолюцияны теріске шығару алгоритмдерін өңдеумен байланысты зерттеулер PROLOG логикалық бағдарламалау тілінің дамуына әкелді. PROLOG бірінші реттегі предикаттар теориясына негізделген. Логикалық бағдарламалау – бұл формальді логика шеңберінде егжей-тегжейлі ашу жиыны. Қазіргі уақытта LISP және PROLOG тілдерінің үлес салмағының төмендеуіне және ИИ есептерін шешу кезінде С, С++ және Java көбірек қолданылатынына қарамастан, көп тапсырмалар және ИИ есептерін шешудің жаңа әдістерін өңдеу LISP және PROLOG тілдеріне сүйеніп келеді. Мұндай есептердің біреуін, әрекет тізбегін жоспарлайтын және оны предикаттар теориясының негізінде шешу есебін, қарастырайық.