Муканова асель сериковна
жүктеу/скачать 5,36 Mb.
|
диссертация Асель
| Күй кеңістігінде шешімдерді іздеудің жалпы әдістері
Интеллектуалды жүйелерде көптеген мәселелердің шешімі ретінде іздеу мәселесін анықтауды айтуға болады, мұнда ізделінетін шешім – бұл іздеудің мақсаты, ал осы мақсатқа жетудің мүмкін болатын жолдарының жиынтығы іздеу кеңістігі (немесе күй кеңістігі) болып табылады. Күй кеңістігінде шешімдерді табу бастапқы күйді мақсатты күйге айналдыратын операторлар тізбегінен тұрады. Күй кеңістігіндегі іздеу есебін былай формалдауға болады: бастапқы есеп () үштігі арқылы берілсін, мұндағы – бастапқы күйлердің жиыны; – бір күйден екінші күйге өтуді көрсететін операторлардың жиыны; – мақсатты күйлердің жиыны. Есептің шешімі ол бастапқы күйлерді соңғы мақсатты күйге алып келетін операторлар тізбегін табу болып табылады. Күй кеңістігіндегі іздеу есебі графтар теориясы түсінігімен сипатталады. Алдымен графтың бастапқы төбесі (бастапқы күй), сосын мақсатты төбелер Т жиынтығы беріледі. Күй кеңістігін құру үшін F операторлар қолданылады. Ағаштың түбір төбесінен келесі деңгейдегі мұрагер төбелерді құру үшін сол деңгейге сәйкес келетін операторлар қолданылады. Төбелер арасындағы доғаларды түрлендіру операторларына теңестіруге болады. Алынатын мұрагер төбелер мақсатты төбеге сәйкес келетіндігіне тексеріледі. Әрі қарай келесі деңгейге өтеді. Терминал төбе дегеніміз ешқандай да операторлар ды қолдануға болмайтын төбелер. Төбелерді ашу мақсатты немесе терминалды төбе алынғанға дейін жұмыс жасайды. Күйлер графында іздеу дегеніміз – бұл мақсатты төбе бар графын құру үдерісі. Бұл граф іздеу графы деп аталады. Іріктеу әдісін жүзеге асырудың бірнеше нұсқасы бар, олар бір бірінен іріктелетін төбенің берілу ретімен өзгешеленеді. Тереңдікке іздеу. Тереңдікке іздеу кезінде алдымен ең тереңде орналасқан төбе ашылады. Бірдей тереңдікте орналасқан төбелердің ішінен біреуін таңдау ерікті түрде таңдалады. Шексіз жолмен айналып кетіп қалмау үшін тереңдікке шектеулі мән қоюымызға болады, Шекаралық тереңдікте орналсқан төберлер ашылмайды. Еніне қарай іздеу. Төбелер олардың туындау тізбегіне байланысты ашылады. Себебі төбелерді ашу бір деңгейде жүзеге асырылады. Мақсатты төбе туындағаннан кейін таңдалынады. Еніне қарай іздеу кезінде мақсатты төбеге жетудің ең қысқа жолын табу мүмкінді көбірек. 2 және 3 суреттерде тереңдікке және еніне қарай іздеу графтары көрсетілген. Cурет 2 – Тереңдікке қарай іздеу кезінде құрылған іздеу графы Cурет 3 – Еніне қарай іздеу кезінде құрылған іздеу графы Қайтуы бар іздеу (бэктрекинг). Мұндай іздеуді жүзеге асыру кезінде ережені таңдау кезінде қайту нүктесі анықталады, яғни егер таңдалып алынған бағыт бойынша іздеу қиындықтар туғызатын болса, онда қайту нүктесіне өту жүзеге асырылады. Ары қарай басқа ереже қолданылады да, іздеу үдерісі жалғасады. Бұл кезде тұйыққа тірелген жағдайлардың барлығы жаңа ереже қолданған сәттен бастап ұмытылады да, іздеудің басқа бағытына өтеді. Қайтуы бар іздеудің мұндай түрі хронологиялық қайтуы бар деп аталады. Бұл әдістің көбінесе тиімділігі аз, себебі ол іздеу кезінде кездескен сәтсіз күйлер мен қадамдарды есте сақтамайды. Таңдау әдістерінің құндылығы оларды жүзеге асырудың қарапайымдылығы және шешім бар жағдайда оны табыдың мүмкіншілігі. Іздеудің эвристикалық әдісін қарастырылатын шешімдер нұсқаларының көлемін қысқартуға мүмкіндік беретін қандай да бір эмпирикалық ережелер болған кезде қолдануға болады. Эвристикалық әдісті қолдану кезінде төбелерді ашу келешегі бар бағыттар бойынша іздеуді жүзеге асыруға болатындай етіп жүзеге асырылады. Іздеудің бағытын анықтау үшін төбенің немесе жолдың келешегі бар екендігін көрсететін қандай да бір өлшем қолданылады. Бұл өлшемді бағалау функциясы f(n) деп атайды. Редукция әдісінде қажетті мәліметтер жиынтығын іздеу есебін шешу үшін алдымен ішкі мәселелер жиынтығын шешу жүзеге асырылады. Мәселелер әртүрлі тәсілдермен сипатталады: тізім, ағаштар, жиымдардар. Ішкі мәселелер іздеу кеңістігіндегі анықталған күйлер арасындағы байланысты табу мәселелері ретінде қарастырылады. Сонымен қатар түрлену үдерісін графтық құрылымдар арқылы сипаттау қолайлы. Берілген есептің шешімін іздеу үдерісі мұндай сипаттау кезінде мәселелер редукциясының бағытталған графы түрінде бейнеленеді. Мұндай графты «және»/«немесе» графы деп атайдф. Бұл графтың төбелері есеп пен ішкі мәселелердің сипаттамаларын көрсетеді. «және»/«немесе» графында төбелердің екі түрі бар. «және» түрі мұрагер төбелерге сәйкес келетін барлық ішкі мәселелерді шығаруды жүзеге асыру шартына сәйкес шешілетін есеп болып табылады. Ал «немесе» түрі мұрагер төбелерге сәйкес келетін қандай да бір ішкі есепті шығаруды жүзеге асыру шартына сәйкес шешілетін есеп болады. 4 суретте «және»/«немесе» графының бөлігі көрсетілген. 4 суретте көрсетілгендей бастапқы берілген S0 есебі өз ішінде ішкі мәселелерге бөлінеді. Ол және ; немесе ; және ішкі мәселелерінің шешімін табу арқылы шешіледі. , , , төбелер – бұлар «және» түріндегі төбелер. Үзік сызық арқылы бастапқы есепті шешу жолын көрсететін граф көрсетілген. , , , , ішкі мәселелерін шешу айқын деп есептелінеді. Басқа ішкі мәселелердің шешімі белгісіз. Ішкі мәселелер жиыны өзінің аталық төбесінде құрылуы үшін берілген құрылымға негізінен қоымша төбелер қосылады. «және»/«немесе» графының төбелері «және» немесе «немесе» түрлеріне жатуы мүмкін. жүктеу/скачать 5,36 Mb. Достарыңызбен бөлісу:
|