Sırt Çantası Problemi

Bilgisayar bilimlerinde optimizasyon algoritmalarıyla ilgilenmeye başladığınızda ilk karşınıza çıkacak olarak problemlerden biri olan sırt çantası problemini biraz açıp optimum sonuç veren bir algoritma verelim bu yazımızda. Öncelikle problemin NP olduğunu belirtmekte fayda var. Dinamik programlama ile optimum sonucu elde edebiliyoruz fakat bu yeterli değil. Detaya girmeden önce problemi tanıyalım.

İsimleri 1 ile n arasında belirtilen çeşitli eşyalar olduğunu ve her  için  olarak eşyanın değerini  olarak aynı eşyanın ağırlığını belirtelim. Genellemeyi kaybetmeden her eşyanın değerinin ve ağırlığının pozitif olduğunu varsayabiliriz. Çantanın kapasitesinin W olduğu ve bunun üst sınır olacağı -aşılamayacağı- belirtiliyor.

Havada kalan ifadeler için daha anlaşılır hali olan hırsız örneğini ele alalım. Hırsız girdiği evden yükte hafif pahada değerli olan eşyaları en karlı şekilde almak istemektedir. Haliyle hırsızın taşıyabileceği maksimum miktar var. Bu yüzden yanına alacağı eşyaları en iyi şekilde seçmeli.

Problem bu noktada 0-1 Sırt Çantası Problemi, Sınırlı Sırt Çantası Problemi olarak ikiye ayrılabilir. 0-1 Probleminde her eşyadan bir adet bulunuyor ve aldığımız eşyaları 1 almadıklarımızı 0 olarak nitelendiriyoruz. Sınırlı sırt çantası probleminde ise mevcut eşyalardan birden fazla alınabileceği belirtiliyor. Ama her eşyanın adedi sınırlıdır. Bu yazımız da sırt çantası probleminin alt problemi olarak düşünülebilecek Subset Sum (Alt kümeler toplamı) problemini ele alalım.

Subset Sum Problemi:

Bir kümede tam sayılardan oluşan elemanlar bulunmaktadır. Bu kümenin öyle bir alt kümesini bulun ki bu altkümenin elemanlarının toplamı verilen S değerine en yakın olsun. Az elemanlı ve küçük tam sayılar için problemi el ile çözmek kolay olsa da eleman sayısı arttıkça ve sayılar büyüdükçe problemi el yordamı ile çözmek çok zor olacaktır. Tam bu noktada problem bilgisayar billimlerinin alanına geliyor. Öyle bir algoritma yazın ki bize makul sayılar için optimum sonucu hızlıca versin. Makul sayılar dememin sebebini problemi NP olarak tanıtmamdan kaynaklanıyor. Oluşturacağımız matris boyutu bilgisayarımızın sınırlarını zorladığında problemimizi çözüme kavuşturmamız ciddi vaktimizi alacak belki de kavuşturmayacağız.

Algoritmanın C proglamlama dilindeki yazılmış halini yazının sonunda bulabilirsiniz fakat bundan önce anlaşılabilir olması açısından anlatmaya çalışacağım.  Öncelikle (kümedeki eleman sayınız+1) x (W+1) boyutunda bir matris açın. Matrise M diyelim. Matrisinizin ilk satır ve sütunu sıfırlardan oluşsun. Matrisin kalan elemanlarını ise şu fonksiyon ile oluşturun. (  matris satırı matris sütunu belirtmektedir. )

Son durumda oluşan matrisin sağ alt indisi optimum sonucu verecektir.

  kümesi ve aranan değer 17 iken oluşan matris şu şekilde olacaktır:

Dinamik programlama ile geliştirdiğimiz bu yöntemin karmaşıklığı O(nW)’dir. Her ne kadar nW polinom gibi görünse de psudeo-polinom. Bunun sebebi ise W değerinin üssel olması. Problemin NP-Complete olmasının sebebi de budur.

İlgililere verdiğim örneğin C dilindeki kodu:

#include<stdio.h>
#define MAX(a,b) (((a)>(b))?(a):(b))
#define W 17
main()
{
int V[6]={0,2,5,11,3,9}; // ilk indisi 0 olarak kümemizi alıyoruz.
int M[6][W+1]={0}; // tüm matrise sıfır atadık başlangıç için.
for(int i=1; i<6;i++)
{
for(int j=0;j<W+1;j++)
{
if(j<V[i])
M[i][j]=M[i-1][j];
else
M[i][j]=MAX(M[i-1][j],M[i-1][j-V[i]] + V[i]);
}
}
for(int i=0;i<6;i++)// matrisi yazdırıyoruz.
{
for(int j=0;j<18;j++)
printf("%3d",M[i][j]);
printf("\n");
}
}

Yazıyı Hazırlayan: Metin Turgay

Dokuz Eylül Üniversitesi matematik bölümü 4. sınıf öğrencisiyim. Bilgisayar Bilimleri bölümünde yandal yapmaktayım. Hobi olarak başlayan bu heves gün geçerek artmaya devam etti. Matematik ile bilgisayarın kavuştuğu alanları öğrenmekten elimden geldiği kadar da öğretmekten zevk alıyorum. Yazılarım da genelde bu çerçevede olacaktır.

Bunlara da Göz Atın

Aklınızda Kalacak Bazı Matematiksel Gerçekler

Çoğu insan matematiğin sıkıcı olduğuna inanır fakat gerçekte öyle değildir, aksine tam tersi gibi gözükmekte… …

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

ga('send', 'pageview');