Kaba kuvvet çözümümü bu soruna nasıl optimize edebilirim?
Aşağıda açıklanan soruna bir çözüm bulmaya çalışıyorum. Kaba kuvvet kullanıyorum, çözümlerin engelleyici olduğu noktaya ulaştım, bu yüzden (mümkünse) daha fazlasını optimize etmem gerekiyor. Elbette, sorunu çözmenin daha iyi bir yolu varsa (kaba kuvvet değil) daha da iyi olacaktır.
Çözümümü iyileştirmek için yapabileceğim herhangi bir şey veya inceleyebileceğim referans var mı (benzer sorunlar vb.)?
Sorun
Dikdörtgen bir tahta ile başlıyoruz. Her hücre N durumda olabilir ve her hücre için başlangıç durumu rastgele (0 <= durum <N) her hücre için. Ayrıca tümü panonun içine sığan bir dizi şekle sahibiz. Her şekil süreklidir.
Her şekil tahtaya bir kez (ve yalnızca bir kez) yerleştirilmelidir. Bir şekil yerleştirildiğinde, şekle ait olan her hücrenin değeri 1 artar. Herhangi bir hücredeki pano değeri N'ye ulaşırsa, 0 olarak değiştirilir.
Amaç, her şeklin yerleştirilmesi gereken pozisyonları bulmaktır, böylece son panoda 0 değerine sahip tüm hücreler bulunur. Problemin bitmiş tahtadan başlayıp rastgele pozisyonlarda rastgele şekiller uygulayarak üretildiğini varsayalım.
Tahta boyutu, durum sayısı N ve şekil sayısı oyunun kurgusudur ve her 'seviye' için artmaya devam eder (farklı oranlarda).
Şu anda ne yapıyorum
Sadece kaba kuvvet kullanarak sorunu belli bir boyuta kadar çözebiliyorum. Yerinde birkaç optimizasyonum var. Çözümün engelleyici olduğu bir noktaya geldim, bu yüzden mantığımı geliştirmek istiyorum.
Yaptığım ilk şey şekli büyükten küçüğe sıralamak, küçüğün iç yinelemelerde taşınması. Varsayım (kanıtlamadığım, ancak daha hızlı olduğu test edildi), çözüm üretme şansları daha yüksek olduğu için küçük şekilleri daha fazla hareket ettirmenin daha iyi olacağıdır.
İkinci olarak, tekrarlanan şekiller için, aynı sonucu verdikleri için tüm permütasyonları kontrol etmekten kaçınırım. Bir çift aynı şekil üst üste geldiğinde yalnızca bir dizi konumu kontrol ederim (çünkü tüm örtüşmeler aynı sonucu verir).
Çok yardımcı olacağını düşündüğüm, ancak hala uyguladığım son bir optimizasyon şudur: dizideki her bir şekilde, taşınacak olan şekillerdeki toplam hücre sayısını sayın. Bu sayı, bitmiş bir tahtayı elde etmek için gereken toplam hücre dönüşleri eksi N'nin katı olmalıdır. Değilse, kalan şekil konumlarını zorlamak anlamsız değildir ve bir şekli harici bir döngüde yeniden konumlandırmalıyız.
Ekstra detaylar
Bunun nasıl optimize edileceğine dair başka ipuçlarıyla ilgileniyorum. Daha fazla araştırma yapmak için kullanabileceğim bilinen algoritmalar, bu problem seti için iyi bir isimlendirme bile harika olurdu.
Yanıtlar
Tamsayı doğrusal programlama
Probleminiz şu şekilde formüle edilebilir: bize vektörler veriliyor $v_{i,j} \in (\mathbb{Z}/N\mathbb{Z})^d$, kurulun olduğu yer $d$ hücreler ve amaç, bir vektör verildiğinde $c \in (\mathbb{Z}/N\mathbb{Z})^d$bir işlev bul $f$ Böylece $\sum_i v_{i,f(j)}=c$. Bu problem daha sonra tamsayı doğrusal programlama ile çözülebilir. Bu bir ile ilgilidir$d$boyutlu alt küme toplamı problemi, böylece çok boyutlu alt küme toplamı için başka algoritmalar bulabilir ve bunları deneyebilirsiniz.
Onu bu şekilde nasıl formüle ederiz? Izgara varsa$d$ hücreler, bir şekli bir $d$- Şeklin kapladığı hücrelerde 1'lerle 0'ların ve 1'lerin vektörü. Her şekil, farklı vektörler verecek şekilde birkaç farklı konuma yerleştirilebilir.$v_{i,j}$ karşılık gelir $j$şeklin bulunduğu yer $i$ yerleştirilebilir. $c$ başlangıçta ızgaradaki sayılara karşılık gelir (bu sayıların olumsuzlanması, modulo $N$). Tüm aritmetik modulo yapılır$N$.
Biraz daha akıllı kaba kuvvet
Alternatif olarak, burada hafızayı takas ederek biraz kaba kuvvet geliştirmenin bir yolu var. Varsayalım ki$k$şekiller. İlk yerleştirmenin tüm yollarını sıralayarak başlayın.$k/2$şekilleri tamamen sıfırlardan oluşan boş bir panoya yerleştirin ve ortaya çıkan tüm konumları hashtable veya sıralı bir listede saklayın. Sonra, sonuncuyu yerleştirmek için tüm yolları sıralayın.$k/2$şekillerini başlangıç konumuna getirin ve hashtable veya sıralı listedeki sonuç konumlarının her birini arayın. Herhangi bir eşleşme bulursanız, bu bir çözüm sağlar. Bu, sınırsız miktarda belleğiniz varsa, kaba kuvveti biraz daha ileri - potansiyel olarak yaklaşık iki kat daha fazla şekle - itmenize izin verecektir. Bunu en üst düzeye çıkarmakla ilgili pek çok ayrıntı var, ancak kaba kuvvet sizi yaklaştırırsa ancak biraz eksik kalırsa düşünebileceğiniz bir fikirdir. Hala bir üstel zaman algoritmasıdır, bu yüzden yine de bir sınıra ulaşacaktır.