Оқулық Қазақстан Республикасы Білім және ғылым министрлігі бекіткен Алматы, 2011
Ені бойынша толық іріктеп алу әдісі
жүктеу/скачать 2,02 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- 5.3. Тереңдік бойынша толық іріктеп алу әдісі
| 5.2. Ені бойынша толық іріктеп алу әдісі
Шыңдар қандай ретімен құрылса, сондай ретімен ашылады ( 5.4-сурет ). Негізгі алгоритм келесі әрекеттердің орындауынан тұрады. 1. Бастапқы шың ашылғанша, бірдей (немесе әртүрлі, шартқа қарағанда) операторды қолдап оны аша береді. Осы кезде бірінші деңгейдің шыңдары S 2 , S 3 ... пайда болады. Олар ӛзінің ретімен ашылады және екінші деңгейдің шыңдарын жасайды және т.б. 2. Жаңа шыңдардан түбірге жүргізетін сілтегіштер (шартты есімдер, әріптер, цифрлер, оператор аттары, қашықтықтар, бағасы, салмақ және т.б.) қойылады. 3. Алынған шыңдардың арасында мақсатты бар болғаны тексеріледі. Егер бар болса, онда сәйкес операторға негізделіп шешім жасалынады. Егер мақсатты шыңдар жоқ болса, онда бірінші тудырылған шың қарастырылады және оған да сол алгоритм қолданады. Осыдан кейін алынған шыңдардың арасында мақсаттыны тапқанша екінші және т.б. ауысып отырады. 5.4-сурет . Ені бойынша іріктеп алу ағаштың фрагменті Ені бойынша толық іріктеп алу мақсатты шыңның табуына кепіл береді, себебі іріктеп алу толық жүргізіледі. Мақсатқа жетудің бірнеше жолдары болу мүмкін. Бұл жағдайда ең қысқа (ең арзан, ең оңай, ең жылдам және т.с.с.) жолды таңдауға болады. Бірақ, іздестіру графы шексіз бола қалса, онда алгоритм ӛз жұмысын аяқтай алмайды. Классикалық мысал – «лабиринтты іздестіру» есебі, оны бірінші шешкен К.Шеннон. Мұнда түрлі әрекет варианттар кеңістігі үлкен емес: «оңға бұрылу», «солға», «алға» және шешім кейбір берілген тереңдікте (әдетте кішкентай) жатады. 49 5.3. Тереңдік бойынша толық іріктеп алу әдісі Тереңдік бойынша іріктеп алуда ( 5.5-сурет ) алдымен, соңғы құрылған шыңдарды ашу керек. Бірінші, ендеше соңғы да ашылатың шың бұл түбір шыңы. Процесс әрқашанда шыңдардың ең сол жақ тармағы бойынша ӛтеді. Іріктеп алуды қалай болсада шектеу үшін, іріктеп алу ағашта шыңның тереңдігі деген ұғым енгізіледі. Ағаштың түбір тереңдігі нӛлге тең, ал әрбіреу келесі шыңның тереңдігі оның алдындағы шыңның тереңдігіне тең бір плюс. Ең үлкен тереңдік осы мезетте ашуға қажетті болатын шыңда. Егер жасалынған жол пайдасыз болса (яғни берілген тереңдікте мақсатты шың ашылмаса), онда ашылғанның алдында болған шыңға қайтып келу керек және оған тағы да, мақсатты шыңды алғанша, ашу операциясына әркеттену қажет. Бұл процесс (бірнеше қадамға қайтып келу) артқа шегіну немесе бэктрекинг деп аталады. Артқа шегіну сілтегіштер кӛмегімен жүзеге асырылады. Берілген шекаралық тереңдікке жеткеннен кейін, осы шекарадан аспайтын ең үлкен тереңдікті шың ашылады. Бұл «кері қадағалауы бар бағдарламалау» ( back – track programming ) деп аталады. Тереңдік бойынша іріктеп алудың сұлбасы 5.5-суретте кӛрсетілген. жүктеу/скачать 2,02 Mb. Достарыңызбен бөлісу:
|