Namangan davlat universiteti informatika kafedrasi

Nazorat savollari
1. Produktsiya qoidasi nima va u nima vazifani bajaradi?
2. Fikrlashning to'g'ridan-to'g'ri usuli bilan teskari usuli o'rtasidagi farq nimadan iborat?
3. BZ dan qoidalar chiqarish qanday nazorat qilinadi?
4. Qoidalarning yakunlovchi qismining ishonchliligi qanday hisobga olinadi?

7-mavzu: Avtoassosasitiv to’rlar.
Ishdan maqsad: Qidiruv “Hill climbing” texnikasi algoritmini ishlab chiqish.
Masalaning qo’yilishi. “Hill climbing” texnikasini qo’llab masalanig yechimini topish.
Uslubiy ko’rsatmalar. Evristik qidiruvning asosiy g’oyasi shundan iborat-ki, unda qidiruv jarayonini boshqarish uchun qo’shimcha axborotlardan foydalaniladi. Bu qo’shimcha axborot empirik orttirilgan tajriba, topish va tadqiqotchining intuitsiyasi, ya’ni evristikasi asosida shakllantiriladi. Evristikadan foydalanish masalaning yechimini izlash jarayonida maqsadga tezroq erishishga olib boruvchi ko’rib chiqiladigan variantlar sonini qisqartirish imkonini beradi.
Evrsitik qidiruv algoritmlarida evristik qoidalar asosida shakllantiriluvchi ochiq cho’qqilar ro’yhati bir nechta baholash funksiyalarining o’sish tartibi bo’yicha tartiblanadi. Baholash funksiyasi ikkita tashkil qiluvchini o’z ichiga olishi mumkin, ulardan biri evristik deb ataladi va hozirgi va maqsadga yaqinlashishni harakterlaydi. Baholash funksiyasi evristik tashkil etuvchisining qiymati qanchalik kichik bo’lsa, ko’rib chiqilayotgan cho’qqi maqsadga shuncha yaqin bo’ladi.
Baholash funksiyasining shakllanish usuliga ko’ra Evristik qidiruv algoritmlari quyidagi turlarga bo’linadi: “tog’ga ko’tarilish”, maqsadga muvofiqlikning global hisob algoritmi, A-algoritm.
1. “Tog’ga ko’tarilish” algoritmi. Algoritm maqsadga yo’naltirilgan qidirishni o’zida ifodalab, .evristik baholash funksiyasining ko’p yo’nalishlarda kamayishini aks ettiradi. Ushbu funksiya joriy n cho’qqidan eng yaqin maqsad cho’qqisiga eltuvchi eng qisqa yo’lning qiymatini ta’minlaydi, qolgan yo’lning qiymati o’lchov sifatida olinadi. funksiyaning qiymati qanchalik kam bo'lsa, cho'qqi joylashgan yo'l shunchalik “istiqbolli” sanaladi.
Ushbu algoritm funksiyaning ekstremumlarini topishda ishlatiladi. Ma’lumki, ko’plab o’zgaruvchilar funksiya ekstremumlarining holati, gradient funksiyaning vektor yo’nalishlarida aniqlanadi. Shuning uchun ekstremum funksiyaning yo’nalishini yana ham o’sishiga, ya’ni gradient yo’nalishinig mos kelishini amalga oshiradi. Funksiyaning maksimumini qidirish eng yuqori cho’qqiga ko’tarilishning optimal yo’lini eslatadi. Shunig uchun ko’rilayotgan algoritm hill-climbing deb ataladi.
Algoritmning navbatdagi qadamida baholash funksiyasi uchun qoyalar quyidagi qiymatlar va qolgan yo’llar uchun qiymat belgilanadi. Agar barcha yondosh qoyalar qiymatga ega bo’lsa qidiruv protsedurasi muvaffaqiyatsizlikka uchraydi,
Procedure Hill_Climbing; 
Begin 
n := ’boshlang’ich cho’qqi’; 
While n <> ’maqsad cho’qqisi’ Do Begin 
n cho’qqining barcha yondosh cho’qqilari uchun qiymatlarni xisoblash; 
Minimal qiymatlarga ega yondosh cho’qqini tanlash; 
If Then Chiqish(MUVAFFAQQIYATSIZ); 
n :=  ; 
End; 
Chiqish(MUVAFFAQQIYATSIZ); 
End.
Evristik baholash funksiyasini yaratishning turli hil usullari bor, lekin tayyor qoida mavjud emas. Aniq masalalarni yechish jarayonida shunga o’xshash oldin yechilgan masalalardan olingan tajribalardan foydalaniladi. qiymat quyidagi formula yordamida xisoblanadi:
,
- maqsad cho’qqisining koordinatalari;  - joriy cho’qqining koordinatalari.
Ushbu qiymat n cho’qqidan maqsad cho’qqisigacha bo’lgan masofaga bog’liq. Holatlar grafi rasmida tasvirlangan labirintda yo’lni qidirish jarayonida ega bo’linadigan cho’qqilarning ketma-ketligi quyidagicha bo’ladi: A, B, L, G. Holatlar grafi rasmida tasvirlangan labirintda yo’lni qidirish jarayoni muvaffaqqiyatsiz yakunlanadi. Bu holatda yo’lni qidirish jarayonida ega bo’linadigan cho’qqilarning ketma-ketligi quyidagicha bo’ladi: A, B. baholash funksiyasi B cho’qqida 3 qiymatga ega bo’ladi. Keyingi qadamlar ĥ(F)=3 va ĥ(C)=4 ekanligi sababli muvaffaqqiyatsiz ekanligi ma’lum bo’ladi, qidirishni davom ettirish uchun quyidagi shart bajarilishi kerak:
Shu tartibda, ushbu algoritm qidiruv jarayonini tezlashtirgani bilan, maqsad cho’qqisiga erishishni kafolatlamaydi. Quyidagi holatlarda algoritmning vaqtidan oldin yakunlanishi yuz beradi: agar qidiruv jarayonida ĥ(n) baholash funksiyasining lokal minimulari uchrasa; agar qo’shni cho’qqilar guruhlari uchun ĥ(n) ning qiymatlari o’zaro teng bo’lsa («Plato» muammosi).