Оқулық Қазақстан Республикасы Білім және ғылым министрлігі бекіткен Алматы, 2011
жүктеу/скачать 2,02 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- 5.4. Кҥйлер кеңістігінде іздестірудің эвристикалық әдістері
| 5.5-сурет
. Бэктрекинг нұсқауы бар тереңдік бойынша іріктеу ағашы Тереңдік бойынша іріктеп алудың алгоритмы келесі: 1. Бастапқы күйге сәйкес бастапқы шың ашылады. 2. Бастапқы шыңның ашу нәтижесінде алынған бірінші шың ашылады. Сілтегіш қойылады. 3. Егер ол ашылса, онда келесі болып қайтадан тудырылған шың ашылады. Егер шың ашылмаса, онда процесс алдындағы шыңға қайтып келеді. 4. Мақсатты шыңды алғаннан кейін ашу процесі аяқталады және сілтегіштер арқылы түбірге келтіретін жол құрылады. Доғаларға сәйкес операторлар есептін шешімін жасайды. 50 5. Егер берілген ашу тереңдігі үшін мақсатты шың табылмаса, онда барлық процесс қайталанады, ал жаңа шың ретінде алдындағы кезеңде алынғанның ең сол жақ шыңы қарастырылады. 5.4. Кҥйлер кеңістігінде іздестірудің эвристикалық әдістері Толық іріктеп алудың әдістері есептің шешімін кепілдейді, егер ол бар болса, ал бірнеше шешім болса, онда ең тиімділігін растайды. Бірақ, тәжірибеде бұл әдістер тек үлкен емес күйлер графтары үшін пайдаланады. Нақты жағдайлар үшін бұрыңғы тәжірибеге сүйенетін немесе теориялық шығармаларға негізделген қосымша ақпарат кӛбінесе, пайдаланады. Осындай ақпарат эвристикалық , ал ережеге ұйымдастырылған – эвристикалық ережелер немесе эвристика деп аталады. Эвристикалық ақпараттың сипаты арнайы және тек берілген есепке ғана қолданады. Эвристикалық ақпарат іріктеп алуды реттелгенге айналдырады. Мысалы, «Беллманның динамикалық бағдарламау әдісі», «бұтақтар мен шекара әдісі» және т.б. Мысал ретінде коммивояжер туралы танымалы есепті қарастырайық. Кӛшпелі сатушы N қаланың бәрінде бір рет болып шығып, бастапқы қалаға қайтып келуі тиіс. Маршрут ұзыңдығы минималды болу керек ( 5.6-сурет ). 5.6-сурет . Коммивояжер туралы есептің күйлер графы Күйлер кеңістігінің фрагменты 5.7-суретте келтірілген. Ені бойынша іріктеуді бастаймыз және бірден бірінші деңгейде әртүрлі ұзыңдығы бар мүмкін болатын жолдар аламыз: 2, 2, 6, 3. Егер «әрбір қадамда минимал ұзыңдығы жолды таңдау» эвристикадан бастасақ, онда келесі қадамдарды жасау керек S 1 — S 2 және S 2 — S 3 , сосын S 3 — S 4 немесе S 3 — S 5 , сосын S 4 — S 5 және т.б. 51 5.7-сурет . Коммивояжер туралы есеп үшін іріктеу ағаштың фрагменті Коммивояжердің барлық мүмкін жолдарын қосатың толық іріктеу графында (N - 1)! варианты болады. Егер кері жолдарды есептемесек, онда (N - 1)!/2. Осындай типке жататын нақты есептерде (мысалы, пейджинг таратқыштың орналасуы, банкоматтар орналасуы және т.с.с.) N әдетте, бірнеше ондаған объектілерге тең болады. Эвристикалық алгоритмдер бір ғана дұрыс (оптималды) шешімді іздеу үшін емес, ал кейбір критерийге сәйкес кӛбінесе, бірінші шешімді іздеу үшін қолданылады. Мысалы, адам дүкенге барғанда, ең арзан сүтті алу деген мақсат ӛзіне қоймайды, ол белгілі сапасынан тӛмен емес және кейбір бағадан қымбат еместі сатып алғысы келеді және осыған 5 минуттен артық уақыт жұмсамайды. жүктеу/скачать 2,02 Mb. Достарыңызбен бөлісу:
|