+6-маъруза

Chuqurligi bo’yicha izlash algoritmining g’oyasi quyidagidan iborat: grafning boslang’ich tuguni yo’lning bo’shlanish tuguni sifatida qabul qilinadi.Undan keyin boshlang’ich tugundan chiqadigan bir qancha alternativ tugunlardan boshlang’ich tugundan eng uzoqda (uzunligi bo’yicha) joylashgan tugun tanlanadi. Navbatdagi tugunlararni tanlash, xuddi boshlang’ich tugundagidek, o’zidan oldingi tugunga nisbatan eng uzoqda joylashgan tugunni tanlash bilan davom ettiriladi. Tugunlarni tanlash algoritm bo’yicha maqsadga erishuvchi yo’lni topishgacha davom ettiriladi.
Chuqurligi bo’yicha birma-bir izlash algoritmi [1, 5-7]. Tugunlarning chuqurligi - tugunlarning pog’onalari tartib raqamiga teng bo’lgan son bilan aniqlahadi. Chuqurligi bo’yicha birma-bir izlash algoritmida tugunlar orasidan eng katta chuqurlikga ega bo’lgan tugunlar ochiladi. Bunda bir xil chuqurlikga ega bo’lgan bir nechta tugunlardan bittasi tanlanadi. Bundan tashqari, odatda ba’zi mulohazalarga ko’ra tugunlarning chegaravuy chuqurliklari beriladi. Bu holda tugunlar orasidan, tygunlari chuqurliklari chegaraviy chuqurlikga teng bo’lganlari ochilmaydi.
Shunday qilib, chuqurligi bo’yicha birma-bir izlash algoritmida tugunlar orasidan, tygunlar chuqurliklari chegaraviy chuqurlikdan kichchik bo’lgan tugunlar ochilmaydi.
Chuqurligi bo’yicha birma-bir izlash algoritmini strukturalashgan holda qaraymiz:

1. 
   Boshlang’ich tugunni «ochiq» royxatiga joylashtirish;
   
2. 
   Agar «ochiq» royxati bo’sh bo’lsa, u holda 1-qadamga, aks holda 3-qadamga o’tiladi;
   
3. 
   «Ochiq» royxatidan birinch tugunni olish va uni «yopiq» royxatiga o’tkazish va unga v nomni berish;
   
4. 
   Agar v tugunning chuqurligi chegaraviy churlikga teng bo’lsa, u holda 2- qadamga o’tish, aks holda 5-qadamga o’tish;
   
5. 
   v tugunni ochish. v tugunning barcha ichki tugunlarini «ochiq» royxatining boshiga joylashtirish va barcha ichki tugunlardan v tugunga keladigan ko’rsatkichlarni qurish; Agar v tugun ichki tugunlarga ega bo’lmasa, u holda 2- qadamga o’tish;
   
6. 
   Agar ushbu tugunlardan birortasi maqsadli echimni hosil qilsa, u holda chiqishda echimni hosil qilish, aks holda 2-qadamga o’tish.
   

Qaralgan algoritmda boshlang’ich tugun sifatida faqat bitta tugun qatnashadi. Agar boshlang’ich tugunlar bir nechta bo’lsa, u holda algoritmning 1-qadamidagi
«ochiq» royxatiga barcha boshlang’ich tugunlar joylashtiriladi.
Misol. Misol sifatida marshrutni tanlash masalasi uchun HFda echimlarni izlashda A, AD, ADC, ADCB, ADCBA optimal marshrutni keltirish mumkin ( 6.3, 6.4-rasmlar).
Ta’kidlash lozimki, echimni chuqurligi bo’yicha izlashda eng chuqurlikga ega bo’lgan tugunlar bir nechta bo’lsa, u holda ular orasidan eng chapdagisi tanlanadi.
Agar echimni izlash tupikli holatga kelib qolsa, ya’ni joriy tugun maqsadli echimga olib kelmasa va uning chuqurroq tugunlar bilan aloqasi bo’lmasa, u holda oldingi tugunga qaytiladi va ushbu tugundan echimni chuqurligi bo’yicha izlash davom ettiriladi.