Simülasyonlarda Döngü Algılama

Bazı benzetimler, trilyon gibi çok büyük sayıda adımdan sonraki durumu sorar. Tek tek adım atmak zamanında asla tamamlanmazdı. ⏳

Olası durumların sayısı sınırlıysa benzetim sonunda mutlaka daha önce görülen bir duruma döner. Bundan sonra sonsuza kadar bir döngü içinde tekrarlanır.

Yolun döngüye giren bir kuyruğu ve ardından tekrarlanan bir döngüsü vardır. Döngüyü fark etmek, milyarlarca adımı atlayarak ilerlemenizi sağlar.

Her durumu, onu ilk gördüğünüz adım numarasıyla eşleyen bir sözlükte saklayın. Durumu yeniden görmek döngüyü ortaya çıkarır.

Her adımdan önce mevcut durumun görülen kümesinde olup olmadığını kontrol edin. Varsa döngüyü az önce kapatmışsınız demektir.

Uzunluk, mevcut adım ile bu durumu ilk gördüğünüz adım arasındaki farktır. Bu kadar adım, durumu yeniden tam olarak başlangıç noktasına getirir.

Kuyruğu çıkarın, ardından kalan adımların sayısını döngü uzunluğuna bölerek kalanını alın. Artık yalnızca çok küçük bir artığı benzetmeniz gerekir.

Benzetimi, döngünün başlangıcından itibaren yalnızca bu kalan adım sayısı kadar çalıştırın. Son durum tam olarak N. adımdaki durumla eşleşir.

Sözlük anahtarları özetlenebilir olmalıdır; bu nedenle listeleri saklamadan önce demetlere dönüştürün. Değişebilir bir durum anahtar olamaz.

Durumlar saklanamayacak kadar büyükse, Floyd'un kaplumbağa ve tavşan yöntemi iki işaretçi kullanarak neredeyse hiç ek bellek harcamadan bir döngü bulur.

Döngü tespiti, imkânsız bir trilyon adımlı döngüyü birkaç bin adıma dönüştürür. İşin tüm püf noktası tekrarı fark etmektir.

Mevcut durumu ilk kez s adımında gördünüz ve şimdi t adımındasınız.

Durumlar tekrarlandığında her birini bir eşlemede kaydedin, döngü uzunluğunu bulun, kalan alma işlemiyle ileriyi atlayın ve yalnızca artakalan adımları benzetin. 🚀