Sun’iy intellekt masalalarini holatlar fazosida namoyish etish

Информация о документе

Цена	2000UZS
Размер	1.6MB
Покупки	0
Дата загрузки	07 Ноябрь 2026
Расширение	docx
Раздел	Рефераты
Предмет	Педагогика

Sun’iy intellekt masalalarini holatlar fazosida namoyish etish

Купить

4) Xususiy havolalardan foydalanish. Bunda aniq obyektlarga havolalarni o’z
ichiga oluvchi xususiy havolalardan foydalaniladi.
Echiladigan masalalarni quyidagi tiplarga ajratish mumkin:
• interpretatsiyalash – ma’lumotlarning ma’nosini aniqlash jarayoni;
• tashhislash –obyektlarni anglash yoki tizimning nosozligini aniqlash;
• monitorihglash -haqiqiy vaqt oralig’ida ma’lumotlarni uzluksiz izohlash va
ba’zi parametrlarning etarli chegaralardan chiqishi haqida signallar berish;
• bashoratlash -oldingi va hozirgi modellar asosida obyektlar harakatining
rejasini qurish;
• rejalashtirish -ba’zi funksiyalarni bajarish qobilyatiga ega obyektlarning
harakat rejasini qurish;
• loyihalash -oldin mavjud bo’lmagan obyektni yaratish va oldindan aniqlangan
xossalar asosida obyektlarni hosil qilishni tasniflashga tayyorlash;
• o’rganish -obyektlar haqidagi ma’lumotlarni o’rganish uslubiyoti;
• boshqarish -tizimlar funksiyasi bo’lib, tizimlarning qandaydir rejimda
faollashuvini qo’llab quvvatlash yoki qandaydir berilgan vazifani bararishga
mo’ljallangan murakkab tizimlarning harakatini boshqarish;
• qaror qabul qilishni qo’llab-quvvatlash- protseduralar majmuasi bo’lib, u
qaror qabul qilish uchun zarur ma’lumotlar bilan ta’minlangan bo’ladi va qaror qabul
qilish jarayoni uchun ko’rsatmalar beradi.
Masalalarni namoyish etish uslubini tanlashda odatda ikkita holat e’tiborga
olinadi [1, 5-7]:
-masalalarni namoyish etish haqiqiylikni etarli aniq modellashtirishi zarur ;
- masalalarni namoyish etish uslublari shunday bo’lishi kerakki, ushbu masalani
echish EHM (echuvchi) uchun qulay bo’lsin .
2. Sun’iy intellekt masalalarini echishning umumiy uslublari
Masalani echish jarayoni qoidaga ko’ra ikki pog’onadan iborat bo’ladi:
masalani namoyish etish va echimni izlash.
Mashina yordamida masalalarni namoyish etish shakllarini izlash masalasi qiyin
formallashgan ijodiy jarayon hisoblanadi. Shuning uchun masalalarni namoyish
etishda qo'llaniladigan ba’zi shakllarni quyidagich keltirish mumkin [1]:
1) Holatlar fazosi(HF)da namoyish etish;
2) Masalalarni masalalar ostilariga keltirish yo’li bilan namoyish etish;
3) Teoremalar ko’rinishida namoyish etish;
4) Kombinatsiyali namoyish etish.
Masalalarning holatini tavsiflashning turli shakllari mavjud. Xususan,
masalalarni qatorlar , vektorlar, matritsalar va graflar ko’rinishda tavsiflash mumkin
HFda echimlarni izlash protseduralari boshlang’ich holatni maqsad funksiyaga
aylantiruvchi operatorlar ketma-ketligini aniqlashga asoslanadi.
Daraxt deb shunday yo’naltirilgan grafga aytiladiki , bunda uning ildizidan
tashqari har bir tuguniga faqat bitta yoy kiradi.
Shunday qilib, daraxtda ildizdan tashqari har bir tiguni bitta yoyning oxiri va
2

