Duyuruyu Kapat
Facebook Gözat
Twitter Gözat

8 Bilmece

Konu, 'Java / JSP / JSF' kısmında Erdem⁣ tarafından paylaşıldı.

  1. Erdem⁣

    Erdem⁣ Üye

    Kayıt:
    1 Temmuz 2012
    Mesajlar:
    99
    Beğenilen Mesajlar:
    0
    Meslek:
    Programcı
    Şehir:
    Eskişehir
    8 Bilmece

    8 Bilmece problemini A* arama algoritmasını kullanarak çözen bir program yazın.

    Problem : 8 bilmece problemi 1870'lerde Noyes Palmer Chapman tarafından icat edilen ve yaygınlaştırılan bir bilmecedir. Üzerinde 8 tane kare taş bulunan 3x3 bir tahta üzerinde oynanır. Amacınız mümkün olduğunca az hamle yaparak taşları tekrad dizmektir. Boş kare içine yatay veya dikey olarak taşları kaydırabilirsiniz. Aşağıda başlangıçtan (solda) bitişe kadar (sağda) bir dizi geçerli hamle gösterilmektedir.

    Kod:
        1  3        1     3        1  2  3        1  2  3        1  2  3
     4  2  5   =>   4  2  5   =>   4     5   =>   4  5      =>   4  5  6
     7  8  6        7  8  6        7  8  6        7  8  6        7  8 
    
    başlangıç      1 sola          2 yukarı       5 sola         hedef
    
    En iyi öncelikli arama - Şimdi , biz A * arama algoritması olarak da bilinen, genel bir yapay zeka yöntemi kullanan bir çözümü açıklayacağız. Bir tane arama düğümü tanımlıyoruz. Bu arama düğümü bir oyun tahtası, tahta o hale gelene kadar yapılan hamle sayısı ve bir önceki arama düğümünü içeriyor, İlkönce ilk arama düğümünü (tahtanın ilk hali, 0 hamle ve önceki arama düğümü null olacak şekilde) öncelikli kuyruğa yerleştirin. Daha sonra öncelikli kuyruktan önceliği en düşük olan elemanı silin ve öncelikli kuyruğa komşu arama düğümlerini (bunlar bir hamlede kuyruktan çıkarılan arama düğümünden bulunabilmeli) ekleyin. Bu işleme kuyruktan çıkan düğümün içerdiği tahta hedef tahta olana kadar devam edin. Bu yaklaşımın başarısı arama düğümü için seçilen öncelik işlevinin başarısına bağlı. Biz iki tane öncelik işlevini inceleyeceğiz.

    Hamming öncelik işlevi : Yanlış konumda bulunan taşların sayısı ve ek olarak geçerli arama düğümüne gelmek için yapılan hamle sayısı. Sizin de farkedeceğiniz üzere az sayıda yanlış konumda bulunan taşlardan oluşan bir arama düğümü çözüme daha yakındır. Arama düğümü seçerken de az hamleyle ulaşılmış bir arama düğümünü tercih ediyoruz.

    Manhattan öncelik işlevi : Taşların bulunduğu konumdan, olmaları gereken konuma kadar olan Manhattan mesafelerinin (dikey ve yatay mesafe toplamı) toplamı, buna ek olarak geçerli arama düğümüne gelmek için yapılan hamle sayısı.

    Örneğin aşağıdaki ilk arama düğümünün Manhattan ve Hamming öncelikleri sırasıyla 5 ve 10.

    Kod:
    
     8  1  3        1  2  3     1  2  3  4  5  6  7  8    1  2  3  4  5  6  7  8
     4     2        4  5  6     ----------------------    ----------------------
     7  6  5        7  8        1  1  0  0  1  1  0  1    1  2  0  0  2  2  0  3
    
       ilk          hedef         Hamming = 5   0          Manhattan = 10   0
    
    Kritik bir en iyileştirme - En iyi öncelikli aramanın can sıkıcı bir özelliği var. Aynı tahtaya ait arama düğümleri öncelikli kuyruğa birden fazla eklenebiliyor. İşe yaramayan arama düğümlerinin gereksiz olarak açılmasını önlemek için bir arama düğümünün komşularını eklerken eğer komşu bir önceki arama düğümüne eşitse onu eklemeyin.

    Kod:
     
     8  1  3       8  1  3       8  1       8  1  3     8  1  3
     4     2       4  2          4  2  3    4     2     4  2  5
     7  6  5       7  6  5       7  6  5    7  6  5     7  6
    
     önceki    arama düğümü      komşu      komşu       komşu
                                       (izin vermeyin)
    
    Oyun ağacı : Yapılan hesaplamayı görebilmenin bir yolu oyun ağacını incelemekten geçiyor. Her arama düğümü oyun ağacında bir düğüme karşılık geliyor ve bu ağacın dalları komşu arama düğümlerine tekabül ediyor. Oyun ağacının kökünde ilk arama düğümü var. Beyazla gösterilen düğümler açılan düğümleri, diğer açılmamış dallar öncelikli kuyrukta saklanıyor. A* arama algoritması her adımda önceliği (masrafı) en düşük düğümü çıkarıyor ve gerekli işlemi yapıyor.

    [​IMG]

    Çözülemeyen bulmacaların tespiti : Tüm tahtalar çözülemiyor. Bunlardan iki tanesini aşağıda görebilirsiniz.

    Kod:
    
     1  2  3         1  2  3  4
     4  5  6         5  6  7  8
     8  7            9 10 11 12
                    13 15 14 
    çözülemiyor
                    çözülemiyor
    
    Bu tür durumları tespit edebilmek için çözülebilirlik bakımından bulmacaların ikiye ayrıldığını düşünebilirsiniz. (i) Normal olarak çözülebilen tahtalar (ii) Eğer ilk baştaki tahtada herhangi iki taşı (boş kare olan 0'ı taş olarak kabul etmiyoruz) yerdeğiştirdiğimizde çözüme ulaşan tahtalar. Bunu denemek için A* arama algoritmasını iki tahta --bir tanesi başlangıçtaki tahtayı diğeri tahtanın herhangi iki taşının yer değiştirilmesi sonucunda oluşan tahta-- üzerinde deneyin. İki tahtadan biri çözüme ulaşacak.

    Tahta ve Çözücü sınıfları : Tahta sınıfını aşağıdaki işlevleri gerçekleştirecek şekilde tasarlayın.
    Kod:
    public class Tahta
    {
        public Tahta(int[][] taşlar)           // N-N diziden oluşan taşlardan (taşlar[i][j] = i. satır ve j.sütünda
                                               // bulunan bir taş olacak şekilde) bir tahta oluşturun
        public int boyut()                     // tahta boyutu N
        public int hamming()                   // olması gerektiği yerde olmayan taş sayısı
        public int manhattan()                 // taşların hedef konuma olan Manhattan uzaklıklarının toplamı
        public boolean hedefMi()               // bu tahta hedef tahta mı?
        public Tahta ikiz()                    // herhangi iki taşın yerdeğiştirilmesiyle elde edilen tahta
        public boolean equals(Object diğer)    // bu tahta diğer tahtaya eşit mi?
        public Iterable<Tahta> komşular()      // tüm komşu tahtalar
        public String toString()               // bu tahtanın string (katar) olarak gösterimi
    
        public static void main(String[] args) // birim testleri (kendi denemeleriniz için)
    }
    
    Tahta sınıfının kurucu işlevinin N'e N boyunda, 0 ve N² - 1 arasında N² tamsayı içeren bir dizi aldığını kabul edebilirsiniz. 0 boş kareyi ifade ediyor.

    Ayrıca çözücü sınıfını da aşağıdaki işlevleri yerine getirecek şekilde tasarlayın.
    Kod:
    public class Çözücü
    {
        public Çözücü(Tahta ilk)                  // ilk tahta için bir çözüm bul(A* algoritmasını kullanarak)
        public boolean çözülebilirMi()          // ilk tahta çözülebilir mi?
        public int hamleler()                   // tahtayı çözmek için yapılması gereken en düşük hamle sayısı; eğer çözülemezse -1
        public Iterable<Tahta> çözüm()          // en kısa çözümü gösteren tahta dizilimi; eğer çözülemiyorsa null döndürmeli
        public static void main(String[] args)  // bulmacayı çöz (aşağıda bulabilirsiniz)
    }
    A* algoritmasını gerçekleştirmek için öncelikli kuyruk olarak MinPQ.java dosyasını kullanabilirsiniz.

    Çözücü test programı : Bir bulmacayı (komut satırında belirtilen) kütükten okuyup çözümü ekrana yazan aşağıdaki test programını kullanabilirsiniz.

    Kod:
    public static void main(String[] args)
    {
        // ilk tahtayı bir kütükten oluştur
        In giriş = new In(args[0]);
        int N = giriş.readInt();
        int[][] taşlar = new int[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                taşlar[i][j] = giriş.readInt();
        Tahta ilk = new Tahta(taşlar);
    
        // bulmacayı çöz
        Çözücü çözücü = new Çözücü(ilk);
    
        // çözümü standart çıkışa yaz
        if (!çözücü.çözülebilirMi())
            StdOut.println("Çözüm yok");
        else
        {
            StdOut.println("En düşük hamle sayısı = " + çözücü.hamleler());
            for (Tahta tahta : çözücü.çözüm())
                StdOut.println(tahta);
        }
    }
    Girdi çıktı biçemleri : Bir tahtanın giriş çıkış biçemi en üstte tahta boyutunu gösterecek N ve N'e N'lik tahtayı gösterecek şekilde olmalı. Örneğin,

    Kod:
    % more bilmece04.txt
    3
     0  1  3
     4  2  5
     7  8  6
    
    % java Çözücü bilmece04.txt
    En düşük hamle sayısı = 4
    
    3
     0  1  3 
     4  2  5 
     7  8  6 
    
    3
     1  0  3 
     4  2  5 
     7  8  6 
    
    3
     1  2  3 
     4  0  5 
     7  8  6 
    
    3
     1  2  3 
     4  5  0  
     7  8  6 
    
    3
     1  2  3 
     4  5  6 
     7  8  0
    % more bilmece3x3-cozumuyok.txt
    3
     1  2  3
     4  5  6
     8  7  0
    
    % java Çözücü bilmece3x3-cozumuyok.txt
    Çözüm yok
    
    Yazdığınız program N'e N boyutunda (2 ≤ N < 128) tüm tahtalar için, bazılarını çözmek zaman alsa ve yavaş çalışsa bile doğru olarak çalışabilmeli.

    Yazdığınız programı test etmek için 8bilmece.zip kütüğünü indirerek örnek bilmeceler üzerinde denemeler yapabilirsiniz.

    Erdem