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

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