A
И
В
Е F
G C D
H I
И
6.1-rasm.Masalalarni reduksiyalash daraxti.
G
FE H IDA
K
B
C
6.2-rasm. Almashtirilgan reduksiyalash daraxti.
кцииbitta yoki bir nechta yoyning boshi bo’ladi.
Daraxtda V tugundan Vi tugunlar hosil bo’ladi. Bunda V - bosh tugun, Vi - ichki
tugunlar deb nomlanadi. Bosh tugun (ildiz) 0-pog’onali, ildizdan hosil bo’lgan
tugunlar 1-pog’onali, 2-pog’onali va h.k. k-pog’onali bo’lishi mumkin.
Masalalar ostilarining o’zaro aloqasi strukturasi ikki tipda bo’lishi mumkin:
VA- strukturalar va VA-YOKI -strukturalar. VA-strukturalarda asosiy masalani
echishda barcha masalalar ostilarini echish talab etiladi. VA-YOKI - strukturalarda
xususiy masalalar guruhlarga bo’linadi va bu guruhlar bir-biri bilan YOKI
munosabati yordamida , guruhlar ichidagilar esa bir-biri bilan VA munosabati
yordamida bog’lanadi.
Bunday holda boshlang’ich masalani echish uchun, faqat qandaydir bitta
guruhga taalluqli barcha masalalar ostilarini echish etarli hisoblanadi.
Masalalarni masalalar ostilariga keltirishni namoyish etishni tavsiflash uchun
masalalarni reduksiya(tiklash)lash grafi deb nomlanuvchi grafdan foydalaniladi (6.1-
rasm). Bunda grafning tugunlariga masalalar, yoylriga esa masalalarni reduksiyalash
operatorlari mos qo’yiladi. Daraxt ildiziga boshlang’ich masala, 1-pog’ona
tugunlarga esa boshlang’ich masaladan hosil qilingan masalalar ostilari mos
qo’yiladi.
A masala echiladi, agarda B va C masalalar yoki D masala echilsa. B masala
echiladi, agarda E yoki F masala echilsa. C- masala echiladi, agarda G masala
echilsa. D masala echiladi, agarda H va I masalalar echilsa.
VA- strukturali tugunlarning bog’lanishini ko’rsatish uchun maxsus egri
chiziqdan foydalaniladi. Agar daraxtda VA- strukturali bog’langan tugunlar bo’lsa, u
holda ular uchun qo’shimcha tugunlar kiritiladi va ushbu tugunlar VA- strukturali
tugunlarning bosh tugunlariga aylanadi ( рис . 6.2).
3

Bundan keyin faqat a lmashtirilgan reduksiyalash daraxtlarini qaraymiz .
Masalalarni masalalar ostilariga keltirishni namoyish etishda boshlang’ich
masalani bir nechta masalalar octilariga bo’lish qaraladi va bo’lingan har bir masala
osti echimi boshlang’ich masalaning echimini beradi. Har bir masala ostilari oz
navbatida yana masala ostilariga bo’linishi mumkin. Masala ostilariga bo’lish
jarayoni nazariy jihatdan chegaralanmagan. Amaliy jihatdan masala ostilariga bo’lish
jarayoni eng quyi pog’onadagi masala ostilari yordamida echimni olguncha davom
ettiriladi.

3. Sun’iy intellekt masalalarini echishning usullari
3.1. Predmet soha xususiyatlari va masalalarni echish usullarini sinflash
Masalalarni izlashga keltirishga asoslangan echish usullari masala echilayotgan
predmet soha hususiyatlariga va masala echimiga foydalanuvchi tomonidan qo’yilgan
talablarga bevosita bog’liq bo’ladi.
Predmet soha xususiyatlari [1] :
1) Echim izlanayotgan fazo hajmi;
2) Sohaning vaqtli va fazoli o’zgarish darajasi (ststistik va dinamik sohalar);
3) Sohani tavsivlovchi modelning to’liqligi. Agar model to’liq bo’lmasa, u holda
sohani tavsiflashda bir-birini to’ldiruvchi bir nechta modellardan foydalaniladi;
4) Echilayotgan masala haqidagi ma’lumotlarning aniqligi, ya’ni
ma’lumotlarning aniqlik(hatolik) va to’liqlik(to’liqmaslik) darajasi.
SITlari masalalarini echishda qo’llaniladigan mavjud usullarni quyidagicha
sinflash mumkin [1, 8]:
1) Bir o’lchovli fazoda echimni izlash usullari – bu usullardan o’lchovi katta
bo’lmagan sohalarda, modellar to’liq, ma’lumotlar aniq va to’liq bo’lganda
foydalaniladi;
2) Ierarhik fazoda echimni izlash usullari - bu usullardan o’lchovi katta bo’lgan
sohalarda echimlarni izlashda foydalaniladi;
3) Ma’lumotlar xatoli va t o’liqmas bo’lganda izlash usullari;
4) Bir nechta modellar yordamida izlash usullari - bu usullardan sohani
tavsiflashda bitta modelning o’zi etarli bo’lmaganda foydalanilad.
3.2. Holatlar fazosida echimni izlash
3.2.1. Holatlar fazosida echimni izlash usullari
HFda echimni izlash usullari odatda quyidagilarga bo’linadi [1-4]:
1) Chuqurligi bo’yicha izlash;
2) Kengligi bo’yicha izlash;
3) Evristikli izlash.
HFda echimlarni izlash protseduralari boshlang’ich holatni maqsad funksiyaga
aylantiruvchi operatorlar ketma-ketligini aniqlashga asoslanadi. Agar operatorlar
ketma-ketligi bir nechta va optimallashtirish mezoni berilgan bo’lsa, u holda masala
4

