LABİRENT ÇÖZME

Recursion yardımıyla labirentlerin çözümü:

"Zamanın uç-urumundan ve karanlık gerisinden başka ne görüyorsunuz?" W.M. Shakespeare, Fırtına

"... yorgunluktan ayakta duracak hali kalmamıştı. Saatine baktı, bu karmaşık labirent sistemine düştüğünden beri tam 15 galaktik-gün geçmişti (bir galaktik-gün, kütle numarası 200 olan kurşunun, kütlesinin ilk değerinin yarısına düşmesi için geçen süre olarak tanımlanan 'yarı ömrü'ne eşittir. = 0.895 dünya günü). Yanında bulunan yiyecek tabletleri ve su rezervleri ise üç-galaktik gün önce tükenmişti. Diğer taraftan susuzluk, açlıktan daha önemliydi. Çünkü, bir insan açlığa uzun süre dayanabilirdi ama susuzluğa çok fazla dayanamazdı. Fakat su bulsa bile değişen ne olacaktı ki? Bu labirentten kurtulması için bir mucize gerekliydi. Bunları düşünürken karanlık dehlizlerin içinde yeni bir yol ayrımına geldiğini farketti. Şimdi ne yapacaktı? Hangi yöne doğru gitmeliydi? Kararını verdi ve..."

Kahramanımız Eras, Cuprum gezegenindeki kötü kalplı büyücü Serus'un hazırladığı labirentten ancak robotu Hector'un beraberinde yedek yiyecek tabletleri ve su rezervleri olduğu halde kendisini bulmasıyla kurtuldu.

Böyle bir hikaye gelecekte gerçekleşebilir mi? Bunu şimdiden söyleyemeyiz. Ama bunun yerine, bilgisayarların bu gibi durumlarda kullandığı algoritmaya benzer bir algoritma geliştirebiliriz. Robotlar için labirentlerin çözümü çoğu zaman kolaydır. Çünkü onlar enerjileri yettiği sürece dolaşabilirler ve her şeyden önemlisi sinirlenip psikolojik baskı altına girmezler. Diğer taraftan robotlar, geçtikleri yerlerin bir haritasını çıkararak daha sonra aynı noktaya geldiklerinde oradan daha önce geçip geçmediklerini anlayabilirler. Robotun bilgisayarı, labirentin içindeki herhangi bir noktanın relatif koordinatını nasıl saptayabilir? Şöyle ki, başlangıç noktası referans noktası olarak alınır ve bir uzunluk birimi tespit edilir. Bundan sonra ileriye doğru gidilecek birim uzunlukların (veya adımların) sayısı +y geriye doğru olanlarının sayısı da -y alınır. Aynı şekilde yan taraflara doğru atılacak adımların sayısı da +x ve -x olarak değerlendirilir. Daha sonra her yol ayrımında bu değişkenler ile gidilmesi mümkün olan yönler kayıt edilirler. Bir robotun adımları hep aynı uzunlukta olacağı için bu sistemde hata olmaz ve böylece herhangi bir zamanda varılacak olan yol ayrımına daha önce gelinip gelinmediğine o anki x ve y değerlerinin bellekte aranmasıyla karar verilir. Eğer sonuç olumlu çıkarsa o kavşağa daha önce gelinmiş demektir, robot burada başka bir yön seçerek işine devam eder. Tabii gerçekte robotlar, adımlarını saymaktan başka çok daha kompleks yöntemler kullanarak da yollarını bulabilirler (örneğin bazı sinyalleri takip etmek). Burada geliştirilen 'Adım sayma' sistemi sadece bir örnektir. Diğer taraftan, biz burada labirentin sadece bir düzlem üzerinde olduğunu varsayıyoruz. Aynı şekilde, aşağıda verilen program da bir düzlem üzerindeki (iki boyutlu) labirentlerin çözümünü vermektedir.

Şimdi programımıza dönelim: Simons Basic kullanılarak yazılan programımızın temelli rekürsif programlama tekniğine dayanmakta

