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.

Yorumlar

  1. BERAT

    Merhabalar hocam c dilinde program yazıorum stack yapısını kullanarak bir labirent yapma,ödevi pek net anlayamadım sanırım yardımcı olursanız sevinirm 1 ler duvar ve 0 lar yol olcak giriş noktasından itibaren de bir yığına eklenecek,giriş noktası sol üst köşe çıkış ise sağ dış kenarı veya alt dış kenarda olcak,program çıkış yolunu bulacak,
    ..11.111
    1.1.11.1
    1..1…1
    11.1.1.1
    11…1.1
    111111.1
    1111…1
    buna benzer bir çıkış yolu üretcekmiş,benm anlamadığım labirent rastgele oluşturuluyor belki de sol üst köşede giriş noktası yok,her bir labirent için bunu nasıl düşüncem,ayrıca tek bir çıkış yolu mu olcak ,birden fazla yol olabilir mi teşekkürler,
    1111.111

  2. Şadi Evren ŞEKER Article Author

    Bu sorularınız, kodlama ile ilgili birer kabulden ibaret. Yani labirent üretilirken sabit bir noktayı giriş ve çıkış için belirliyorsanız (ki yukarıdaki örnek kodda bu şekildedir) buna göre kodlarsınız. Şayet labirentteki giriş ve çıkış noktaları değişiyorsa, bunları bulmak için ilave bir koda ihtiyacınız var. Örneğin labirentin kenarlarını dolaşıp bir 0 değeri arayabilirsiniz:

    for(int i=0;i
    

    Yukarıdaki kod, çok kabaca, matrisin kenar değerlerini (i=0 veya j=0 veya i=en-1 veya j=boy-1 olduğu durum) bulmaktadır. Ayrıca kenar değerlerinden birisi ve değer 0 ise (yani sizin tanımınızda yol ise) burayı başlangıç alır.

    Ayrıca labirent üretilirken kullanılan her türlü detay yukarıdaki örnekte olduğu gibi sizin kodunuzu yazmanız için kullanacağınız detayları belirler. Bu yüzden kodlamaya başlamadan önce sorunun bütün detaylarını anlamanız ve güzel bir tasarım yapmanız çok önemlidir.

    başarılar

  3. BERAT

    Hocam dediinizi anladım ama benim anlamadıım şu giriş noktamız belli sol üst köşe ama labirent rastgele olcağı üretileceği için mesela 11000110 bu şekilde ilk satır bunun sol üst köşesinden girişi yok 11 le başlıyor aynı şey çıkış için de olabilir,belirlediimiz çıkış noktası bir sonraki labirent için uymayabilir,soruyu anlamakta baya zorlandım bu durumda bu labirente giriş olmaz mı diecem?

  4. Şadi Evren ŞEKER Article Author

    Bakın bu soruyu neden bana soruyorsunuz bilmiyorum ama ödevinizi ben vermedim, ödeviniz hakkında bir fikrim yok. Bence ödevinizi veren kişiye sormanız daha yerinde bir karar olur. Ödevden sizin anladığınızdan benim anladığım üzerine yorum yapmam çok sağlıklı görülmüyor.

  5. Şadi Evren ŞEKER Article Author

    Hareket için:

    int f(int x, int y) { // x ve y koordinatlarını alır
    data[x][y] = 2; // geldiğimiz bu yere geldik işareti bırakıyoruz
    // 4 farklı yönü test ediyoruz.
    if(data[x+1][y]== 0 )
      f(x+1,y);
    if(data[x][y+1]== 0 )
      f(x,y+1);
    if(data[x-1][y]== 0 )
      f(x-1,y);
    if(data[x][y-1]== 0 )
      f(x,y-1);
    }
    

    Yukarıdaki özyineli (recursive) fonksiyon 4 yöne bakarak boş olan yöne hareket eder.

    Ayrıca yukarıda kullanılan yığın (stack) yapısı, aslında geri çağrım yığınıdır (call back stack) yani fonksiyondan nereye döneceğini tutan yığındır.

  6. arda

    hocam özyineli çıkmaz bi yola girince nasıl geri dönecek? ben adres değişkeni kullanarak bunu sınırlı yapabiliyorum…

  7. Anonim

    meraba bnm de özyinelemli olarak aşağıdaki labirentiolştrmam lazm ama yapamadm c++ da yardımcı olabilicekolan var mıı lütfeeeeeeeeeeeeennnn
    00110111
    10101101
    10010001
    11010101
    11000101
    11111101
    11110001
    11110111

  8. gülsüm

    00110111
    10101101
    10010001
    11010101
    11000101
    11111101
    11110001
    11110111
    bu labirent yapısı c++ da özyinelemli olarak yazmam lazm yardm edebilcek olan var mı

  9. Orhan

    Hocam merhabalar, anlatımınız çok yalnız netbeans projesi olarak verdiğiniz rar dosyası linki ölmüş onu yenileyebilir misiniz?

  10. gökçe

    merhaba hocam netbeans projesi çalışmıyor en kısa zamanda yenilerseniz sevinirim projem var ve yanlış noktalarda düzeltmek istiyorum.

  11. salih

    hocam netbeans projesindeki path adlı stack sizin anlattığınız stack ile uyuşmuyor yani karar düğümlerini tutmuyor acaba anlatım mı yanlış kod mu ?

Şadi Evren ŞEKER için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir