| |
|
31 Mart 2012, 19:23
| #1 | |
| Çevrimdışı  IF Ticaret Sayısı: (0) | Sırt Çantası Problemi 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ğerin vi ve ağırlığı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şalamıyacağı bilinir. Bu problem tipi değişik sınırlama koşullarına göre değişik problem tipi şekilini alabilir. Bunlardan bazıları şöyle tanımlanabilir: * "0-1 sırt çantası problemi": "Sirt çantası problem" tipleri arasında en iyi bilinen problem "0-1 sırt çantası problemi"dir. 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 deerleri 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 "tamsayı değişkeni" olur. Matematik formulasyon şöyle verilir: maksimumu bulunacak objektif fonksiyon: Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. sınırlamalar: Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. * "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 xi, 0 ile tam sayı olan ci arasında olabilir. Bu tür "sınırlı sırt çantası problemi"nin matematik formülasyonu şöyledir: . maksimum bulunacak objektif fonksiyon: Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. sınırlamalar: Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. * "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 xi, 0 ile tam sayı olan +∞ arasında olabilir. * İlgi çeken başka iki özel sırt-çantası problemi şu özellikleri ile tanımlanır: o Bu bir karar verme problemidir. o Bu problem için karar değişkeni sadece 0-1 değerleri alabilir; o Her bir madde için ağırlık o maddenin değerine eşittir; yani wi = vi. 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 tamsayı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ı" verziyonu ş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ı tesbit etmeye çalışmak olmuştur. Bu yaklaşımla NP-tam tavırlı en-fena halleri tesbit 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: | |
| |  |
| IRCForumlari.NET Reklamlar |
   |
 |
| Etiketler |
| çantası, problemi |
| Konuyu Toplam 1 Üye okuyor. (0 Kayıtlı üye ve 1 Misafir) | |
| |
Benzer Konular | ||||
| Konu | Konuyu Başlatan | Forum | Cevaplar | Son Mesaj |
| Sırt Çantası Çocuğun Bel Sağlığına Zarar Vermesin | Ecrin | Çocuk Sağlığı | 0 | 27 Şubat 2012 23:24 |
| Doğum Çantası | pyracantha | Aile Evlilik ve Çocuklar | 0 | 27 Aralık 2010 20:28 |
| Beslenme Çantası | YapraK | Aile Evlilik ve Çocuklar | 0 | 13 Ocak 2010 03:01 |
Normal
