Algoritmik çözüm ben mayın tarama gemisi çözücüsü yapmaya çalışıyorum

Mayın Tarlası için. Bildiğiniz gibi, mayın tarlasında hangi alanların açılmasının güvenli olduğunu belirlemek için iki yol vardır, ya da hangi alanların mayınlandığını belirlemek ve onu işaretlemeniz gerekir. belirlemek için ilk yolu önemsiz olduğunu ve böyle bir şey var:Algoritmik çözüm ben mayın tarama gemisi çözücüsü yapmaya çalışıyorum

if (mayın sayısı etrafında X - X etrafında keşfedilen madenlerin mevcut sayısı) X etrafında Tüm açılmamış alanlar

mayınlı sonra X etrafında açılmamış alanların = sayı

if (X etrafında mayın sayısı == X etrafında keşfedilen madenlerin mevcut sayısı) daha sonra X etrafında Tüm açılmamış alanlar

mayınlı dEĞİLDİR Ama soru şudur: biz herhangi mayınlı bulamadığında durum hakkında neler veya güvenli alan ve 1'den fazla alana bakmamız gerekiyor mu? Örneğin

http://img541.imageshack.us/img541/4339/10299095.png

bu durum. Önceki yöntemi kullanarak hiçbir şey belirleyemiyoruz. Bu yüzden bu durumlarda algoritma konusunda yardıma ihtiyacım var.

Bunu yapmak için A * algoritması kullanmak zorunda. Bu yüzden algoritmada bir sonraki adım için tüm olası güvenli durumlara ihtiyacım var. Mümkün olan tüm güvenli durumları bulduğumda onları en kısa yollara ekleyeceğim ve sezgisel fonksiyona bağlı olarak yolların listesini sıralayacağım ve açılması gereken bir sonraki alanı seçeceğim.

kaynak

2013-04-11 user216799

Sen algoritması yazma önlemek ve bilgisayar kendiliğinden öğrenelim, ama sana herhangi bir daha fazla söyleyemem olabilir ..:/ – BlackBear

Sana sağlamak örneği görüntüyü anlamıyorum. En soldaki "2", soldaki ikinci satırdaki alanların çıkarıldığını, ancak ikinci "2" nin sadece birinin olduğunu öne sürer. Bu hangi oyun bağlamında ortaya çıkar? Oyunun bilgilerinin çelişkili olabileceğini mi düşünüyorsun? – pjmorse

Ancak, algoritmanızda bu görüntüde güvenli bir alan bulursunuz. İki tarafından çevrili 2 atın; iki etrafındaki mayın sayısı, ikisi arasında bulunan mevcut mayın sayısıdır. Yani üstündeki boş alanı ortaya çıkarabilirsin. Yoksa, henüz işaretlenmemiş bir bayrakla bu alana sahip olsaydınız, bu iki bayrağı işaretlemeyi nasıl bilirdiniz? – Kevin

Harika bir sorun olsa da, çok heyecanlanmadan önce lütfen NP Completeness and Minesweeper'u ve beraberindeki bazı iyi kötü durum örneklerini geliştiren presentation'u okuyun ve bir insanın bunları nasıl çözebileceğini okuyun. Yine de, temel budama ve sezgisel yaklaşımları kullanırsak, büyük ihtimalle bir zaman bariyerine çarpmayacağımıza inanıyoruz.

oyun üretme sorusu burada sorulur: Minesweeper solving algorithm. algebraic yöntemlerinde çok güzel bir yazı var. Ayrıca, yerel bilginin sudoku gibi bir şey için yeterli olmadığı durumlarda, bir deneme için geri izleme (yani, bir tahminde bulunun ve bir şeyleri geçersiz kılmaya bakın) verebilirsiniz. Bu technique ile ilgili bu büyük tartışmayı görün. @tigger olarak

kaynak

2013-04-11 19:45:01

Hatalarınızdan geri kalmanıza izin verilirse, o zaman her kareyi bir kez ortaya çıkarabilir ve hangi karelerin mayınların olduğunu görebilirsiniz. Belki de OP'nin bir insanla aynı kuralları izleyen bir çözücü aradığını düşünüyorum - bir yanlış hamle yaparsanız başarısız olursunuz. – mbeckish

Evet, elbette, başka türlü başarısız olduğunda geri izleme kullanın, ağaç katlanarak büyür. –

Ama bir madeni ortaya çıkarmadan ve oyunu kaybetmeden nasıl geri dönüş yapabilirsiniz? – mbeckish

bu kurallar basit seti ile çözülebilecek bir sorun olmadığını söyledi. Mayın Tarlası, DPLL gibi geri dönüş algoritmalarının yararlı olduğu iyi bir örnektir. Öneri mantığı kadar basit bir şeyle, mayın tarama gemisi için çok verimli bir çözücü uygulayabilirsiniz. Sana AI muhakeme & mantık çıkarım aşina emin değilim - Stuart Russel ve Peter Norvig tarafından - Değilse, kitabın "A Modern Approach Yapay Zeka" da bir göz atmak isteyebilirsiniz. DPLL ve teklif mantığına hızlı bir şekilde başvurmak için Google'da "wumpus dünyası önerme mantığı" nı arayın.

kaynak

2013-04-11 22:07:44 aaronqli

Algoritmik çözüm ben mayın tarama gemisi çözücüsü yapmaya çalışıyorum

cevap

İlgili konular