A B
C12
11
8 10
6.3-rasm.Marshrutni tanlash masalasi.D 55
6
A
AC
10
15 15
11 108 6
3
8 11 5
11
112 10
8
6 8
14
12 10
3929
*36
*39
*36
* 29
* ADCBA
ACDBA
ACBDAABCDAABDC
AABDC
ABDC ABCD ACDB ADCB
ADBCADC ADB
ACDACBABCABD AB
AD
6.4-rasm. Masalaning holatlar grafi.ushbu mezonni qanoqtlantiruvchi optimal operatorlar ketma-ketligini izlash
masalasiga keltiriladi.
HFda echimlarni izlash usullarini holatlar daraxti(grafi)dan foydalanib
tavsivlash qulay hisoblanadi. Holatlar daraxtida echimlarni izlash masalasi daraxt
ildizidan maqsadli holatga mos tugungacha bo’lgan yo’lni (optimalli, agar optimallik
mezoni berilgan bo’lsa) topishga keltiriladi.
Umumiy holda holatlar daraxtini (S0 ,F,G) uchlik ko’rinishda berish mumkin.
Bu erda
S0−¿ bitta elementdan iborat to’plam , F- operatorlar to’plami, G-maqsadli
holatlar to’plami.
Holatlar daraxtini qurish quyidagicha amalga oshiriladi: avvalo daraxt
ildiziga(boshlang’ich holat) F dagi operatorlarni qo’llab 1-pog’onali tugunlar
quriladi; Keyin, F dagi operatorlardan 1-pog’onali tugunlarga qo’llaniladiganlaridan
foydalanib 2-pog’onali tugunlar
quriladi va h.k. Ushbu
protsedura maqsadli tugunni
topguncha davom ettiriladi.
Misol. Yuk tashuvchi robot
A punktdan chiqib, (B, C, D)
punktlarning har birida faqat bir
martadan bo’lib, yana A
punktga qaytib kelishi kerak.
Punktlar orasidagi masofalar va
marshrutlar sxemasi 6.3-rasmda
keltirilgan.
Marshrutni tanlash masalasi uchun HFda echimlarni izlash 6.4-rasmda
keltirilgan [1].
5 ADBCA

Ushbu grafda boshlang’ich tugunga A holat mos keladi. A tugun AB, AC, AD
holatlarga mos keluvchi uhta 1-pog’onali ichki tugunlarni hosil qiladi. 1-pog’onali
AB, AC, AD ichki tugunlar 2-pog’onali ichki tugunlarni hosil qiladi va h.k.
Grafda tugunlarning ochilish tartibi izlash strategiyasi deb ataladi.
3.2.2. Chuqurligi bo’yicha izlash strategiyasi
Masalani echishning ba’zi strategiyalrini qarab chiqamiz. Graflarda hal qiluvchi
yo’llarni qurishga yo’naltirilgan bir qator strategiyalar masalani echishda baholash
funksiysi(BF)ga asoslanadi. BF grafning tugunlarida aniqlanadi va haqiqiy
qiymatlarni qabul qiladi. Ixtiyoriy tugun uchun hosil qilingan BF qiymati ushbu
tugundan hal qiluvchi yo’lni davom ettirish kerakligi yoki yo’qligini aniqlaydi.
Masalani BFni hisoblash asosida echish strategiysi evristik izlashning bir
ko’rinishi hisoblanadi.
BFni hisoblash asosida masalani echishning boshqa strategiyalariga chuqurligi
bo’yicha izlash va kengligi bo’yicha izlash kiradi. Chuqurligi bo’yicha izlashda
ixtiyoriy tugunning baholash funksiyasi qiymati ushbu tugundan boshlang’ich
tugungacha bo’lgan masofaga to’g’ri proportsional bo’ladi. Kengligi bo’yicha
izlashda bu bog’lanish teskari proportsional bo’ladi.
Tugunlarning chuqurligi deganda tugunlarning pog’onalari tartib raqamiga
teng bo’lgan son tushuniladi.
Quyida masalani echishning boshqa strategiyalarini keltiramiz .
1) Shoxlar va chegaralar usuli. Qidirish jarayonida tugamagan yo’llardan eng
qisqasi tanlab olinadi va bir qadamga uzaytiriladi. Hosil qilingan yangi tugamagan
yo’llar (mazkur tugunda qancha shox bo’lsa ularning soni ham shuncha bo’ladi)
eskilari bilan bir qatorda ko’riladi va yana ulardan eng qisqasi bir qadamga
uzaytiriladi. Jarayon birinchi maqsadli tugunga yetguncha takrorlanadi va yechim
saqlanadi. So’ngra qolgan tugamagan yo’llardan tugagan yo’lga nisbatan uzunroq
yoki unga teng yo’llar olib tashlanadi, qolganlari esa xuddi shunday algoritm
bo’yicha ularning uzunligi tugagan yo’lnikidan katta bo’lguncha uzaytiriladi.
Natijada yo barcha tugamagan yo’llar olib tashlanadi, yo ular orasidan oldingi
olingan yo’ldan qisqaroq bo’lgan yo’l shakllanadi. Oxirgi yo’l etalon hisoblanadi va
h.k.
2) Murning qisqaroq yo’llarni topish algoritmi. Boshlang’ich X
0 tugun 0 soni
bilan belgilanadi. Algoritm ishlash jarayonining boshlang’ich qadamida X
i tugunning
tarmoq tugunlar to’plami X(X
i ) olingan bo’lsin. U holda oldin olingan barcha
tugunlar undan o’chiriladi, qolganlari esa x
i tugunning nishoniga qaraganda bir
birlikka oshirilgan nishon bilan belgilanadi va ulardan X
i ga tomon ko’rsatkichlar
o’tkaziladi. Keyin hali ko’rsatkichlar manzili sifatida qatnashmaydigan belgilangan
tugunlar to’plamida eng kichik nishonli tugun olinadi va u tugun uchun
tarmoqlanuvchi tugunlar quriladi. Tugunlarni belgilab chiqish maqsadli tugun hosil
qilinguncha takrorlanadi.
Minimal qiymat bilan yo’lni aniqlashning Deykstr algoritmi o’zgaruvchan
uzunlikdagi yoyni kiritish hisobiga Mur algoritmining umumlashmasi hisoblanadi.
6

