Ancak Heule, geçmiş sonuçların keşfedilmesini canlandırıcı buldu. Diğer araştırmacıların sorunu üzerinde çalışacak kadar önemli bulduklarını gösterdi ve elde etmeye değer tek sonucun sorunu tamamen çözmek olduğunu onayladı.
“Sorun üzerinde 20 yıllık bir çalışma olduğunu anladığımızda, bu tabloyu tamamen değiştirdi” dedi.
Vulgardan Kaçınmak
Yıllar geçtikçe, Heule çok geniş olası kombinasyonlar arasında arama yapmanın etkili yollarını bularak bir kariyer edinmişti. Yaklaşımına SAT çözme denir – “tatmin edilebilirlik” in kısaltması. Boole formülü adı verilen ve iki olası sonucu olabilen uzun bir formül oluşturmayı içerir: 0 veya 1. Sonuç 1 ise, formül doğrudur ve sorun giderilmiştir.
Paketleme renklendirme problemi için, formüldeki her değişken, belirli bir hücrenin belirli bir sayı tarafından işgal edilip edilmediğini temsil edebilir. Bir bilgisayar, formülü yerine getirmek için değişken atama yollarını arar. Bilgisayar bunu yapabiliyorsa, ızgarayı belirlediğiniz koşullar altında paketlemenin mümkün olduğunu bilirsiniz.
Ne yazık ki, paketleme renklendirme probleminin bir Boole formülü olarak basit bir şekilde kodlanması milyonlarca terime kadar uzanabilir – bir bilgisayar, hatta bir bilgisayar filosu, içindeki değişkenleri atamanın tüm farklı yollarını test ederek sonsuza kadar çalışabilir.
Goddard, “Bunu saf bir şekilde yaparsanız, bu kaba kuvveti yapmaya çalışmak, evrenin sona ermesine kadar sürer” dedi. “Yani, bunu mümkün olan bir şeye indirgemek için bazı harika basitleştirmelere ihtiyacınız var.”
Üstelik salmastra renklendirme problemine her sayı eklediğinizde, olası kombinasyonların çoğalması nedeniyle yaklaşık 100 kat daha zor hale gelir. Bu, paralel çalışan bir bilgisayar bankasının tek bir günlük hesaplamada 12’yi eleyebilmesi durumunda, 13’ü elemek için 100 günlük hesaplama süresine ihtiyaç duyacakları anlamına gelir.
Heule ve Subercaseaux, kaba kuvvet hesaplama yaklaşımını büyütmeyi bir bakıma kaba buldu. Subercaseaux, “Birkaç umut verici fikrimiz vardı, bu yüzden ‘Kümede 48 saatten daha kısa bir sürede bu sorunu çözene kadar yaklaşımımızı optimize etmeye çalışalım’ zihniyetini benimsedik” dedi.
Bunu yapmak için, bilgi işlem kümesinin denemesi gereken kombinasyon sayısını sınırlamanın yollarını bulmaları gerekiyordu.
“[They] Colorado Springs, Colorado Üniversitesi’nden Alexander Soifer, “sadece çözmek değil, aynı zamanda etkileyici bir şekilde çözmek istiyorum” dedi.
Heule ve Subercaseaux, birçok kombinasyonun aslında aynı olduğunu kabul etti. Baklava şeklindeki bir taşı sekiz farklı rakamla doldurmaya çalışıyorsanız, yerleştirdiğiniz ilk sayının ortadaki karenin bir yukarı ve bir sağına veya bir aşağı ve bir soluna olması fark etmez. merkez kare. İki yerleşim birbiriyle simetriktir ve bir sonraki hamlenizi tamamen aynı şekilde kısıtlar, bu nedenle ikisini de kontrol etmek için bir neden yoktur.
Her paketleme problemi, 1’lik çapraz bir ızgaranın tüm alanı kapladığı (satranç tahtasındaki karanlık boşluklar gibi) bir satranç tahtası deseniyle çözülebilseydi, hesaplamalar büyük ölçüde basitleştirilebilirdi. Yine de, 14 sayı ile dolu bu sonlu karo örneğinde olduğu gibi, durum her zaman böyle değildir. Satranç tahtası deseni sol üste doğru birkaç yerden kırılmalıdır.Bernardo Subercaseaux ve Marijn Heule’nin izniyle
