Sırt çantası problemi

Sırt çantası problemi (İngilizce: "knapsack problem") bir klasik yöneylem araştırması ve matematiksel olarak "kombinatorik optimizasyon" problemidir. Çözüm algoritması bakımından sırt çantası problemi en ünlü NP-hard problemleri arasındadır.

 Tanımlanma 

"Sırt çantası problemi"nin tanımlanması için şu notasyon kullanılmaktadır: İsimleri 1 ile n arasında sayı ile ifade edilen n değişik madde bulunur. Her bir madde i için değerinin vi ve ağırlığının wi olduğu bilinmektedir. Genel olarak her bir değer ve her bir ağırlık negatif olamazlar. Çanta içinde taşınabilecek tüm maddelerin toplam ağırlığının en çok W olup, bunun bir üst sınır olup aşılamayacağı bilinir.

Bu problem tipi değişik sınırlama koşullarına göre değişik problem tipi şeklini alabilir. Bunlardan bazıları şöyle tanımlanabilir:
 "0-1 sırt çantası problemi": "Sırt çantası problem" tipleri arasında en iyi bilinen problem "0-1 sırt çantası problemi"dır. Bu tip problemde mevcut n maddeden her biri ya 1 birim olarak çantaya konulur yahut çantaya konulmaz, yani 0 birim çantaya koyulur. Her bir madde tek birim olarak çantaya konulur ya koyulmaz. Çantaya konulup konulmama, sadece 1 ve 0 değerleri alan "çantada mevcut olup olmama" adı verilebilen iki kategorili değer alan bir karar değişkeni olur. Böylece karar değiskeni olan xi ya 0 ya da 1 değeri alan iki kategorili "tam sayı değişkeni" olur. Matematik formülasyon şöyle verilir:

maksimumu bulunacak objektif fonksiyon: 
sınırlamalar: 

 "Sınırlı sırt çantası problemi": Bu tür problemde sırt çantası içine her maddeden birden fazla yerleştirilebilmek imkânı olduğu kabul edilir. Ama her bir madde için mevcut madde adedi sınırlıdır; i maddesi için mevcut sayı olan , 0 ile tam sayı olan  arasında olabilir. Bu tür "sınırlı sırt çantası problemi"nin matematik formülasyonu şöyledir: .

maksimum bulunacak objektif fonksiyon: 
sınırlamalar: 

 "Sınırsız sırt çantası problemi": Bu tür problemde her madde sıfırdan sınırsız sayıya kadar sırt çantası içine yerleştirilebilir. i maddesi için sırt çantasına yerleştirilen sayı, yani , 0 ile tam sayı olan +∞ arasında olabilir.
 İlgi çeken başka iki özel sırt-çantası problemi şu özellikleri ile tanımlanır:
 Bu bir karar verme problemidir.
 Bu problem için karar değişkeni sadece 0-1 değerleri alabilir.
 Her bir madde için ağırlık o maddenin değerine eşittir; yani .
Bu şekildeki özel problem şu değişik şekilde de ifade edilebilir: bir negatif olmayan sayılar seti verilmiş ise, bunun herhangi bir altsetinin toplamı W toplam ağırlık/değer sınırına eşit olabilir mi?

Buna benzer diğer bir özel problem, eğer her bir madde için negatif olan ağırlık mümkünse (yani −∞ < wi < +∞ ise) ve toplam ağırlık sınırı en çok W sıfıra eşit ise (yani W=0 olursa) ortaya çıkar. Problem şu olur: bir tam sayılar veri seti verilirse, bunun herhangi bir alt-seti tam olarak 0a eşit olabilir mi? Buna "alt-set toplamı problemi" adı verilir. Kriptografi alanında sırt-çantası problemi" ismi sadece bu çok özel "alt-set toplam∞ problemi" olarak görülür.

Eğer tek bir değil ama birden fazla sırt-çantası yüklemek mümkün ise, bu yeni tip probleme "kutu paketleme problemi" adı verilir.

 Çözüm hesaplanmanın karmaşıklığı 

