Dudley's Hat Probleminin Çözüm Algoritması
Dudley's Hat problemindeki artan dizi ve alt küme toplamı kısıtlarını dinamik olarak denetleyerek arama alanını azaltmayı amaçlayan; tarihsel proje kaydında 27 değerine ulaşan algoritma çalışması.
Bu proje, Dudley's Hat olarak kayıt altına aldığım kombinatoryal problem için farklı bir arama yaklaşımı geliştirme çalışmasıdır.
Mevcut proje tanımındaki kısıta göre sayılar 1'den başlayarak üç farklı diziye yerleştiriliyor. Yeni bir sayının ilgili diziye eklenebilmesi için o dizide daha önce oluşan alt küme toplamlarıyla çakışmaması ve dizinin son elemanından büyük olması gerekiyor.
Asıl Maliyet: Alt Küme Toplamları
Yeni bir aday sayının geçerli olup olmadığını denetlemek için daha önceki elemanların oluşturabildiği toplamların bilinmesi gerekir. Bu toplamları her adayda baştan üretmek arama maliyetini hızla büyütür.
Geliştirdiğim yaklaşımın temel fikri, daha önce hesaplanmış durumdan yararlanarak adayın geçerliliğini dinamik biçimde kontrol etmekti. Böylece bütün olasılıkları baştan sona tekrar kuran brute-force yaklaşımına göre daha dar bir arama alanı elde edilebiliyordu.
Tarihsel Sonuç
Eski proje kaydında elle yapılan çözüm ve karşılaştırılan diğer yaklaşımlar için ulaşılan en büyük değer 21, geliştirdiğim algoritma için ise 27 olarak kayıtlıdır.
Bu sayfada, aradan geçen süre içinde özgün deney düzeninin bütün ayrıntıları elimde olmadığı için bu sonucu yeni bir matematiksel rekor veya evrensel optimum iddiasına dönüştürmüyorum. Doğru ifade, projenin kendi problem tanımı ve uygulama koşulları altında 27 değerine ulaştığıdır.
Dinamik Arama ile Paralellik Farkı
Bir arama uzayını daha fazla iş parçacığına bölmek ile arama uzayının kendisini küçültmek farklı optimizasyonlardır. Paralellik aynı sayıda durumu daha kısa sürede deneyebilir; iyi bir durum temsili veya budama ise denenmesi gereken durum sayısını azaltır.
Bu çalışma benim için algoritma optimizasyonunda bu ayrımı erken dönemde görünür hale getirdi.
Benzer üstel arama ve dinamik programlama karşılaştırmasını Subset Sum Optimizasyonu projesinde; genel karmaşıklık çerçevesini ise Veri Yapıları ve Algoritma Analizi notunda ele alıyorum.
