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



Download 63,5 Kb.
Sana15.05.2021
Hajmi63,5 Kb.
#64192
Bog'liq
Nima uchun biri-WPS Office
Ma'lumotlar baz, Savollarga javoblar, Savollarga javoblar, Артикова иситкич, Артикова иситкич, Артикова иситкич, Ашурова ректиф колонна 50 тс, Ашурова ректиф колонна 50 тс, Katalitik kreking jarayonining sanoatdagi qurilmalari.13, Katalitik kreking jarayonining sanoatdagi qurilmalari.13, Katalitik kreking jarayonining sanoatdagi qurilmalari.13, PHONETICS 4, PHONETICS 4, Lesson 13

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 2022
ma'muriyatiga murojaat qiling

    Bosh sahifa
davlat universiteti
ta’lim vazirligi
axborot texnologiyalari
maxsus ta’lim
zbekiston respublikasi
guruh talabasi
O’zbekiston respublikasi
nomidagi toshkent
o’rta maxsus
davlat pedagogika
toshkent axborot
texnologiyalari universiteti
xorazmiy nomidagi
rivojlantirish vazirligi
Ўзбекистон республикаси
pedagogika instituti
haqida tushuncha
таълим вазирлиги
tashkil etish
O'zbekiston respublikasi
махсус таълим
toshkent davlat
vazirligi muhammad
kommunikatsiyalarini rivojlantirish
respublikasi axborot
saqlash vazirligi
vazirligi toshkent
bilan ishlash
Toshkent davlat
fanidan tayyorlagan
uzbekistan coronavirus
sog'liqni saqlash
respublikasi sog'liqni
vazirligi koronavirus
koronavirus covid
coronavirus covid
risida sertifikat
qarshi emlanganlik
vaccination certificate
covid vaccination
sertifikat ministry
Ishdan maqsad
o’rta ta’lim
fanidan mustaqil
matematika fakulteti
haqida umumiy
fanlar fakulteti
pedagogika universiteti
moliya instituti
ishlab chiqarish
fanining predmeti