Labirentte yol bulma kodu

Yazan : Şadi Evren ŞEKER

Bu yazının amacı, geri izleme algoritmasının (backtracking algorithm) bir uygulaması olarak, basit bir labirentte yol bulma kodunu JAVA dilinde kodlamaktır. Bu uygulamada herhangi bir yapay zeka yönetmi uygulanmayacaktır. Basitçe kör arama (blind search) yapan ve ihtimalleri sırayla deneyen bir robot uygulaması geliştirilecektir.

Örneğin labirent bilgisinin bir dosyada bulunduğunu ve bizim amacımızın bu dosyayı okuyarak labirentin başlangıcından çıkışına kadar olan yolu bulmak olduğunu düşünelim. Labirent tasarımımızda duvarları 1 ve yolları 0 ile gösterelim. Örneğin aşağıda bir labirent verilmiştir:

1111111
0010011
1000011
1101111
1100000
1111111

Yukarıdaki bu labirentte, sol üst köşeyi başlangıç konumu ve sağ alt köşeyi de bitiş konumu olarak kabul edeceğiz. Buna göre labirentin her zaman için ikinci satırının ilk kolonunda başlıyoruz ve labirentin boyutuna göre son satırın bir üstünde en sağ kolonda bitiriyoruz. Amacımız bu iki nokta arasındaki yollardan bir tanesini çözüm olarak bulmak. Ayrıca dosyadan labirent okuyacağımız için, veri yapısı kullanımını kolaylaştırmak amacıyla, labirentin boyutlarını da dosyanın ilk satırında tutalım. Buna göre bir labirent dosyasının içeriği aşağıdaki şekilde olacaktır:

6 7
1111111
0010011
1000011
1101111
1100000
1111111

Dosyanın ilk satırında, labirentin satır ve sütun boyutları verilmiştir.

Algoritmamız, basitçe labirentin başlangıç konumundan yola çıkacak ve yol alternatiflerini değerlendirecektir. Şayet yol tek yönlü ise hareket etmeye devam edecek ancak bir yol ayrımına geldiğinde bu noktayı bir yığında (stack) tutarak çıkmaz bir yola girdiğinde en son aklında tuttuğu bu yola geri dönecek ve farklı bir karar verecektir.

