|
qadam
qadam
qadam
|
| bet | 3/11 | | Sana | 21.12.2023 | | Hajmi | 0,86 Mb. | | #125713 |
qadam
qadam
qadam
qadam
va hakozo
Algoritmni ishlash vaqti:
Barcha uchlar va barcha qirralar ko‘rib chiqiladi. Demak, algoritmning umumiy ishlash vaqti O(n+m).
Bu yerda n – uchlar soni, m – qirralar soni.
Agar bog‘lanishlar qo‘shnilik matritsasida berilsa u holda O(n2)
Algoritmni qo‘llasnilishi:
grafning komponentalarni aniqlash.
leksikografik tartibdagi birinchi yo‘lni aniqlash.
grafni ikki rangga bo‘yash.
grafda ajralish nuqtalarini topish.
grafda ko‘ptiklarni topish.
kun algoritmida(grafni maksimal juftliklarga ajratish).
Ierarxik grafda bir uch ikkinchi uchning ajdodi ekanligini yoki eng kichik umumiy ajdodni(LCA) tezkor topish.
Agar ko‘proq ma’lumotlarni bilmoqchi bo‘lsangiz, «Искуственный интеллект: современный » (Styuart Rassel, Piter Norvig) kitobini o‘qishni tavsiya qilamiz.
Axborotli (ma’lumotli) izlash algoritmi [10,11]. Axborotli izlash strategiyasi ,umuman olganda, yechimni izlashni ancha samarali ta’minlaydi. Bunday algoritmlarning umumiy prinsipi – birinchi mos tushishni izlash (Best- First-Search).
Ochko‘z izlash birinchi eng yaxshi mos kelish bo‘yicha, yoki ochko‘z izlash “birinchi – yaxshi”, ko‘p jihatdan chuqurlik bo‘yicha izlash algoritmiga o‘xshash, ammo u shunday tugunni tanlaydiki, u boshlang‘ich nuqtaga yaqin bo‘ladi. Bu algoritmda shunday bir baholash funksiyasi (evristik) mavjud, ko‘rilayotgan tugun maqsadga yetish tugunidan qanchalik uzoq ekanligini ifodalovchi. Bu algoritm ham chuqurlik bo‘yicha izlash algoritmi kabi optimal emas, bundan tashqari to‘liq emas.
Turli evristik baholash funksiyalariga ega bo‘lgan algoritmlar oilasi mavjud. Algoritmlarning bir-biridan farqlanishi ifodalanadigan evristik funksiyalarga bog‘liq, ya’ni h(n): h(n) = biror tugundan p tugunga boradigan yo‘lni yuqori qiymatli bahosi. Misol tariqasida ochko‘z izlash algoritmini (A* algoritmni) ko‘rib chiqamiz.
Masalaning qo‘yilishi. Quyidagi grafda (1-rasm) A tugundan J tugungacha bo‘lgan eng qisqa va eng kam qiymatli yo‘lni izlash zarur.
Maqsad. Yechimning umumiy bahosini qiymatini minimallashtirish. A* izlash – eng yaxshi mos keladigan eng mashhur izlash algoritmi. Algoritmning samaradorligi baholash funksiyasi bilan xarakterlanadi – har bir qadamda algoritm ancha ratsional yechimni qabul qiladi. Matematik ko‘rinishda quyidagicha ifodalash mumkin:
f(n) = biror tugundan p tugunga boradigan yo‘lning yuqori qiymatli bahosi.
f(n) = g(n) + h(n), bu erad g(n) — birorta tugunga boradigan yo‘lning qiymati, h(n) — birorta tugundan maqsadgacha boradigan yo‘lning qiymati.
3
1-rasm
Algoritmni ishlashini qadamba -qadam ko‘rib chiqamiz.
qadam:
A tugundan harakatni boshlaymiz.
A tugundan B va F tugunga borish mumkin.
A* algoritm f(B) va f(F) larni qiymatini hisoblaydi.
f(B) = 6 + 8 = 14
f(F) = 3 + 6 = 9
f(F) < f(B) bo‘lgani uchun, F tugunga boriladi deb echim qabul qilamiz.
|
| |
