8 Bilmece Problemi

[Erdem]

8 Bilmece Problemini A* arama algoritması kullanarak çözebilirmisiniz?

8 Bilmece Problemi

[ahmet_matematikci]

A* algoritması nedir ki

------------------------------
Pardon yazım yanlışı var sanmıştım A* algoritması diye bir şey gerçketen varmış.

[Erdem]

A* ağaç ya da çizit gibi veri yapılarıyla kullanılan bir arama algoritması.

Bu arama algoritmalarından örneğin derinine arama algoritması önce en derine kadar gidip sonra diğer dalları inceliyor.

Örneğin bir zaman yazdığım bu uygulamada Pacman yolu derinine arama algoritması kullanarak buluyor.

http://www.zayifakim.org/resim/resim/pacmandfs.mp4

A*'nın gerçekleşmesini de buradan inceleyebilirsiniz.

http://bgrins.github.io/javascript-astar/demo/

Bizim örneğimizde aslında A* algoritmasını yazıyorsunuz ama bu algoritmanın  gerçekleştirilmesini soruyu çözerek yapıyorsunuz.

Ama öncelikli kuyruğun nasıl çalıştığını bilmek gerekebilir.

Buna da örnek olarak normal kuyruğu vermek istiyorum. Normal kuyruğa sırayla 8 1 6 7 2 ekledik diyelim. Çıkarken bunlar gene  8 1 6 ..  şeklinde çıkıyor. Normal kuyruk için ilk giren ilk çıkar.

Öncelikli kuyrukta ise 8 1 6 7 2 ekledik. Çıkarken bizim örneğimizdeki gibi düşük öncelikli ise 1 2 6 7 8 şeklinde çıkar.

Denemek isterseniz ilkönce tahta sınıfının gerçeklemesinden başlayabilirsiniz.

[ahmet_matematikci]

@Erdem Bu soruyu çözebildin mi?

[Erdem]

Evet çözdüm 

Ama 4x4 tahtaların zor olanlarından bir tanesini çözebiliyor. Diğer ikisini çözemiyor.

Zaten çözümde de tüm 4x4 bulmacaları çözmesi beklenmiyor.

Örneğin 3x3 tahta için 9!/2=181.440 dizilim ortaya çıkarken kolayca çözülüyor. 4x4 tahtalar için 1.3 trilyon dizilim ortaya çıkıyor ve en iyi arama algoritmaları bunları bir kaç milisaniyede çözebiliyormuş.

5x5 tahtalar için ise 10^25 tane dizilim ortaya çıkıyor ve rastgele olanlarını çözmek saatler alıyormuş.

[ahmet_matematikci]

Çözümü paylaşacak mısın

[Erdem]

Hayır. 

Ama çözmek isteyen olursa, çözüm yolu konusunda yardım edebilirim.

[ahmet_matematikci]

sebep

[Erdem]

Kursa kayıt olurken kabul ettiğiniz etik kuralları arasında soruların çözümlerini paylaşmayacağım diye bir ifade varmış. Ben daha sonra acaba başka bir programlama dilinde paylaşsak olur mu diye sordum ama olumlu yanıt gelmedi   

[ahmet_matematikci]

Bu kurs hangi ilde kimin kursu...Ne kursu acaba...
Budist rahipler gibi ne yemini.. ..
Şimdi daha çok ilgi mi çekti bu kursun notları var mı? Şimdi o da yasaktır.

[Erdem]

Bu Princeton Üniversitesi'nin kursu 

Ders notlarına da buradan erişebilirsiniz.

http://algs4.cs.princeton.edu/lectures/