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.

Sırt çantası problemi : Elde bulunan çeşitli birim ağırlıklı ve birim değerli kitapların en değerli olanları, en fazla 15kg taşıyabilen bir sırt çantasına yerleştirilmeli.

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 v_i ve ağırlığının w_i 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 x_i 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: ${\displaystyle \qquad \sum _{i=1}^{n}v_{i}x_{i}}$

sınırlamalar: ${\displaystyle \qquad \sum _{i=1}^{n}w_{i}x_{i}\leqslant W,\quad \quad x_{i}\in \{0,1\}}$

• "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 ${\displaystyle x_{i}}$, 0 ile tam sayı olan ${\displaystyle c_{i}}$ arasında olabilir. Bu tür "sınırlı sırt çantası problemi"nin matematik formülasyonu şöyledir: .

maksimum bulunacak objektif fonksiyon: ${\displaystyle \qquad \sum _{i=1}^{n}v_{i}x_{i}}$

sınırlamalar: ${\displaystyle \qquad \sum _{i=1}^{n}w_{i}x_{i}\leqslant W,\quad \quad x_{i}\in \{0,1,\ldots ,c_{i}\}}$

• "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 ${\displaystyle x_{i}}$, 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 ${\displaystyle w_{i}=v_{i}}$.

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 −∞ < w_i < +∞ 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.

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:
• Dallandırma-ve-sınırlama (branch-and-bound) algoritması kullanma:
• Bu iki yaklaşımın bir melez bileşimini kullanma:

Dipnotlar

1. ^ Pisinger, D. 2003. Where are the hard knapsack problems? Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark.
2. ^ L. Caccetta, A. Kulanoot, Computational Aspects of Hard Knapsack Problems, Nonlinear Analysis 47 (2001) 5547–5558.
3. ^ 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
4. ^ S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementation, John Wiley and Sons, 1990
5. ^ S. Martello, D. Pisinger, P. Toth, Dynamic programming and strong bounds for the 0-1 knapsack problem, Manag. Sci., 45:414-424, 1999.
6. ^ 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.004
7. ^ G. Plateau, M. Elkihel, A hybrid algorithm for the 0-1 knapsack problem, Methods of Oper. Res., 49:277-293, 1985.
8. ^ S. Martello, P. Toth, A mixture of dynamic programming and branch-and-bound for the subset-sum problem, Manag. Sci., 30:765-771

Ayrıca bakınız

Dış bağlantılar

• Ingilizce Wikipedia "Knapsack_problem" maddesi14 Şubat 2010 tarihinde Wayback Machine sitesinde arşivlendi. (İngilizce) (Erişim:5.6.2010).
• (İngilizce) (Erişim:5.6.2010).
• Home page of David Pisinger2 Ocak 2009 tarihinde Wayback Machine sitesinde . with downloadable copies of some papers on the publication list (including "Where are the hard knapsack problems?") (İngilizce) (Erişim:5.6.2010).
• Cesitli dillerde sirt-cantasi problem çözüm algaroritmasi28 Mart 2010 tarihinde Wayback Machine sitesinde . Kaynak: (İngilizce) (Erişim:5.6.2010).
• 0-1 sirt-cantasi problem çözüm çözümu icin dinamik programlama algoritması25 Mayıs 2010 tarihinde Wayback Machine sitesinde . (İngilizce) (Erişim:5.6.2010).
• Python yazilimli 0-1 sirt-cantasi problem çözüm algaroritmasi10 Ocak 2010 tarihinde Wayback Machine sitesinde . (İngilizce) (Erişim:5.6.2010).
• (İngilizce) (Erişim:5.6.2010).