Nima uchun birinchi keng izlash birinchi chuqurlikdan ko'ra ko'proq xotiradan foydalanadi?



Download 63.5 Kb.
Sana15.05.2021
Hajmi63.5 Kb.

Nima uchun birinchi keng izlash birinchi chuqurlikdan ko'ra ko'proq xotiradan foydalanadi?

Men bu savolga onlayn javob topolmayman va shunga o'xshash savollarga berilgan boshqa javoblarda shunchaki DFSning afzalligi shundan iboratki, u DFS-ga qaraganda kamroq xotiradan foydalanadi.

Menimcha, bu men kutganimning aksi. BFS faqat tashrif buyurgan so'nggi tugunni saqlashi kerak. Masalan, agar biz quyidagi daraxtda 7 raqamini qidirsak:

bu erda rasm tavsifini kiriting

U 8, so'ngra 3, 10, 1, 6, 14, 4 qiymatlari bilan tugunni qidiradi, so'ngra yakuniy 7. DFS uchun u 8, so'ngra 3, 1, 6, 4, so'ngra 7 qiymatiga ega tugunni qidiradi. .

Agar har bir tugun xotirada saqlanib qolsa, uning qiymati, uning bolalari va daraxtning holati to'g'risidagi ma'lumotlar mavjud bo'lsa, unda BFS dasturi faqat tashrif buyurgan so'nggi tugunning holati to'g'risidagi ma'lumotlarni saqlashi kerak, keyin u tekshirishi mumkin. daraxt va daraxtning keyingi tugunini toping. DFS dasturi oxirgi tugunni, shuningdek, allaqachon tashrif buyurgan barcha tugunlarni saqlashi kerak, shunda ularni qaytadan tekshirib bo'lmaydi va shunchaki ikkinchi avlod tugunlariga o'tadigan barcha barg tugunlarini aylanib o'tadi.

Xo'sh, nima uchun BFS aslida kam xotiradan foydalanadi?

4 ta oltin nishon

● 16

16 ta kumush nishon



● 40

40 bronza nishon

17

qabul qilindi



Har qanday qidiruv usulini yozish mumkin, shunda u faqat oldingi tugunni kuzatib borishi kerak, ammo keyin DFS BFS-ga qaraganda samaraliroq bo'ladi.

Yaqin atrofda ko'proq tugun bor-yo'qligini bilish uchun DFS bir vaqtning o'zida bitta darajani bosib o'tishi kerak. Bularning barchasini qidirish uchun tugunlar bo'ylab harakatlanish kerak edi:

8-3-1-3-6-4-6-7-6-3-8-10-14-13-14-10-8

BFS daraxtning boshqa yarmiga borganda, yuqoriga va pastga qarab yuqoriga qarab yurishi kerak. Bu tugunlar orqali quyidagi tartibda harakat qilar edi:

8-3-8-10-8-3-1-3-6-3-8-10-14-10-8-3-1-6-4-6-7-6-3-8-10-14-13-14-10-8