3) Doran va Mitchining past baho bilan qidirish algoritmi . Qidirish bahosi
optimal yechimning bahosiga nisbatan katta bo’lgan holda ishlatiladi. Bu holda Mur
va Deykstr algoritmlaridagiday boshidan eng kam uzoqlikda joylashgan tugunni
tanlash o’rniga maqsadgacha bo’lgan masofaning evristik bahosi eng kam bo’lgan
tugun tanlanadi. Yaxshi baholashda yechimni tez hosil qilish mumkin, ammo
yo’lning minimalligiga kafolat berilmaydi.
4) Xart, Nilson va Rafael algoritmi . Algoritmda ikkala kriteriya birlashtirilgan:
g(x) tugungacha bo’lgan yo’l narxi (bahosi) va h(x) tugundan additiv baholanadigan
f{x}=g(x)-h(x) funksiyagacha bo’lgan yo’l narxi hisoblanadi. h(x)<hp(x) shartda (bu
yerda hp(x) maqsadgacha bo’lgan haqiqiy masofa) algoritm optimal yo’lni topishga
kafolat beradi.
Grafda yo’llarni qidirish algoritmlari qidirish yo’nalishi bilan ham farq qiladi.
To’g’ri, teskari va ikki tomonga yo’nalgan qidirish usullari mavjud. To’g’ri izlash
boshlang’ich holatdan ketadi va maqsad holat oshkormas holda berilganda
qo’llaniladi. Teskari qidirish maqsadli holatdan ketadi va boshlang’ich holat oshkor
berilmagan, maqsadli holat oshkor berilgan holda qo’llaniladi. Ikki tomonga
yo’nalgan qidirish ikkita muammoning qoniqarli yechimini talab qiladi: qidirish
yo’nalishining almashishi va «uchrashuv nuqta»sini optimallashtirish. Birinchi
muammoni yechish kriteriyalardan biri qidirish «kengligi»ni ikkala yo’nalishda
taqqoslashdan iborat. Qidirishni toraytiradigan yo’nalish tanlanadi. Ikkinchi
muammoning yuzaga kelishiga sabab to’g’ri va teskari yo’llar ajralib ketishi mumkin
va qidirish qancha tor bo’lsa uning ehtimoli ko’proq bo’ladi.
5) Cheng va Sleyg algoritmi . Ixtiyoriy VA/YOKI grafni har bir YOKI shoxi
faqat oxirida VA tugunga ega maxsus YOKI grafga aylantirishga asoslangan.
Ixtiyoriy VA/YOKI grafni muloxazalar mantiqining ixtiyoriy formulasiga aylantirish
va keyin bu formulani diz’yunktiv normal shaklga keltirishdan foydalanib aylantirish
amalga oshiriladi. Bunday aylantirish keyinchalik Xart, Nilson va Rafael
algoritmlaridan foydalanishga imkon beradi.
6) Kalit operatorlar usuli. <A,B> masala berilgan bo’lsin va f operator albatta
bu masalaning yechimiga kirishi ma’lum bo’lsin. Bunday operator kalit operator deb
ataladi. f ni qo’llash uchun S holat kerak bo’lsin, uni qo’llash natijasi esa I(c) bo’lsin.
U holda VA tugun uchta tarmoq tugunlarni keltirib chiqaradi: <A,C>, <C,f{c}> va
<f(c),B>. Ulardan o’rtadagisi elementar masala hisoblanadi. <A,C> va <f(c),B>
masalalar uchun ham kalit operatorlar tanlanadi va ko’rsatilgan reduksiyalash
prosedurasi mumkin bo’lgunga qadar takrorlanadi. Natijada <A,B> boshlang’ich
masala har biri HFda rejalashtirish usuli bilan yechiladigan masala ostilarining
tartiblangan majmuiga ajratiladi. Kalit operatorlarni tanlashda alternativlar bo’lishi
mumkin, shuning uchuun umumiy holda VA/YoKI graf sodir bo’ladi. Ko’pgina
masalalarda kalit operatorni ajratishga erishilmaydi, faqatgina uni o’z ichiga oladigan
to’plamni ko’rsatishga erishiladi. Bu holda <A,B> masala uchun A va V ning farqi
hisoblanadi. Oxirgisi kalit operator bo’ladi.
7) Umumiy masala yechuvchi(UME)ni rejalashtirish usuli. UMEni
rejalashtirish eng mashxur model sifatida paydo bo’lgan. U integral hisob, mantiqiy
xulosa, grammatik tahlil va shu kabi boshqa masalalarni yechish tuchun ishlatilgan.
7

