Forum
Aktif konular
Üyeler
Kurallar
Arama
8 Puzzle Solution 8 Puzzle Solution
-
Hepiniz daha önce bu puzzle'ın 4*4 lerini oyuncak olarak görmüşünüzdür..
Amaç kaydırarak doğru sonuca ulaşmak..
Bil ödevim için buna bi kaç tane farklı çözüm hüristiği geliştirmem lazım.
Daha önce böyle birşey hazırlamış veya karşılaşmış müritler varsa, yardımınızı bekliyorum..
-
9
-
buraqgo bunu yazdı:
-----------------------------9
-----------------------------Şaka mısın sen?
-
Konuyu çok geç gördüm, umarım çok geç kalmamışımdır.
Bir kaç tane heuristic geliştirmem lazım demişsin, işin zor gibi. Zamanında bunun 4x4 lük versiyonu bana proje olarak verilmişti. Kendim bir heuristic geliştirerek Java'da implementasyonunu yapmıştım ama kodu arşivlerim arasında bulamadım. Eğer hala ihtiyacın varsa sana mantığını anlatabilirim.
-
Destroyer bunu yazdı:
-----------------------------Konuyu çok geç gördüm, umarım çok geç kalmamışımdır.
Bir kaç tane heuristic geliştirmem lazım demişsin, işin zor gibi. Zamanında bunun 4x4 lük versiyonu bana proje olarak verilmişti. Kendim bir heuristic geliştirerek Java'da implementasyonunu yapmıştım ama kodu arşivlerim arasında bulamadım. Eğer hala ihtiyacın varsa sana mantığını anlatabilirim.
-----------------------------Eger anlatirsan burda eminim soruyu soran arkadasimiz ve ben sana cok minnettar kaliriz kardesim. Anlatimini bekliyoruz , tesekkkurler.
-
Artık çok geç :D
Kendime göre bi hüristik geliştirdim.. Ama sağ alt 2*2 lik kısımda döngüye başlıo bi noktadan sonra..
Bi kaç hüristiği bi arada kullanıp, aynı puanlara denk gelince dallanmaların hepsini çözmek lazım.. Optimum çözüm anca bu şekilde çıkıo.
Php ile bi script yazıp ağaç çıkartmayı denedim ölüm gibi oluo yaw :D Neyse kıytırıktan bişi yazıp verdim hocaya :D
-
Yok bence gec degil , yani sen odevi vermissin ama bizim ve burdaki insanlarin yeni biseler gorup ogrenmesi icin cok gec degil :)
Arkadas umarim gorunce kendi dusuncelerini implemantasyonunu bize aktarir , ve sendende yaptigin cozumu ve scripti buraya koyup anlatirsan
sevinirim kardesim.
-
SpArK bunu yazdı:
-----------------------------Yok bence gec degil , yani sen odevi vermissin ama bizim ve burdaki insanlarin yeni biseler gorup ogrenmesi icin cok gec degil :)
Arkadas umarim gorunce kendi dusuncelerini implemantasyonunu bize aktarir , ve sendende yaptigin cozumu ve scripti buraya koyup anlatirsan
sevinirim kardesim.
-----------------------------ben çözüme ulaşamadım. Tek başına yeterli olmadı benim hüristik..
Mantık olarak sayıların bulunduğu kare ile içindeki değerin farkının mutlak değerlerini topluodum, buna göre bi toplam puan bulup küçük olan puana doğru ilerliyodum..
Çok komplike bi cümle oldu :D
-
Selam,
Bu puzzle'ın optimal çözümüne o kadar da ağır olmayan bir heuristic ile ulaşılabilir. A* (astar) search algoritmasını (http://www.autonlab.org/tutorials/astar08.pdf) duymuşsunuzdur.Çözümümüzde tam anlamıyla bu search algoritmasını kullanacağız.
Bu algoritmayı kullanlanırken h değerini (yani puzzle'ın bir pozisyondaki önem değerini), her tuşun bu pozisyondaki yeri ile olması gereken yerinin arasındaki Manhattan mesafesinin (http://www.improvedoutcomes.com/docs/WebSiteDocs/Clustering/Clustering_Parameters/Manhattan_Distance_Metric.htm) mutlak degerlerinin toplayarak bulacağız.
Verilen bir puzzle'da öncelikle ilk pozisyon için h değerini buluyoruz ve priority queue denilen yapıya bu pozisyonu değeriyle beraber koyuyoruz. Sonra bu pozisyondan üretilebilecek pozisyonlar için aynı şekilde h hesaplamalarını yapıyoruz ve priority queue'ya koyuyoruz. Bundan sonraki adımlar bir loop'un içinde geçecek, puzzle'ın olması gerektiği pozisyona ulaşınca bu loop'tan çıkacağız.
Loop'umuz başladı.
Priority queue'dan en küçük h değerli pozisyonu çekiyoruz.
Eğer pozisyon orjinal puzzle posizyonuysa tamamdır sonuca ulaştık.
Değilse, pozisyondan üretilebilecek pozisyonları buluyoruz, h hesaplamalarını yapıyoruz ve priority queue'ya koyuyoruz.
Loop'un başına dönüyoruz.
NOT: Priority queue'ya koyarken aynı pozisyonları koymamaya dikkat edilmeli. Üsünde geçilmiş pozisyonların bir listesini array yapısında tutabilirsiniz.
NOT: Pozisyonları oluştururken, parent pozisyonlarını unutmamak gerekiyor. Bunu da bir pointerla halledebilirsiniz.
Bu greedy heuristic olup da optimal sonuca götüren bir çözümdür.
-
edit: tamam tamam
-
O zaman ben de edit..
Kısayol
Şikayet
Özel Mesaj
Alıntı yap
Cevapla