Mirsaid Aripov, Nurillo Otaxanov

14.4. Yo`l qidirish masalasi

Bir-biri bilan bir nechta yo`llar orqali bog’langan bir nechta shaharlar berilgan bo`lsin. Ayrim yo`llarning boshi berk bo`lishi ham mumkin. Bir shahardan ikkinchisiga olib boruvchi barcha marshrutlarni topish masalasi qo`yilgan bo`lsin.

Mavjud bo`lgan barcha yo`llarning haritasi graf (shaharlarni angla-tuvchi uchlar va yo`llarni bildiruvchi qirralarning to`plami) yordamida berilgan bo`lsin. (13.9-rasm)

13.9-rasm. Graf ko`rinishidagi yo`llar xaritasi

Qidirish jarayonini qadamlar ketma-ketligi sifatida ifodalash mumkin. Har bir qadamda joriy nuqtadan turib, biror shart ostida o`tish mumkin bo`lgan ikkinchi nuqta tanlanadi. Agar navbatdagi nuqta izlangan nuqta bilan ustma-ust tushsa, u holda masala yechildi. Aks holda yana bir qadam qo`yish kerak. Joriy nuqtani boshqa bir nechta nuqtalar bilan birlashtirish imkoniyati bo`lgani uchun tanlash biror shart asosida bajariladi. eng sodda holda eng kichik nomerli nuqtani olish mumkin.

Faraz qilaylik, 1-nuqtadan 5-chiga o`tish talab qilingan bo`lsin. Shartga ko`ra, dastlab 2-nuqtani tanlanadi keyingi qadamda uning boshi berk ekanligi ayon bo`ladi. Mumkin bo`lgan yo`llardan biri 1→3→4→6→5. Shundan keyin 6-ga qaytib, 5-dan farqli yana boshqa yo`l mavjudligini tekshiriladi va h.k. Qidirish masalasi xarakat boshlangan joydan boshqa boradigan birorta ham yo`l qolmaganidan so`ng tugatiladi.

Qidirish algoritmi rekursiv xarakterga ega: yangi qadam uchun nuqta tanlanadi. Bu jarayon to maqsadga erishmaguncha, davom etaveradi.

Mumkin bo`lgan barcha yo`llarni qidirish masalasi yangi nuqtani (shaharni) tanlash va yo`lning qolgan qismidan mumkin bo`lgan barcha yo`llarni qidirish masalasiga aylandi. Bu yerda rekursiya ko`rinib turibdi.

Grafni ikki o`lchovli map massivi deb qaraylik: map[i, j] - bu i va j shaharlar o`rtasidagi masofa. Agar ular orasida yo`l bo`lmasa, bu masofa 0, aks holda 1 ga teng. Yuqoridagi graf uchun map massivi quyidagicha yoziladi (13.10-rasm)

12.10-rasm. Map massivi

Massivdan tashqari bizga yana road (yo`l) va incl (include – kiritilsin) massivlari ham kerak bo`ladi. Road massiviga o`tilgan shaharlar yozib boriladi. Oxirgi nuqtaga borganda, bu massivga barcha o`tilgan nuqta-shaharlar, ya`ni marshrutlar yozib qo`yiladi. Incl[i] massiviga esa i-nomerli nuqta marshrutga kirgan bo`lsa – true yoziladi. Bu bir marta borilgan nuqtaga yana qayta bormaslik uchun kerak.

Rekursiv protseduradan foydalanilgani uchun, rekursiv jarayonning tugashiga alohida e`tibor qaratish lozim. Protsedura joriy nuqta mo`ljaldagi nuqta bilan ustma-ust tushguncha o`zini o`zi chaqiraveradi. 13.11-rasmda navbatdagi nuqtani tanlash protsedurasining blok-sxemasi, 13.12-rasmda esa dialog oynasi keltirilgan.

Grafni o`z ichiga olgan massivni kiritish uchun StringGrid1 komponentasidan (13.1-jadval) foydalaniladi, natijani (topilgan marshrutni) chiqarish uchun - Label1 maydoni kiritilgan. Boshlang’ich va oxirgi nuqtalar Edit1 va Edit2 maydonlariga kiritiladi. Qidirish jarayoni Qidirilsin (Button1) tugmasi bilan boshlanadi.

13.11-rasm. Marshrut qadamini tanlash protsedurasining blok-sxemasi

13.12-rasm. Marshrut qidirish dasturining dialog oynasi

StringGrid1 komponentasining hususiyat qiymatlari 13.1-jadval.