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:
qadam
qadam
qadam
qadam
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
qadam
qadam
qadam
qadam
|