UME qidirishning ikkita asosiy prinsiplarini birlashtiradi: maqsadlarni va vositalarni
tahlil qilish va masalani rekursiv yechish. Qidirishning har bir siklida UME uchta
turdagi standart masalalarni qat’iy ketma-ketlikda yechadi: A obyektni B obyektga
almashtirish, A va B orasidagi D farqni kamaytirish, f operatorni A obyektga
qo’llaydi.
8) Mantiqiy xulosa asosida rejalashtirish. Bunday rejalashtirish holatlarni
qandaydir mantiqiy hisobning to’g’ri qurilgan formulalari (TQF) ko’rinishida
tavsiflashni; operatorlarni yoki TQF ko’rinishda yoki bir TQFni boshqasiga o’girish
qoidalari ko’rinishida tavsiflashni taqozo etadi. Operatorlarni TQF ko’rinishida
tasvirlash rejalashtirishning deduktiv usullarini yaratishga imkon beradi, operatorlarni
o’girish qoidalari ko’rinishida tasvirlash esa deduktiv xulosa elementlari bilan
rejalashtirish usullarini yaratishga imkon beradi.
Chuqurligi bo’yicha izlash strategiyasini faqat tugunlar N = { n
1 , n
2 , …, n
r }
ro’yxati va yoylar L = { l
1 , l
2 , …, l
s } ro’yxatidan iborat HFberilganda qo’llash
maqsadga muvofiq. Bu erda l
k = ( n
ik , n
jk ) qirralar bo’lib, n
ik tugundan n
jk tugunga
yo’naltirilgan bo’ladi.
Chuqurligi bo’yicha izlash algoritmining g’oyasi quyidagidan iborat: grafning
boslang’ich tuguni yo’lning bo’shlanish tuguni sifatida qabul qilinadi.Undan keyin
boshlang’ich tugundan chiqadigan bir qancha alternativ tugunlardan boshlang’ich
tugundan eng uzoqda (uzunligi bo’yicha) joylashgan tugun tanlanadi. Navbatdagi
tugunlararni tanlash, xuddi boshlang’ich tugundagidek, o’zidan oldingi tugunga
nisbatan eng uzoqda joylashgan tugunni tanlash bilan davom ettiriladi. Tugunlarni
tanlash algoritm bo’yicha maqsadga erishuvchi yo’lni topishgacha davom ettiriladi.
Chuqurligi bo’yicha birma-bir izlash algoritmi [1, 5-7] . Tugunlarning
chuqurligi - tugunlarning pog’onalari tartib raqamiga teng bo’lgan son bilan
aniqlahadi. Chuqurligi bo’yicha birma-bir izlash algoritmida tugunlar orasidan eng
katta chuqurlikga ega bo’lgan tugunlar ochiladi. Bunda bir xil chuqurlikga ega
bo’lgan bir nechta tugunlardan bittasi tanlanadi. Bundan tashqari, odatda ba’zi
mulohazalarga ko’ra tugunlarning chegaravuy chuqurliklari beriladi. Bu holda
tugunlar orasidan, tygunlari chuqurliklari chegaraviy chuqurlikga teng bo’lganlari
ochilmaydi.
Shunday qilib, chuqurligi bo’yicha birma-bir izlash algoritmida tugunlar
orasidan, tygunlar chuqurliklari chegaraviy chuqurlikdan kichchik bo’lgan tugunlar
ochilmaydi.
Chuqurligi bo’yicha birma-bir izlash algoritmini strukturalashgan holda
qaraymiz:
1) Boshlang’ich tugunni «ochiq» royxatiga joylashtirish;
2) Agar «ochiq» royxati bo’sh bo’lsa, u holda 1-qadamga, aks holda 3-qadamga
o’tiladi;
3) «Ochiq» royxatidan birinch tugunni olish va uni «yopiq» royxatiga o’tkazish
va unga v nomni berish;
4) Agar v tugunning chuqurligi chegaraviy churlikga teng bo’lsa, u holda 2-
qadamga o’tish, aks holda 5-qadamga o’tish;
8