dır. Rekürsif programlar, değişen durumlara uyum sağlamak amacıyla değişik parametrelerle kendini çağırma yeteneğine sahiptirler. Recursion, özellikle Yapay Zeka (Artificial Intelligence) çalışmalarında büyük kullanım alanına sahiptir. Bu konuda daha çok bilgi edinmek isteyenler 10. sayıdaki Sayın Ayhan Kalaylıoğlu'nun yazısına başvurabilirler. Programın çalışma biçimi ise yukarıda açıklanan robot örneğinde olduğu gibidir. Bir tek farkla, yukarıda başlangıç noktası referans noktası olarak alınmaktaydı, programda ise buna gerek yok, çünkü cursor'un ekran koordinatlarını zaten bilmeyiz. Aynı şekilde gidilen yöne göre x ve y değişkenleri azaltılmakta veya çoğaltılmaktadır. Herhangi bir yol ayrımına gelindiği zaman x ve y koordinatları bir yığında (Stack) saklanmakta ve bu yığının göstergeci bir arttırılmaktadır.

Bundan sonra, bu kavşaktan yola devam etmek için, daha önce belirlenmiş bir düzene göre bir yön seçilerek o yöne ait flag ve yığından silinir. Kavşağa yaklaşırken gelinen yönün ters yönü yığına en son yerleştirilir ve bu yöne ait flag yığından hiçbir zaman silinmez. Çünkü bütün olası olasılıklar değerlendirilip dikten sonra çıkış bulunamayabilir ve o zaman yapılacak tek şey geldiğimiz yerden geri dönmektir. Bu şekilde yol alırken herhangi bir nedenle daha önce varılan bir kavşağa gelindiğinde ise bu yeni bir olasılık olarak değerlendirilmemekte (öyle olmak zorunda, çünkü aksi halde belirli bir yerde durmadan dolaşılacak) tersine yığın göstergeci daha önce gelinen o kavşağın numarasına eşitlenerek o kavşaktaki diğer olasılıklar araştırılmaktadır. Bu yöntemle ekran üzerinde dolaşan sembolik robotumuz deneme-yanılma metoduyla sonuca varmaktadır. Bu şekilde kurulan bir rekürsif düzenin, örneğin ekranda bir bölgeyi boya gibi değerlendirmek için kullanılan sistemden bazı farklılıklar vardır. Çünkü şekli boyayan program, şeklin sınırları veya daha önce aynı renge boyadığı bir alan ile karşılaştığı zaman hemen bir önceki yol ayrımına atlar ve boyamadığı yerleri boyamaya devam eder. Bu şekilde çalışan programlar hızlı olmalarına rağmen sonuca sadece teorik olarak yaklaşırlar. Bunun problemi ise, bu program yardımıyla, bir labirent içinde yolunu bulmaya çalışan duyargalarla dolu bir robotu kontrol etmeye çalıştığımızda karşımıza çıkar. Robotumuzu duvarların üzerinden atlatamayacağımıza göre ona çıkış yolunu bulamadığı bir yerden geri dönmesini öğretmeliyiz.

Şimdi de programı nasıl kullanacağınızı açıklayalım. Programı çalıştırdığınız zaman ilk önce karşınıza labirenti dizayn edeceğiniz ekran çıkacaktır. Labirentinizi 23 satır ve 38 sütun genişliğinde bir alan üzerinde dizayn edebilirsiniz. Dizayn işinde kullanacağınız tuşların anlamları ise aşağıda verilmiştir.

S: Başlangıç noktası

Space : Boşluk açmak için.

F: Açılan boşluğu tekrar doldurmak için.

Kursor Tuşları:

Kursoru istediğiniz noktaya götürmek için:

E: Bitiş noktası

P: Ekranın kopyasını yazıcıdan almak için.

Bitiş noktası E harfi ile bitirildikten sonra (tabii daha önce başlangıç noktasını belirtmelisiniz) program çözüme başlayacaktır. Çözüm sırasında robotumuzun hareketlerini ve gittiği yerlerde çözümü belirtmek için bıraktığı izleri ekranda aynı anda görebilirsiniz. Labirentin çözümü yok veya çözüm için bellek yetmiyor ise bilgisayar sizi uyaracaktır. Eğer kurduğunuz düzende çok fazla sayıda genişliği bir kareden fazla olan yollar var ise belleğin yetmemesi durumu ortaya çıkar.

Son olarak, ekranın altında geçen gösterilenleri belirterek yazımızı noktalayalım.

(Hector'un kullandığı algoritmayı hiç görmemiş ama şüphesiz bizimki onun yanında çok mütevazı kalırdı.)