Konu bilgisayar bilimi bakış açısından ele alınırsa "sırt-çantası problemi" şu nedenler dolayısıyla ilgi çekmektedir:
 Dinamik programlama kullanarak "sözde-polinomsal zamanda" çözüm sağlayan algoritma bulunmaktadır.
 "Sözde-polinomsal zamanda" çözümü sağlayan algoritmaları bir alt-program olarak kullanan "FPTAS yaklaşık tam polinomsal zaman kullanma" yordamı ile çözüm bulunmak imkân dahilindedir.
 Tam olarak çözüm için problem NP-tam karakterlidir ve her türlü halde hem hatasız hem de hızlı polinomsal zamanda çözme algoritması bulmak imkânsızdır.
 Pratikte, buna rağmen birçok halde ve bazı dağılımlardan bazı rastgele haller'' verileri kullanılarak pek çok sayıda problem için tam şekilde çözüm yapma için kullanma imkânı bulunmaktadır

Problemin polinomsal zamanda çözümü ispatlanabilirse P = NP savı da ispatlanmış olacaktır.

"Alt-set toplamı" versiyonu şekildeki sırt-çantası problemi, genellikle, "Karp'in 21 NP-tam problemler"inden biri olduğu bilinmektedir.

Araştırma kaynaklarında ilgi çeken bir konu sırt-çantası probleminin "zor" şekillerinin nasıl görünüş alacağını tespit etmeye çalışmak olmuştur. Bu yaklaşımla NP-tam tavırlı en-fena halleri tespit edip bunları daha kolay uygulanır şekillere koyma imkânları araştırılmıştır.Pisinger, D. 2003. Where are the hard knapsack problems? Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark.L. Caccetta, A. Kulanoot, Computational Aspects of Hard Knapsack Problems, Nonlinear Analysis 47 (2001) 5547–5558.

Sırt-çantası problemlerini çözümlemek için parasız kullanılmaları imkânı olan birkaç tane algoritma yazılımı hazır bulunmaktadır. Bunlardan seçilmişleri şu listede verilir:
 Dinamik programlama yaklaşımına dayanan algoritma kullanma:Rumen Andonov, Vincent Poirriez, Sanjay Rajopadhye (2000) Unbounded Knapsack Problem : dynamic programming revisited European Journal of Operational Research 123: 2. 168-181 http://dx.doi.org/10.1016/S0377-2217(99)00265-9
 Dallandırma-ve-sınırlama (branch-and-bound) algoritması kullanma:S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementation, John Wiley and Sons, 1990
 Bu iki yaklaşımın bir melez bileşimini kullanma:S. Martello, D. Pisinger, P. Toth, Dynamic programming and strong bounds for the 0-1 knapsack problem, Manag. Sci., 45:414-424, 1999.Vincent Poirriez, Nicola Yanev, Rumen Andonov (2009) A Hybrid Algorithm for the Unbounded Knapsack Problem  Discrete Optimization http://dx.doi.org/10.1016/j.disopt.2008.09.004G. Plateau, M. Elkihel, A hybrid algorithm for the 0-1 knapsack problem, Methods of Oper. Res., 49:277-293, 1985.S. Martello, P. Toth, A mixture of dynamic programming and branch-and-bound for the subset-sum problem, Manag. Sci., 30:765-771

 Dipnotlar 

 Dış bağlantılar 
 PYAsUKP: Sinirsiz Sirt Cantasi Problemi Icin Bir Diger Cozucu, yazilim kodlari, sinama sonuclar ve bazi onemli makaleler.  (Erişim:5.6.2010).
 Home page of David Pisinger with downloadable copies of some papers on the publication list (including  "Where are the hard knapsack problems?")  (Erişim:5.6.2010).
  Cesitli dillerde sirt-cantasi problem çözüm algaroritmasi Kaynak: Rosetta Code  (Erişim:5.6.2010).
  0-1 sirt-cantasi problem çözüm çözümu icin dinamik programlama algoritması  (Erişim:5.6.2010).
 Python yazilimli 0-1 sirt-cantasi problem çözüm algaroritmasi  (Erişim:5.6.2010).
 Interactive JavaScript branch-and-bound solver  (Erişim:5.6.2010).

Kategori:Bilgisayar
Kategori:Yöneylem araştırması