5) v tugunni ochish. v tugunning barcha ichki tugunlarini «ochiq» royxatining
boshiga joylashtirish va barcha ichki tugunlardan v tugunga keladigan
ko’rsatkichlarni qurish; Agar v tugun ichki tugunlarga ega bo’lmasa, u holda 2-
qadamga o’tish;
6) Agar ushbu tugunlardan birortasi maqsadli echimni hosil qilsa, u holda
chiqishda echimni hosil qilish, aks holda 2-qadamga o’tish.
Qaralgan algoritmda boshlang’ich tugun sifatida faqat bitta tugun qatnashadi.
Agar boshlang’ich tugunlar bir nechta bo’lsa, u holda algoritmning 1-qadamidagi
«ochiq» royxatiga barcha boshlang’ich tugunlar joylashtiriladi.
Misol. Misol sifatida marshrutni tanlash masalasi uchun HFda echimlarni
izlashda A, AD, ADC, ADCB, ADCBA optimal marshrutni keltirish mumkin ( 6.3,
6.4-rasmlar).
Ta’kidlash lozimki, echimni c huqurligi bo’yicha izlashda eng chuqurlikga ega
bo’lgan tugunlar bir nechta bo’lsa, u holda ular orasidan eng chapdagisi tanlanadi.
Agar echimni izlash tupikli holatga kelib qolsa , ya’ni joriy tugun maqsadli
echimga olib kelmasa va uning chuqurroq tugunlar bilan aloqasi bo’lmasa, u holda
oldingi tugunga qaytiladi va ushbu tugundan echimni c huqurligi bo’yicha izlash
davom ettiriladi.
Misol. 6.5, а -rasmda HFda echimni c huqurligi bo’yicha izlashda qanday
tugunlardan foydalanish kerakligi ko’rsatilgan. Bu erda a boshlang’ich, j va f oxirgi
holatlarga mos keladi.
Ajratilgan [ a , b , e , j ] va [ a , c , f ] yo’llar – bu topilgan hal qiluvchi yo’llar, [ a , c , f ]
yo’l esa – hal qiluvchi qisqa yo’l hisoblanadi.
HFda echimni c huqurligi bo’yicha izlash ko’p hollarda 6.5, а -rasmda
ko’rsatilgandek yaxshi ishlaydi . Ba’zi hollarda u to'xtash holatiga ham tushib qolishi
mumkin, masalan, sikllanish holatiga tushishi mumkin. Masalan 6.5, б –rasmda
sikllanish holatlari [ d , h , d ] va [ b , e , i , b ] keltirilgan.
6.5-rasm. Chuqurligi bo’yicha izlash strategiyasi.
9a)
b)

3.2.3. Kengligi bo’yicha izlash strategiyasi
Kengligi bo’yicha izlash algoritmining g’oyasi quyidagidan iborat: grafning
boslang’ich tuguni yo’lning bo’shlanish tuguni sifatida qabul qilinadi.Undan keyin
boshlang’ich tugundan chiqadigan bir qancha alternativ tugunlardan boshlang’ich
tugunga yaqin (uzunligi bo’yicha) joylashgan tugun tanlanadi. Navbatdagi
tugunlararni tanlash, xuddi boshlang’ich tugundagidek, o’zidan oldingi tugunga
nisbatan eng yaqin joylashgan tugunni tanlash bilan davom ettiriladi. Tugunlarni
tanlash algoritm bo’yicha maqsadli echimga erishuvchi yo’lni topishgacha davom
ettiriladi.
Ta’kidlash lozimki , echimni kenglik bo’yicha izlashda boshlang’ich tugunga
yaqin bo’lgan tugunlar bir nechta bo’lsa, u holda ular orasidan eng chapdagisi
tanlanadi.
Agar echimni izlash tupikli holatga kelib qolsa , ya’ni joriy tugun maqsadli
echimga olib kelmasa va uning chuqurroq tugunlar bilan aloqasi bo’lmasa, u holda
oldingi tugunga qaytiladi va ushbu tugundan echimni kengligi bo’yicha izlash davom
ettiriladi.
Misol. 6.6 -rasmda HFda echimni kengligi
bo’yicha izlashda qanday tugunlardan
foydalanish kerakligi ko’rsatilgan. Bu erda a
boshlang’ich, j va f oxirgi holatlarga mos keladi.
Ajratilgan [ a , c, f] – bu birinch topilgan hal
qiluvchi yo’l bo’lib, u qisqa yo’l hisoblanadi.
Ikkinchi hal qiluvchi yo’l [ a , b, e, j] bo’lib, u
to’liq birma-bir tekshirish orqali hosil qilinadi.
Misol. Qisqa yo’l haqudagi masala . Qisqa
yo’l bilan grafning bir tugunidan boshqa tuguniga
qanday borish mumkin? Ishlab chiqarishni
boshqarish masalalarida: qisqa 6.6-
rasm. Kengligi bo’yicha
yo’l bilan (masalan, eng kam yoqilg’i va vaqt, izlash strategiyasi.
ancha orzon) А punktdan Б punktga qanday borish mumkin? Bu masalani echish
uchun yo’naltirilgan grafning boshlang’ich tugunidan oxirgi tugunigacha bo’lgan har
bir yoyiga harakat vaqtini ifodalovchi son mos qo’yiladi (6.7-rasm).
6.7-rasm. Qisqa yo’l haqudagi masalauchun boshlang’ich qiymatlar.
105 2
1
21 2
4
6 5
7
1 4
3
3 5
3

