Birçok zor LeetCode problemi aslında kolay kısıt problemi

• LeetCode'daki zor problemler bile kısıt çözücüleri kullanıldığında çok daha kolay çözülebilir
• Karmaşık dinamik programlama ya da özel algoritmalar yerine MiniZinc gibi kısıt çözücüleri kullanılarak matematiksel optimizasyon problemleri basitçe çözülebilir
• Geleneksel programlama dilleri bu tür matematiksel optimizasyon problemlerini ifade etmekte zorlandığından, kısıt tabanlı yaklaşım burada güçlüdür
• İstisna durumları veya ek kısıtlar ortaya çıktığında da kısıt çözücülerindeki modelde çok az değişiklik yapmak yeterlidir
• Çalışma zamanı karmaşıklığı elle yazılmış optimize algoritmalardan daha yavaş olabilir, ancak esneklik ve geliştirme verimliliği açısından birçok avantaj sunar

---

Kısıt çözücü ile çözülen LeetCode problemleri

Doğru aracın seçimi

• Yazar, üniversiteden mezun olduktan sonraki ilk mülakatında "bozuk para üstü problemi" ile karşılaştı

  • Verilen bozuk para birimleriyle, belirli bir tutarı ödemek için gereken en az bozuk para sayısını bulma problemidir
  • Basit bir açgözlü algoritma kullandı, ancak bu yöntem her durumda en iyi çözümü garanti etmiyordu
  • Doğru yaklaşım dinamik programlamaydı, ancak bunu uygulayamadığı için mülakatta başarısız oldu

• Ancak algoritmayı doğrudan kendiniz yazmak yerine MiniZinc gibi bir kısıt çözücü kullanarak bunu çok kolay çözebilirsiniz

  • Örnek kod:

    int: total;
    array[int] of int: values = [10, 9, 1];
    array[index_set(values)] of var 0..: coins;
    
    constraint sum (c in index_set(coins)) (coins[c] * values[c]) == total;
    solve minimize sum(coins);
    

  • Çevrimiçi olarak doğrudan MiniZinc örneğini çalıştırabilirsiniz

  • Çözücü en iyi çözümü adım adım bulur

Çeşitli optimizasyon/tatmin problemleri

• LeetCode vb. platformlarda sık görülen matematiksel optimizasyon problemleri (amaç fonksiyonunu maksimize/minimize etme ve birden çok kısıt içerme),
  programlama dilleriyle çözüldüğünde düşük seviyeli uygulama ayrıntıları yüzünden zordur; ancak kısıt çözücüler için uygundur
• Örneğin, aşağıdaki türde çeşitli problemler buna girer

Örnek 1: Maksimum hisse senedi kârı problemi

• "Liste halinde verilen hisse fiyatları verisinde, bir kez alıp daha sonra satarak elde edilebilecek maksimum kârı bulun"
  • Geleneksel olarak O(n²) brute force ya da O(n) optimal algoritma gerekir
  • MiniZinc'te bu, aşağıdaki gibi basit bir kısıt problemi olarak tanımlanabilir

    array[int] of int: prices = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
    var int: buy;
    var int: sell;
    var int: profit = prices[sell] - prices[buy];
    
    constraint sell > buy;
    constraint profit > 0;
    solve maximize profit;
    

Örnek 2: Belirli sayıların toplanması/çıkarılmasıyla 0 elde etmek (tatmin problemi)

• "Bir listedeki üç sayıyı toplayarak veya çıkararak 0 elde etmek mümkün mü?"
  • En iyi değeri değil, yalnızca tatmin edilebilir bir çözüm bulmak yeterlidir
  • Kısıt çözücüde şu şekilde ifade edilebilir

    include "globals.mzn";
    array[int] of int: numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
    array[index_set(numbers)] of var {0, -1, 1}: choices;
    
    constraint sum(n in index_set(numbers)) (numbers[n] * choices[n]) = 0;
    constraint count(choices, -1) + count(choices, 1) = 3;
    solve satisfy;
    

Örnek 3: Histogramda en büyük dikdörtgen alanı

• "Çubuk yükseklikleri verilen bir histogramda oluşturulabilecek en büyük dikdörtgen alanını bulun"
  • Geleneksel olarak karmaşık algoritmalar ve çok sayıda durum yönetimi gerekir
  • Çözüm yalnızca kısıtlarla özlü biçimde anlatılabilir

    array[int] of int: numbers = [2,1,5,6,2,3];
    
    var 1..length(numbers): x; 
    var 1..length(numbers): dx;
    var 1..: y;
    
    constraint x + dx <= length(numbers);
    constraint forall (i in x..(x+dx)) (y <= numbers[i]);
    
    var int: area = (dx+1)*y;
    solve maximize area;
    
    output ["(\(x)->\(x+dx))*\(y) = \(area)"]
    

Kısıt çözücü yaklaşımı daha mı iyi?

• Mülakat ortamında zaman karmaşıklığı gibi sorular karşısında zayıf kalabilir

  • Kısıt çözücülerin çalışma süresini öngörmek zordur ve genellikle özel tasarlanmış optimal algoritmalardan daha yavaştır
  • Ancak kötü uygulanmış düşük kaliteli bir algoritmadan yine de daha iyidir; ayrıca çoğu programcı için her seferinde en iyi çözümü sıfırdan yazmak kolay değildir

• Asıl güçlü yön, yeni kısıtlar eklerken sağlanan esnekliktir

  • Örneğin, hisse senedi örneğinde yalnızca bir kez değil birçok kez alım satım yapacak şekilde değiştirmek istendiğinde algoritmanın karmaşıklığı hızla artar
  • MiniZinc'in kısıt modelinde ise çok küçük kod değişiklikleriyle çok daha karmaşık gereksinimler karşılanabilir

    include "globals.mzn";
    int: max_sales = 3;
    int: max_hold = 2;
    array[int] of int: prices = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8];
    array [1..max_sales] of var int: buy;
    array [1..max_sales] of var int: sell;
    array [index_set(prices)] of var 0..max_hold: stocks_held;
    var int: profit = sum(s in 1..max_sales) (prices[sell[s]] - prices[buy[s]]);
    
    constraint forall (s in 1..max_sales) (sell[s] > buy[s]);
    constraint profit > 0;
    
    constraint forall(i in index_set(prices)) (stocks_held[i] = (count(s in 1..max_sales) (buy[s] <= i) - count(s in 1..max_sales) (sell[s] <= i)));
    constraint alldifferent(buy ++ sell);
    solve maximize profit;
    
    output ["buy at \(buy)\n", "sell at \(sell)\n", "for \(profit)"];
    

• Çevrimiçi kısıt problemi örnekleri genellikle Sudoku gibi bulmacalara odaklansa da, gerçekte iş mantığı veya optimizasyon gereksinimi olan problemlerde daha ilginç ve pratik şekilde kullanılabilir

  • Örneğin symmetry breaking (simetri kırma) gibi ileri optimizasyon tekniklerini uygulama potansiyeli de yüksektir

Kapanış ve notlar

• Bu yazı, yazarın haftalık bülteninden alınmıştır ve yazılım tarihi, biçimsel yöntemler, yeni teknolojiler, yazılım mühendisliği teorisi gibi konuları ele alır
• İlgileniyorsanız abone olabilir veya yazarın ana web sitesine göz atabilirsiniz
• Yazarın yeni kitabı "Logic for Programmers" da yayımlanıyor