Örneğin yukarıdkai problem için çözümü elle yaparak tasarımımıza başlayalım. Başlangıç durumumuz (1,0) olacak (dizide satır sayısının 0’dan başladığını düşünürsek, ikinci satırın ilk sütunu (1,0) olarak gösterilecektir.

Bitiş durumumuz ise (4,6) olarak belirlenecektir (dizi boyutumuzda azami satır ve sütun değerleri 5,6 olacaktır (boyuttan bir eksik) ve en altın bir üstü satır 4 ve son sütun 6 olacaktır. Dolayısıyla bitiş durumu olarak (4,6) tanımlıyoruz.

(1,0) konumundan, (4,6) konumuna kadar olan çözüm yolunu bulmak için adım adım algoritma tasarımımızı inceleylim.

Algoritmamız kör arama (blind search) olduğu için, çözüme giden en mantıklı yolu bulmak yerine bütün ihtimalleri deniyeceğiz. Bu ihtimalleri belirli bir sıra ile aramamız gerekiyor. Bu srıalama için algoritmamızı aşağıdaki şekilde tasarlayalım:

Geldiğim yeri işaretle

if(sola gidilmemişse)

sola git;

else if(sağa gidilmemişse

sağa git;

else if(yukarı gidilmemişse)

yukarı git;

else if (aşağı gidilmemişse)

aşağı git;

Yukarıdaki bu tasarımda sol -> sağ -> yukarı -> aşağı sırası tamamen rast gele olarak üretilmiştir ve daha farklı sırada da olabilirdi.

(1,0) konumundan başlayarak yukarıdaki algoritmayı icra ettirelim. İşaretleme için 2 değerini kullanacağız. Öncelikle yığın (stack) değeri boş olarak başlıyoruz (bundan sonra S olarak gösterilecek ve sağdan eklenerek sağdan çıkarma yapılacaktır):

1111111
0010011
1000011
1101111
1100000
1111111

S -> boş

İlk değeri işaretliyoruz:

1111111
2010011
1000011
1101111
1100000
1111111

(1,0) konumunda tek gidilebilecek komşu, (1,1) konumudur (1,0) konumunun komşuları 0,0 2,0 ve 1,1 olduğuan göre bu değerlere bakıyoruz ve bunlardan 0 olan tek değere gidiyoruz:

1111111
2210011
1000011
1101111
1100000
1111111

Benzer şekilde (1,1) konumunun tek 0 olan komşusu (2,1) olan konuma gidiliyor. Benzer şekilde (2,1) konumunun tek komşusu olan (2,2) konumuna gidilerek aşağıdaki durum elde ediliyor:

1111111
2210011
1220011
1101111
1100000
1111111

Yukarıdaki son durumda geldiğimiz konum (2,2) ve birden fazla komşumuzda 0 değer var. Yani (2,2) konumunun komşuları olan (2,3) ve (3,2) değerleri 0 olduğu için bu alternatiflerden birisini takip edeceğiz. İşte bu yol ayrımında yığın (stack) kullanmanın sırası geliyor. Bunun sebebi şu anda vereceğimiz kararın doğru olup olmadığını bilmediğimiz ve basitçe hata yapıyorsak buraya geri dönmek istememiz.

S -> (2,2)

Yukarıdaki şekilde karar noktamızı yığına yerleştirdikten (push) sonra algoritmamızdaki öncelikli yol olan sol tarafı deniyoruz. Sol tarafımızda ((2,2)’nin solunda (2,1) vardır) 0 olmadığı için gidemiyoruz. Algoritmamızdaki ikinci ihtimal olan sağ tarafa bakıyoruz (sağın koordinatı (2,3)) ve bu değer 0 olduğu için bu yönde gidiyoruz.

1111111
2210011
1222011
1101111
1100000
1111111

Sağa gitme işlemine devam ediyoruz (aşağıya gidemediğimiz için) ayrıca burada bir yol ayrımı bulunduğu için (sağa veya yukarıya gidebiliriz) yığının (stack) içerisine yerleştiriyoruz:

S -> (2,2) , (2,3)

1111111
2210011
1222211
1101111
1100000
1111111

Tek alternatif olan yukarıya devam ediyoruz:

1111111
2210211
1222211
1101111
1100000
1111111

Tek alternatif olan sola devam ediyoruz:

1111111
2212211
1222211
1101111
1100000
1111111

Netice itibariyle alternatifi kalmayan (hiçbir yönde 0 olmayan) bir duvar ile karşılaştık ve bu noktadan sonra çıkma ihtimalimiz kalmadığı için yığındaki en üstte bulunan ve en son karar verdiğimiz noktaya dönüyoruz.

Bu nokta (2,3) koordinatlarındadır ve pop edildikten sonra stack aşağıdaki şekildedir:

S – > (2,2)

Pop ettiğimiz (2,3) noktasında da gidilecek hiçbir alternatif bulunmuyor. Mecburen yığındaki (stack) bir sonraki noktaya dönüyoruz:

S -> Boş

Döndüğümüz koordinat (2,3) noktası ve buradaki tek alternatif aşağı yönde bulunan 0 değeri:

1111111
2212211
1222211
1121111
1100000
1111111

Bu aşamadan sonra, hiçbir alternatif kalmadan 0 olan yollar izlenerek sonuca ulaşan yol bulunmuş oluyor.

Kodlama

Yukarıdaki yaklaşımın JAVA dilinde kodlanmış hali yazının sonunda verilmiştir. Bu kodun kısaca açıklamasını bu bölümde anlatacağım. Kodumuzda temel olarak iki sınıf bulunuyor:

• currentInfo
• Maze

currentInfo sınıfı, anlık olarak matrisin hangi konumunda bulunduğumuzu tutmaya yarıyor. Çok basit şekilde satır ve sütün koordinatlarımızı barındırıyor. Ayrıca bu değerlere erişmeyi sağlayan inşa sınıfları (constructors) ve kapsülleme fonksiyonları (encapsulation) bulunuyor.

Maze sınıfı ise geri kalan herşeyi yapan ana sınıfımız. Bu sınıfta getMaze() isimli fonksiyon, dosyadan labirent bilgilerini okumak için kullanılıyor. solveMaze fonksiyonu da labirentteki sonucu bulmaya yarayan yukarıdaki işlemleri çalıştırıyor.

Yukarıdaki anlatımda geçen ve S harfi ile ifade ettiğimiz yığın (stack) ise kodumuzda path ismi ile tanımlanmış java.util.Stack sınıfından tanımlanmış bir yığın. Buradaki yığın, karar verirken atılan her adımı tutmakta. Yani yukarıdaki labirent çözümünde geçen ve 2 olarak işaretlerken, birden fazla 0 ihtimali bulunan dönüm noktalarını tutuyor.

Yığının en temel 3 fonksiyonu ise aşağıdaki şekildedir:

• Pop() yığında bulunan en üstteki değeri alarak bir değişkene döndürür.
• Push() yığının en üstüne, parametre olarak aldığı veriyi yerleştirir.
• Peek() yığının en üstündeki veriyi alır ancak pop fonksiyonunun aksine bu veriyi silmez. Bu fonksiyon bazı kaynaklarda Top() olarak da geçmektedir ancak java.util.Stack sınıfında peek ismi ile tanımlanmıştır.

Kodumuzda kullandığımız iki temel dizi ise aşağıda verilmiştir:

• mazeData[][] iki boyutlu bu dizi, dosyadan okunan ve hafızada labirent bilgisini tutan dizidir.
• Mark[][] diğer iki boyutlu dizimiz ise sonuca giden yolu tutar.

İkinci diziye neden ihtiyaç duyduğumuz sorusunu şu şekilde cevaplayalım. Dizimizi dolaşırken, yanlış yollara sapabiliyoruz, geçtiğimiz her yeri basarsak bu sonuçta görmek istediğimiz çözüm yolu olmayacaktır. Ayrıca labirentte dolaşırken, çözüme giden yolu 2 ile işaretliyoruz ama hatalı yolları da 2 ile işaretliyoruz. Dolayısıyla labirenti dolaştıktan sonra 2 ile işaretli yolları basarsak bu yollarda da sonuca gitmeyen değerlerin basılması söz konusu. Çözüm olarak ayrı bir dizide, sonuca giden yoldaki koordinatları ayrıca tutuyoruz.

Koddaki bazı satırları anlatmamız gerekirse:

Yukarıdaki kod parçasında, bulunduğumuz konumdan (current) sonraki gidebileceğimiz yönleri sırasıyla deniyoruz. İlk if koşulunda mazeData isimli dizide (yani labirentin verilerinin tutulduğu dizi) bulunan ve mevcut konumun bir sağında yer alan (col + 1 işleminin anlamı bir sonraki kolon demektir) değere gidilmesi ve bu değerin daha önce mark dizisinde işaretlenmemiş olması (gidilmemiş olması ) durumu kontrol edilmektedir. Ardından sırasıyla, sol, aşağı ve yukarı yönler için aynı kontroller yapılmaktadır. Yazıda anlatılan sıradan bu anlamda farklıdır.

Yukarıdaki kod parçasında ise, bir önceki kod parçasının devamı niteliğinde, şayet 4 yöndede hareket edilemiyorsa, çıkmaz bir yola girilmiş neticesine varılabilir. Bu durumda mevcut durum dolaşıldı anlamında, 2 ile işaretlendikten sonra, yığından (stack) pop fonksiyonu ile dönülecek en son karar anına bakılıyor.

Şayet yığın bir şekilde boş olursa (ki bu durum try/catch blokları arasında istisna kabz edilerek (exception handling) çözülmüştür) bu durumda labirentin bir çözümü olmadığını söyleyebiliriz çünkü hem bir çıkmaz yol bulduk hem de geriye döneceğimiz hiçbir yol ayrımı bulunmuyor demektir.

Netice itibariyle, 61. Satıra kadar ulaştıysak, bu satırda flag değişkeni true değerinde olup, yukarıdaki 4 iften birisine girerek bir yöne hareket etmiş olabilir. Bu durumda gidilen bu yok, mark dizisinde işaretlerenerek yığına yerleştiriliyor. Ayrıca flag değişkenin false olduğu tek ihtimal olan çıkmaz yol durumunda da if bloğu çalışmıyor.

Yukarıda alıntılıanan kod parçası ise bütün işlemler bitip, labirent bir sonuca ulaşacak şekilde dolaşıldıktan sonra, mark dizisi üzerinden dolaşılan yolu ekrana basmaktadır. Döngü, labirent boyutları olan dim1 ve dim2 sınırlarında dönmekte, her adımdaki konum 71. Satırda ekrana basılmakta ve sonraki konum da 4 farklı koşul konrolü ile işaretlenmiş olan yöne doğru değiştirilmektedir.

Kodun çalışması sonucunda, örnek ekran çıktısı aşağıda verilmiştir:

Görüldüğü üzere labirentteki bütün yolları dolaşarak, sonuca ulaşan yolları ekrana basmıştır(lütfen basma işlemi sırasında, 71. Satırda olduğu üzere önce satır sonra sütun koordinatının basıldığına dikkat ediniz). Bu örnek çalışma, aşağıdaki labirent içindir:

Ayrıca farklı bir dosya içeriği, projenin bulunduğu dizindeki maze.dat dosyasının içerisine yerleştirilerek çalıştırılabilir.

Kodun tamamını netbeans projesi olarak indirmek için tıklayınız.