+6-маъруза

Misol. 6.5, а-rasmda HFda echimni chuqurligi bo’yicha izlashda qanday tugunlardan foydalanish kerakligi ko’rsatilgan. Bu erda a boshlang’ich, j va f oxirgi holatlarga mos keladi.
Ajratilgan [a, b, e, j] va [a, c, f] yo’llar – bu topilgan hal qiluvchi yo’llar, [a, c, f] yo’l esa – hal qiluvchi qisqa yo’l hisoblanadi.
HFda echimni chuqurligi bo’yicha izlash ko’p hollarda 6.5, а-rasmda ko’rsatilgandek yaxshi ishlaydi. Ba’zi hollarda u to'xtash holatiga ham tushib qolishi mumkin, masalan, sikllanish holatiga tushishi mumkin. Masalan 6.5, б –rasmda sikllanish holatlari [d, h, d] va [b, e, i, b] keltirilgan.

6.5-rasm. Chuqurligi bo’yicha izlash strategiyasi.

3. Kengligi bo’yicha izlash strategiyasi

Kengligi 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 tugunga yaqin (uzunligi bo’yicha) joylashgan tugun tanlanadi. Navbatdagi tugunlararni tanlash, xuddi boshlang’ich tugundagidek, o’zidan oldingi tugunga nisbatan eng yaqin joylashgan tugunni tanlash bilan davom ettiriladi. Tugunlarni tanlash algoritm bo’yicha maqsadli echimga erishuvchi yo’lni topishgacha davom ettiriladi.
Ta’kidlash lozimki, echimni kenglik bo’yicha izlashda boshlang’ich tugunga yaqin 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 kengligi bo’yicha izlash davom ettiriladi.
Misol. 6.6-rasmda HFda echimni kengligi bo’yicha izlashda qanday tugunlardan foydalanish kerakligi ko’rsatilgan. Bu erda a boshlang’ich, j va f oxirgi holatlarga mos keladi.
Ajratilgan [a, c, f] – bu birinch topilgan hal qiluvchi yo’l bo’lib, u qisqa yo’l hisoblanadi. Ikkinchi hal qiluvchi yo’l [a, b, e, j] bo’lib, u to’liq birma-bir tekshirish orqali hosil qilinadi.