Boshlang’ich qiymatlarni 6.1-jadval ko’rinishda ham berish mumkin.
6.1-jadval. Qisqa yo’l haqudagi masalauchun boshlang’ich qiymatlar.
Yoyning boshi Yoyning oxiri Yo’ldagi vaqt
1 2 7
1 3 1
2 4 4
2 6 1
3 2 5
3 5 2
3 6 3
5 2 2
5 4 5
6 5 3
Talab qilinadi : qanday qisqa yo’l bilan 1–tugundan 4 – tugunga borish
mumkin?
Echimi . Quyidagi belgilashni kiritamiz : С ( Т ) – 1- tugundan T- tugungacha
qisqa yo’lning uzunligi. Qaralayotgan masalada 1- tugundan 4- tugungacha bo’lgan
С (4) qisqa yo’lni hisoblash talab etiladi.
6.7-rasmda va 6.1-jadvalda keltirilgan boshlang’ich qiymatlarni hisobga olsak,
u holda 1-tugundan 3-tugunga uning uzunligi 1 ga teng bo’lgan faqat bitta
yo’naltirilgan yoy chiqayapti, shuning uchun С (3)=1. Bundan tashqari, ko’rinib
turibdiki С (1)=0.
4-tugunga uzunligi 4 ga teng bo’lgan 2-tugundan yoki uzunligi 5 ga teng
bo’lgan 5-tugundan borish mumkin. Shuning uchun quyidagi munosabat o’rinli
С (4) = min { С (2) + 4; С (5) + 5}.
Demak, С (4) ni topish uchun avval С (2) va С (5) ni topish talab etiladi.
5-tugunga uzunligi 2 ga teng bo’lgan 3-tugundan yoki uzunligi 3 ga teng
bo’lgan 6-tugundan borish mumkin. Shuning uchun quyidagi munosabat o’rinli
С (5) = min { С (3) + 2; С (6) + 3}.
Bilamizki, С (3) = 1. Shuning uchun
С (5) = min {1+2; С (6) + 3}= min {3 ; С (6) + 3}. (6.1)
6-tugunga uzunligi 3 ga teng bo’lgan 3-tugundan yoki uzunligi 1 ga teng
bo’lgan 2-tugundan borish mumkin. Shuning uchun quyidagi munosabat o’rinli
С(6) = min { С(3)+3; С(2) +1}= min {4 ; С(2) +1}. (6.2)
2- tugunga uzunligi 7 ga teng bo ’ lgan 1- tugundan yoki uzunligi 5 ga teng
bo ’ lgan 3- tugundan yoki uzunligi 2 ga teng bo ’ lgan 5- tugundan borish mumkin .
Shuning uchun quyidagi munosabat o’rinli
С(2) = min {С(1) + 7; С(3) + 5 ; С(5) + 2}.
Bizga ma ’ lumki С(1) = 0, С(3) = 1, С(5) = 3. Shuning uchun
С (2) = min {0 + 7; 1 + 5 ; 3 + 2} = 5. (6.3)
(6.3) ni hisobga olsak
С (6) = min {4; С (2) +1}= min {4 ; 5+1}=4. (6.4)
(6.4) ni hisobga olsak, (6.1) dan
С (5) = min {3; С (6) + 3}= min {3 ; 4+ 3}=3.
11

Endi С (4) ni topish mumkin:
С (4) = min { С (2) + 4; С (5) + 5} = min {5 + 4; 3 + 5} = 8. (6.4)
Shunday qilib, 1-tugundan 4-tugungacha bo’lgan qisqa yo’lning uzunligi 8.
(6.5) munosabatdan ma’lumki, 4-tugunga 5-tugundan borish kerak. 5-tugunga 3-
tugundan borish kerak. 3-yugunga esa faqat 1-tugundan birish mumkin. Demak, qisqa
yo’l:
1 → 3 → 5 → 4 .
6.7-rasmda va 6.1-jadvalda keltirilgan boshlang’ich qiymatlar uchun qisqa yo’lni
toppish masalasi to’liq echildi.

3.2.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-
12

betta algoritm, dinamik programmalash, shoxlar va chegaralar usuli, bo’linish va
baholash usulilarini kiritish mumkin .
Evristik izlashni namoyish etrish uchun namuna sifatida А * algoritmini
keltiramiz.
3.2.4.1. А * algoritmi
Bu algoritm HFko’rinishida berilgan tugunlar to’plamida evristik axborotlar
baholi funksiya shaklida ifodalanganda evristik izlashda qo’llaniladi. Aytaylik,
echiladigan masalaning HFni ifodalovchi grafda N = { n
1 , n
2 , …, n
r } –tugunlar
to’plami, L = { l
1 , l
2 , …, l
s } – yoylar to’plami berilgan bo’lsin. Ushbu grafdagi
ixtiyoriy L= (ni,n j)∈ L
yoy uchun ushbu yoyning bahosini ifodalovchi c ( n
i , n
j )
son aniqlangan bo’lsin.Dgar bir nechta maqsadli tugunlar mavjud bo’lsa, u holda
boshlang’ich tugunni n
0 , maqsadli tugunni esa t yoki t
i bilan belgilaymiz.