(Bo'lsa-bo'ladimi, aniq emasman, lekin oxirgi darajadagi tugunlar yo'qligini bilish uchun hatto bir necha bor yuqoriga va pastga yurishga to'g'ri keladi.)

Ko'rib turganingizdek, agar siz minimal xotirani ishlatadigan algoritmni amalga oshirishni istasangiz, BFS juda kam samaralidir.

Agar siz algoritmlarni samaraliroq qilish uchun ko'proq xotiradan foydalanishni istasangiz, ular deyarli bir xil samaraga ega bo'ladilar, asosan har bir tugunni bir marta bosib o'tadilar. DFS kamroq xotiraga muhtoj, chunki u faqat yuqoridan pastgacha zanjirdagi tugunlarni kuzatishi kerak, BFS esa barcha tugunlarni bir xil darajada ushlab turishi kerak.

Masalan, 1023 tugunli (muvozanatli) daraxtda DFS 10 tugunni, BFS esa 512 tugunni kuzatishi kerak.

BFS har doim ham ko'proq xotiradan foydalanmaydi. Sizda bor daraxt, xususan, yo'q joyda namuna bo'ladi.



Ushbu daraxtni ko'rib chiqing: ( manba )

BFS bilan, ba'zi bosqichlarda, 8-15 yoshdagi barcha tugunlar xotirada qoladi.

DFS bilan siz hech qachon xotirada 4 tadan ortiq tugunga ega bo'lmaysiz (daraxt balandligiga teng).

Daraxt kattalashib borgan sari (u to'liq to'lguncha) farq yanada yomonlashadi.

Aniqrog'i, BFS faqat DFS foydalanadigan joyda O(branchingFactor^maxDepth)yoki O(maxWidth)xotirada ishlaydi O(maxDepth).

Agar maxWidth < maxDepth, BFS kam xotiradan foydalanishi kerak (agar siz ikkala uchun ham shunga o'xshash tasvirlardan foydalansangiz, deb taxmin qilamiz), ammo bu kamdan-kam hollarda haqiqatdir.



Umuman olganda, u aniq grafikka bog'liq bo'lishi yoki bo'lmasligi mumkin.

Chuqurlik bo'yicha qidiruvda ildizdan qidirilayotgan tugungacha tugunlari bo'lgan stack ishlatiladi. Shunday qilib, grafikning eng ko'p radiusi.

Kenglikdagi birinchi qidiruv qidirishning old qismida tugunlarni o'z ichiga olgan navbatdan foydalanadi. Shunday qilib, d masofadagi barcha tugunlar .

Umumiy grafikada aytishingiz mumkinki, bu har ikkala holatda ham daraxtning barcha tugunlari.

Agar bor bo'lsa, lekin bir (yoki asosan, shuning uchun) muvozanatli k faqat O (log (bo'ladi, ya'ni radiusi -ary daraxtga, u ning chuqurligi, n eng past qatlami u (o'z ichiga oladi esa,)) n tugunlari) ( n / 2 ikki tomonlama uchun daraxt va undan yuqori darajalar uchun).



Shunday qilib, birinchi chuqur qidiruv faqat O (log ( n )) xotirasidan foydalanadi va kenglikdagi birinchi qidirishda O ( n ) ishlatiladi. Muvozanatli k -ary daraxtlari uchun; boshqa holatlar uchun har xil natijalar bo'lishi mumkin (lekin ko'pchilik uchun keng tarqalgan grafiklar uchun diametri halqadan ancha kam bo'ladi).
Download 63.5 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2020
ma'muriyatiga murojaat qiling

    Bosh sahifa
davlat universiteti
ta’lim vazirligi
O’zbekiston respublikasi
maxsus ta’lim
zbekiston respublikasi
axborot texnologiyalari
o’rta maxsus
davlat pedagogika
nomidagi toshkent
guruh talabasi
pedagogika instituti
texnologiyalari universiteti
toshkent axborot
xorazmiy nomidagi
rivojlantirish vazirligi
samarqand davlat
haqida tushuncha
navoiy nomidagi
toshkent davlat
nomidagi samarqand
ta’limi vazirligi
Darsning maqsadi
vazirligi toshkent
Toshkent davlat
tashkil etish
kommunikatsiyalarini rivojlantirish
Ўзбекистон республикаси
Alisher navoiy
matematika fakulteti
bilan ishlash
Nizomiy nomidagi
vazirligi muhammad
pedagogika universiteti
fanining predmeti
таълим вазирлиги
sinflar uchun
o’rta ta’lim
maxsus ta'lim
fanlar fakulteti
ta'lim vazirligi
Toshkent axborot
махсус таълим
tibbiyot akademiyasi
umumiy o’rta
pedagogika fakulteti
haqida umumiy
Referat mavzu
fizika matematika
universiteti fizika
ishlab chiqarish
Navoiy davlat