Axborotsiz (ma’lumotsiz) izlash




Download 0,86 Mb.
bet2/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)

Axborotsiz (ma’lumotsiz) izlash.


Odatda axborotsiz izlash masalasida beshta strategiya o‘rganiladi – bunda masalaning shartida berilgan axborotdan tashqari hech qanday axborot ishlatilmaydi. Axborotsiz izlashning beshta strategiyasi quyidagilar:

    • kenglik bo‘yicha izlash;

    • chuqurlik bo‘yicha izlash;

    • chuqurlikni cheklanganlik bo‘yicha izlash;

    • ketma-ket chuqurlashish bilan chuqurlik bo‘yicha izlash;

    • baho mezoni bo‘yicha izlash;

    • ikki yo‘nalishli izlash.

Kenglik bo‘yicha izlash (Breadth first search, BFS) algoritmini ko‘rib chiqamiz. Masalaning qo‘yilishi:

  • Kenglik bo‘yicha izlash algoritmi grafni o‘tib chiqish va eng qisqa yo‘l izlash metodi hisoblanadi.

  • Kiruvchi ma’lumotlar:

  • Graf, boshlang‘ich uch, oxirgi uch.

  • Maqsad: boshlang‘ich uchda oxirgi uchgacha boradigan eng qisqa yo‘lni topish.




Belgilash kiritamiz:






  1. qadam




  1. qadam




  1. qadam





  1. qadam




  1. qadam








  • Shuning bilan barcha uchlar va barcha bog‘lanishlar bir martadan ko‘rib chiqiladi. Natijada boshlang’ich uchga bo‘g’langan barcha uchlar ko‘rib chiqiladi.

  • Algoritm ishlash vaqti O(n+m). n – uchlar soni, m – bog’lanishlar soni.


Chuqurlik bo‘yicha izlash(inglizcha Depth-first search, DFS.



  • Chuqurlik bo‘yicha izlash (inglizcha Depth-first search, DFS) graflar nazariyasining eng muhim algoritmlaridan biri grafni o‘tib chiqish uchun qo‘llaniladi.

  • Chuqurlik bo‘yicha izlash algoritmi strategiyasi uning nomiga mos ravishda grafda chuqurlik bo‘yicha qancha borish mumkin bo‘lsa ,shuncha yuradi, toki yo‘l qolmagunga qadar.

Berilgan yo‘nalishli graf:


Tugunlar soni – 6 ta, qirralar soni – 9 ta. Tugunlarning bog‘lanishlari:


1-2, 1-3, 1-4, 3-4, 3-5, 4-2, 5-4, 5-6, 6-3.


Uchlarning holatlari:

15




  1. qadam




  1. qadam




  1. qadam




  1. qadam






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




Download 0,86 Mb.