Baholash funksiyasi f( ּ ) ning qiymatini shunday aniqlaymizki , uning n
tugunlardagi qiymati f ( n ) ikkita qiymatlar yig’indisi bahosidan iborat bo’ladi:
1) boshlang’ich n
0 tugunlardan n
tugungacha bo’lgan yo’lning minimal bahosi;
2) n
tugunlardan qaysidir maqsadli t yoki t
i tugungacha bo’lgan yo’lning minimal
bahosi;
Agar birinchi bahoni g * ( n ) va ikkinchi bahoni h * ( n ) bilan belgilasak, u holda
f ( n ) baholsh funksiyasi f * ( n ) =g * ( n ) + h * ( n ).
g * ( n ) va h * ( n ) fynksiyalarni c ( n
i , n
j ) lar yordamida quyidagicha aniqlash
mumkin:
g¿(n)= min
{lα}n0
n ∑
lα∈{lα}n0n
c(niα,njα)
h¿(n)= min
lα
min
{lα}n0n ∑
lα∈{lα}n0n
c(niα,njα)
Bu erda formuladagi g * ( n ) uchun minimum boshlang’ich n
0 tugundan n
tugungacha bo’lgan barcha
{lα}n0
n
yo’llar bo’yicha hisoblanadi. Formuladagi h * ( n )
uchun tashqi minimum barcha maqsadli t
i tugunlar bo’yicha, ichki minimum esa
boshlang’ich n tugundan tugallanadigan maqsadli t
i tugungacha bo’lgan barcha
{lα}n
ti
yo’llar bo’yicha hisoblanadi.
{lα}m
n belgilash, boshlang’ich m tugundan n
tugallanadigan ixtiyoriy yo’l uchun foydalaniladi.
Umumiy holda baholash funksiyasini f ( n ) = g ( n ) + h ( n ),
aniqlash mumkin, bu erda g ( n ) funksiy - g * ( n ) funksiyalarning qandaydir bahosi
(yaqinlashish), h ( n ) funksiy esa - h * ( n ) funksiyalarning qandaydir bahosi
13

$7 33 6.8-rasm(yaqinlashish). g ( n ) funksiyning bahosi sifatida n 0 tugunlardan n tugungacha bo’lgan{lα}n0 n yo’llardagi yoylar bahosining yig’imdisi, ya’ni g(n)= ∑ lα∈{lα}n0n c(niα,njα). Barcha maqsadli bo’lmagan tugunlar uchun h(n)≤ h∗(n) shatni qanoatlantiruvchi baholash funksiyasi f ( n ) = g ( n ) + h ( n ), А * algotitmi deb ataladi. Barcha maqsadli bo’lmagan tugunlar uchun h(n)≤ h∗(n) shat qatnashmasa baholash funksiyasi f ( n ) = g ( n ) + h ( n ), А algotitmi deb ataladi . А va А * algoritmlarida g ( n ) funksiy g * ( n ) funksiyalarning qandaydir bahosi hisoblanadi. Ikkala algoritmda ham tugunlarni izlashni davom ettirish uchun alternativ tugunlar orasidan f ( n ) funksiyaning eng kichchik qiymatiga mos keladigan tugun tanlanadi. Misol. Aitaylik izlashning 1-qadamida S0 tugun ochilgan bo’lsin va undan yo’lning baholash qiymatlari ^ g( V 1 ) = 3 va ^ g( V 2 ) = 7 ega bo’lgan V 1 va V 2 tugunlar chiqqan bo'lsin. 2-qadamda V1 tugun ochiladi va undan V 3 va yana V 2 tugun chiqadi, bunda V 1 tugundan V 2 tugunga olib boruvchi yolning baholash funksiyasi qiymati qiymatlari ^g(V1)=3 . Ko’rinib turibdiki, S0 tugundan V2 tugungacha bo;lgam qisqa yo’lning bahosi ^ g( V 2 ) = 6 (6.8-rasm). Ta’kidlash joizki, ^ g( V ) = 7 ≥ g ( V ) = 6 . Misol. Aytaylik , A, B, S, D, E, F zavodlar va ular orasidagi yo’l masofalari berilgan bo’lsin (6.9-rasm). Biz A zavoddan F zavodga kelishimiz kerak. Zavodlar orasidagi masofa ikki yoqlama, ya’ni xarakat ikki tomonga ham yo’naltirilgan bo’lishi mumkin. 14$