Va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi

Chuqur birinchi qidiruv

Siz bunday labirintga tushib qolishingizni tasavvur qiling.

Siz qandaydir yo'l bilan chiqib ketishingiz kerak. Sizning boshlang'ich pozitsiyangizdan chiqishgacha bir nechta yo'nalish bo'lishi mumkin. Labirintdan chiqishga tabiiy yondashuv barcha yo'llarni sinab ko'rishdir.

Aytaylik, siz turgan joyingizda ikkita tanlov mavjud. Shubhasiz, labirintdan qaysi biri chiqishini bilmaysiz. Shunday qilib, siz birinchi tanlovni amalga oshirishga qaror qildingiz va labirentda oldinga siljiting.

Harakatlar qilishda davom etaverasiz va oldinga siljiysiz va oxirigacha urasiz. Endi siz boshqacha yo'lni sinab ko'rishni xohlar edingiz va shu bilan avvalgi nazorat punktiga o'tasiz, u erda siz bitta birini tanladingiz, so'ngra boshqa yo'lni, ya'ni bu safar boshqacha yo'lni sinab ko'rasiz.

Siz chiqish joyini topguningizcha shunday qilasiz.

Rekursiv ravishda ma'lum bir yo'lni sinab ko'rish va orqaga qaytish - bu chuqurlikni birinchi qidirish algoritmini (DFS) tashkil etuvchi ikkita komponent.

Agar labirent muammosini grafik sifatida modellashtirsak, uchlari labirintdagi odamning pozitsiyasini va ikki tugun orasidagi yo'naltirilgan qirralarning bir pozitsiyadan boshqasiga o'tishini bildiradi. DFS-dan foydalanib, chiqish joyi topilgunga qadar barcha mumkin bo'lgan yo'nalishlarni sinab ko'radi.

Xuddi shu uchun algorit namunasi.

1 protsedura DFS (G, v):

2 yorliq v topildi

G.adjacentEdges (v) dan v gacha bo'lgan barcha qirralar uchun 3

4, agar vertex w, keyin kashf etilgan deb belgilanmasa

5 DFS rekursiv ravishda qo'ng'iroq qilish (G, w)

Ushbu algoritmni chuqurroq o'rganish uchun tekshiring: -

Vaqtning murakkabligi: O (V + E)