+6-маъруза

1 → 3 → 5 → 4 .

6.7-rasmda va 6.1-jadvalda keltirilgan boshlang’ich qiymatlar uchun qisqa yo’lni toppish masalasi to’liq echildi.

4. 
   Evristikli izlash
   

Churligi va kengligi bo’yicha izlash strategiyalari bosh tugundan chiquvchi yo’llar orasidan hal qiluvchi (qisqa, minimal) yo’lni izlab topishda barcha tugunlarni birma-bir tekshirishga asoslanadi. Ko’rinib turibdiki, bizga faqat tugunlar N va yoylar L ro’yxatidan iborat frag berilgan bo’lsa, u holda maqsadli hal qiluvchi y’olni topishda tugunlarni birma-bir tekshirish yordamida erishish mumkin.

Ko’p hollarda maqsadli hal qiluvchi y’olni topishda tugunlar N va yoylar L ro’yxatidan iborat grafda izlashni qisqartirish (vaqtni, hisoblash hajmini) maqsadida ba’zi bir qo’shimcha axborotlardan foydalanish imkoniyatlari mavjud. Shunday qo’shimcha axborotlar evristikli deyiladi. Evristikli axborotlar yordamida izlash evristikli izlash deyiladi. Masala haqidagi evristik axborotlarni hisobga olib alternative tugunlarni tanlash protsedurasi evristike deyiladi,
Masala haqidagi qo’shimcha (evristikli) axborotlar ba’zi hollarda tugunlardan iborat HFda, ya’ni tugunlar to’plamida baholash funksiyasi f(n) shaklida sonli ifoda ko’rinishida ifodalanishi mumkin.
HFdagi n-tugundagi baholash funksiyasi f(), n – tugunlardan izlashni davom ettirishni baholash uchun haqiqiy son f (n) bilan taqqoslanadi. f (n) ning qiymati qanchalik kichchik (ba’zi masalalarda qanchalik katta) bo’lsa, ushbu n-tugundan izlashni davom ettirish maqsadga muvofiq bo’ladi. Shuning uchun ham evrisrtik izlashni ba’zi hollarda maqsadli (afzalli) izlash deb atashadi.
Evristik izlashning g’oyasi quyidagidan iborat: yo’lning bo’shlanish tuguni sifatida nomzod tugunlar orasidan afzalroq tugunni tanlash kerak va ushbi tugun grafdagi hal qiluvchi yo’lning boshlang’ish tuguni sifatida qabul qilinadi. Undan keyin boshlang’ich tugundan boshlanadigan yo’lni davom ettirish uchun boshlanf’ich tugundan chiqadigan bir qancha alternativ tugunlardan baholash funksiyasi kichchikroq (ba’zi hollarda kattaroq) qiymatga ega bo’lgan tugun tanlanadi. Yo’lni davom ettirish uchun navbatdagi tugunlarni tanlashda bir qancha alternativ tugunlardan baholash funksiyasi kichchikroq (ba’zi hollarda kattaroq) qiymatga ega bo’lgan tugunlar tanlanadi. Tugunlarni tanlash algoritm bo’yicha maqsadli echimga erishuvchi yo’lni topishgacha davom ettiriladi.
Baholash funksiyasidan foydalnishga asoslangan ko’plab evristik izlash usullari mavjud. Bular qatoriga chiziqli programmalashtirishdagi simpleks usuli, A* algoritmi, sonli tahlildagi ketma-ket yaqinlashish usullari, minimaxli usullar, al’fa-
betta algoritm, dinamik programmalash, shoxlar va chegaralar usuli, bo’linish va baholash usulilarini kiritish mumkin.
Evristik izlashni namoyish etrish uchun namuna sifatida А* algoritmini keltiramiz.

1.