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 değiştir

"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:

\qquad \sum _{i=1}^{n}v_{i}x_{i}

sınırlamalar:

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

maksimum bulunacak objektif fonksiyon:

\qquad \sum _{i=1}^{n}v_{i}x_{i}

sınırlamalar:

\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 $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 $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ığı değiştir

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.^[1]^[2]

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:^[3]
Dallandırma-ve-sınırlama (branch-and-bound) algoritması kullanma:^[4]
Bu iki yaklaşımın bir melez bileşimini kullanma:^[5]^[6]^[7]^[8]

Dipnotlar değiştir

^ 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.
^ 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
^ S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementation , John Wiley and Sons, 1990
^ 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.004
^ G. 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

Ayrıca bakınız değiştir

Dış bağlantılar değiştir

Ingilizce Wikipedia "Knapsack_problem" maddesi14 Şubat 2010 tarihinde Wayback Machine sitesinde arşivlendi. (İngilizce) (Erişim:5.6.2010).
PYAsUKP: Sinirsiz Sirt Cantasi Problemi Icin Bir Diger Cozucu, yazilim kodlari, sinama sonuclar ve bazi onemli makaleler. (İngilizce) (Erişim:5.6.2010).
Home page of David Pisinger2 Ocak 2009 tarihinde Wayback Machine sitesinde arşivlendi. 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 arşivlendi. Kaynak: Rosetta Code (İ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 arşivlendi. (İngilizce) (Erişim:5.6.2010).
Python yazilimli 0-1 sirt-cantasi problem çözüm algaroritmasi10 Ocak 2010 tarihinde Wayback Machine sitesinde arşivlendi. (İngilizce) (Erişim:5.6.2010).
Interactive JavaScript branch-and-bound solver (İngilizce) (Erişim:5.6.2010).

[pisinger200308-1] Pisinger, D. 2003. Where are the hard knapsack problems? Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark.

[Cacetta2001-2] L. Caccetta, A. Kulanoot, Computational Aspects of Hard Knapsack Problems, Nonlinear Analysis 47 (2001) 5547–5558.

[eduk2000-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

[martellototh90-4] S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementation , John Wiley and Sons, 1990

[martellopisingertoth99a-5] S. Martello, D. Pisinger, P. Toth, Dynamic programming and strong bounds for the 0-1 knapsack problem , Manag. Sci., 45:414-424, 1999.

[poirriez_et_all_2009-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

[plateau85-7] G. Plateau, M. Elkihel, A hybrid algorithm for the 0-1 knapsack problem, Methods of Oper. Res., 49:277-293, 1985.

[martellotothe99-8] S. Martello, P. Toth, A mixture of dynamic programming and branch-and-bound for the subset-sum problem, Manag. Sci., 30:765-771

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]