qadam qadam qadam




Download 0,86 Mb.
bet3/11
Sana21.12.2023
Hajmi0,86 Mb.
#125713
1   2   3   4   5   6   7   8   9   10   11
Bog'liq
Fayllar tizimida ishlash test, pedagogik texnalogiya, HTML QOLLANMA, kenguru 2012 class 2, 3 kurs ekanomika, Kompyuter kimyo, Raqamli hisoblash mashinasi - Vikipediya, Sana 14-mart Sinf 8,,B’’ Fan Chizmachilik Mavzu Modelning be, 00 Бизнес режа нима, jadval bo`yicha, optika, bayonnoma 2 ko`chirma, Asinxron mashinalar, 2022 Fermentlar maruza (2), Academic-Data-341201109566 (1)
qadam



  1. qadam





  1. qadam



  1. 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.

  1. 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.

Download 0,86 Mb.
1   2   3   4   5   6   7   8   9   10   11




Download 0,86 Mb.