Sırt çantası sorunu - Knapsack problem

Tek boyutlu (kısıtlı) bir sırt çantası problemi örneği: Toplam ağırlığı 15 kg'ın altında veya buna eşit tutarken para miktarını en üst düzeye çıkarmak için hangi kutular seçilmelidir? Bir çoklu kısıtlı problem kutuların hem ağırlığını hem de hacmini dikkate alabilir.
(Çözüm: Her kutunun herhangi bir numarası varsa, üç sarı kutu ve üç gri kutu; yalnızca gösterilen kutular varsa, yeşil kutu hariç tümü.)

sırt çantası sorunu bir problemdir kombinatoryal optimizasyon: Her biri bir ağırlık ve bir değere sahip bir dizi öğe verildiğinde, toplam ağırlığın belirli bir sınırdan az veya ona eşit ve toplam değerin olabildiğince büyük olması için bir koleksiyona dahil edilecek her öğenin sayısını belirleyin. Adını, sabit bir boyutla kısıtlanan birinin karşılaştığı sorundan alır. sırt çantası ve en değerli eşyalarla doldurmalıdır. Sorun genellikle şu şekilde ortaya çıkar: kaynak tahsisi Karar vericilerin, sırasıyla sabit bir bütçe veya zaman kısıtlaması altında bir dizi bölünemez proje veya görev arasından seçim yapması gerektiğinde.

Sırt çantası sorunu, 1897 yılına kadar uzanan ilk çalışmalarla bir asırdan fazla bir süredir inceleniyor.^[1] "Sırt çantası problemi" adı matematikçinin ilk çalışmalarına kadar uzanır. Tobias Dantzig (1884–1956),^[2] ve en değerli veya faydalı eşyaların bavulu aşırı yüklemeden ambalajlanmasına ilişkin genel problemi ifade eder.

Başvurular

Stony Brook Üniversitesi Algoritma Deposunun 1999 yılında yapılan bir çalışması, 75 algoritmik problemden sırt çantası probleminin en popüler 19. ve sonra en çok ihtiyaç duyulan üçüncü problem olduğunu gösterdi. sonek ağaçları ve çöp kutusu paketleme sorunu.^[3]

Sırt çantası sorunları, hammaddeleri kesmenin en az israflı yolunu bulmak gibi çok çeşitli alanlarda gerçek dünyadaki karar verme süreçlerinde ortaya çıkıyor.^[4] seçimi yatırımlar ve portföyler,^[5] için varlık seçimi varlığa dayalı menkul kıymetleştirme,^[6] ve için anahtarlar oluşturmak Merkle – Hellman^[7] ve diğeri sırt çantası şifreleme sistemleri.

Sırt çantası algoritmalarının ilk uygulamalarından biri, test katılımcılarının hangi soruları cevaplayacakları konusunda bir seçim yapabildikleri testlerin oluşturulması ve puanlanmasıydı. Küçük örnekler için, sınava girenlere böyle bir seçim sağlamak oldukça basit bir süreçtir. Örneğin, bir sınav her biri 10 puan değerinde 12 soru içeriyorsa, sınav katılımcısının maksimum olası 100 puan alabilmesi için yalnızca 10 soruyu yanıtlaması gerekir. Bununla birlikte, puan değerlerinin heterojen dağılımına sahip testlerde, seçenekler sunmak daha zordur. Feuerman ve Weiss, öğrencilerin toplam 125 olası puanla heterojen bir teste tabi tutulduğu bir sistem önerdi. Öğrencilerden tüm soruları ellerinden gelen en iyi şekilde yanıtlamaları istenir. Toplam puan değerleri toplamı 100 olan olası problem alt kümelerinden, bir sırt çantası algoritması, hangi alt kümenin her öğrenciye mümkün olan en yüksek puanı verdiğini belirleyecektir.^[8]

Tanım

Çözülen en yaygın sorun, 0-1 sırt çantası sorununumarayı kısıtlayan ${displaystyle x_ {i}}$ her tür öğenin kopyalarının sıfıra veya bire. Bir dizi verildiğinde ${displaystyle n}$ 1'den ile numaralandırılmış öğeler ${displaystyle n}$her birinin ağırlığı ${displaystyle w_ {i}}$ ve bir değer ${displaystyle v_ {i}}$maksimum ağırlık kapasitesiyle birlikte ${displaystyle W}$,

maksimize etmek ${displaystyle toplamı _ {i = 1} ^ {n} v_ {i} x_ {i}}$

tabi ${displaystyle toplamı _ {i = 1} ^ {n} w_ {i} x_ {i} leq W}$ ve ${0,1}} içinde {displaystyle x_ {i}$.

Buraya ${displaystyle x_ {i}}$ öğenin örnek sayısını temsil eder ${displaystyle i}$ sırt çantasına dahil etmek. Gayri resmi olarak sorun, sırt çantasındaki eşyaların değerlerinin toplamını maksimize etmektir, böylece ağırlıkların toplamı sırt çantasının kapasitesinden daha az veya ona eşit olur.

sınırlı sırt çantası sorunu (BKP) her bir öğeden yalnızca birinin olduğu kısıtlamasını kaldırır, ancak sayıyı sınırlar ${displaystyle x_ {i}}$ her tür öğenin kopyalarının maksimum negatif olmayan tam sayı değerine ${displaystyle c}$:

maksimize etmek ${displaystyle toplamı _ {i = 1} ^ {n} v_ {i} x_ {i}}$

tabi ${displaystyle toplamı _ {i = 1} ^ {n} w_ {i} x_ {i} leq W}$ ve ${0,1,2, dots, c} içinde {displaystyle x_ {i}.}$

sınırsız sırt çantası sorunu (UKP) her tür öğenin kopya sayısına üst sınır koymaz ve yukarıdaki gibi formüle edilebilir, tek kısıtlama ${displaystyle x_ {i}}$ negatif olmayan bir tam sayı olmasıdır.

maksimize etmek ${displaystyle toplamı _ {i = 1} ^ {n} v_ {i} x_ {i}}$

tabi ${displaystyle toplamı _ {i = 1} ^ {n} w_ {i} x_ {i} leq W}$ ve ${displaystyle x_ {i} geq 0, x_ {i} matematikte {Z}.}$

Sınırsız sırt çantası sorununun bir örneği, bu makalenin başında gösterilen şekil ve bu şeklin başlığındaki "her kutunun herhangi bir numarası varsa" metni kullanılarak verilmiştir.

Hesaplama karmaşıklığı

Sırt çantası sorunu, birçok nedenden ötürü bilgisayar bilimi açısından ilginçtir:

• karar problemi sırt çantası sorununun şekli (En azından bir değer olabilir V ağırlığı aşmadan elde edilebilir W?) dır-dir NP tamamlandı bu nedenle, her durumda hem doğru hem de hızlı (çok terimli zaman) bilinen bir algoritma yoktur.
• Karar problemi NP-tam iken, optimizasyon problemi değildir, çözünürlüğü en az karar problemi kadar zordur ve bir çözüm verildiğinde optimal olup olmadığını söyleyebilecek bilinen bir polinom algoritması yoktur (bu, daha büyük bir çözümün olmadığını V, böylece NP-tam karar problemini çözer).
• Var sözde polinom zaman algoritma kullanıyor dinamik program.
• Var tam polinom zamanlı yaklaşım şeması Sözde polinom zaman algoritmasını bir alt rutin olarak kullanan, aşağıda açıklanmıştır.
• Pratikte ortaya çıkan birçok durum ve bazı dağıtımlardan "rastgele örnekler" yine de tam olarak çözülebilir.

"Karar" ve "optimizasyon" problemleri arasında bir bağlantı vardır, çünkü "karar" problemini çözen bir polinom algoritması varsa, o zaman bu algoritmayı yinelemeli olarak uygulayarak polinom zamanda optimizasyon problemi için maksimum değeri bulabilir. k değerini arttırmak. Öte yandan, eğer bir algoritma, optimizasyon probleminin optimal değerini polinom zamanında bulursa, bu algoritma ile çözüm çıktısının değeri k değeri ile karşılaştırılarak karar problemi polinom zamanda çözülebilir. Bu nedenle, sorunun her iki versiyonu da benzer zorluktadır.

Araştırma literatüründeki bir tema, sırt çantası sorununun "zor" durumlarının neye benzediğini belirlemektir.^[9][10] veya uygulamada örneklerin hangi özelliklerinin onları en kötü NP-tam davranışlarının gösterdiğinden daha uygun hale getirebileceğini belirlemek için başka bir şekilde incelendi.^[11] Bu "zor" durumları bulmanın amacı, açık anahtarlı kriptografi sistemler, örneğin Merkle-Hellman sırt çantası şifreleme sistemi.

Ayrıca, sırt çantası sorununun sertliğinin girdinin şekline bağlı olması da dikkate değerdir. Ağırlıklar ve karlar tamsayı olarak verilirse, zayıf NP tamamlandı iken kesinlikle NP-tamamlandı ağırlıklar ve karlar rasyonel sayılar olarak verilirse.^[12] Ancak, rasyonel ağırlıklar ve karlar söz konusu olduğunda, yine de tam polinom zamanlı yaklaşım şeması.

Çözme

Dinamik programlama yaklaşımına dayanan sırt çantası problemlerini çözmek için çeşitli algoritmalar mevcuttur.^[13] dal ve sınır yaklaşmak^[14] veya melezlemeler her iki yaklaşımın.^{[11][15][16][17]}

Dinamik programlama önceden algoritma

sınırsız sırt çantası sorunu (UKP) her tür öğenin kopya sayısına herhangi bir sınırlama getirmez. Ayrıca, burada varsayıyoruz ki ${displaystyle x_ {i}> 0}$

${displaystyle m [w '] = maksimum sol (toplam _ {i = 1} ^ {n} v_ {i} x_ {i} ight)}$

tabi ${displaystyle toplamı _ {i = 1} ^ {n} w_ {i} x_ {i} leq w '}$ ve ${displaystyle x_ {i}> 0}$

Bunu gözlemleyin ${displaystyle m [w]}$ aşağıdaki özelliklere sahiptir:

1. ${displaystyle m [0] = 0 ,!}$ (sıfır öğelerin toplamı, yani boş kümenin toplamı).

2. ${displaystyle m [w] = max (v_ {1} + m [w-w_ {1}], v_ {2} + m [w-w_ {2}], ..., v_ {i} + m [ w-w_ {i}])}$, ${displaystyle w_ {i} leq w}$, nerede ${displaystyle v_ {i}}$ değeridir ${displaystyle i}$-çeşitli öğe.

İkinci özelliğin ayrıntılı olarak açıklanması gerekiyor. Bu yöntemin çalıştırılması sürecinde ağırlığı nasıl alırız ${displaystyle w}$? Sadece var ${displaystyle i}$ yollar ve önceki ağırlıklar ${displaystyle w-w_ {1}, w-w_ {2}, ..., w-w_ {i}}$ toplam nerede ${displaystyle i}$ farklı öğe türleri (farklı diyerek, ağırlık ve değerin tamamen aynı olmadığını kastediyoruz). Bunların her bir değerini bilirsek ${displaystyle i}$ öğeleri ve ilgili maksimum değeri daha önce, sadece birbirleriyle karşılaştırıyoruz ve sonuçta maksimum değeri elde ediyoruz ve işimiz bitti.

Burada boş kümenin maksimumu sıfır olarak alınır. Sonuçların tablo haline getirilmesi ${displaystyle m [0]}$ doğruca yukarı ${displaystyle m [W]}$ çözümü verir. Her birinin hesaplanmasından beri ${displaystyle m [w]}$ en çok incelemeyi içerir ${displaystyle n}$ öğeler ve en fazla ${displaystyle W}$ değerleri ${displaystyle m [w]}$ hesaplamak için, dinamik programlama çözümünün çalışma süresi ${displaystyle O (nW)}$. Bölme ${displaystyle w_ {1} ,, w_ {2} ,, ldots ,, w_ {n} ,, W}$ onlar tarafından en büyük ortak böleni çalışma süresini iyileştirmenin bir yoludur.

Bile P ≠ NP, ${displaystyle O (nW)}$ karmaşıklık, sırt çantası sorununun şu olduğu gerçeğiyle çelişmez: NP tamamlandı, dan beri ${displaystyle W}$aksine ${displaystyle n}$, probleme girdi uzunluğunda polinom değildir. Uzunluğu ${displaystyle W}$ probleme girdi, bit sayısıyla orantılıdır ${displaystyle W}$, ${displaystyle log W}$değil ${displaystyle W}$ kendisi. Ancak, bu çalışma zamanı olduğundan psödopolinom Bu, sırt çantası problemini (karar versiyonunun) bir zayıf NP-tam problem.

0-1 sırt çantası sorunu

0-1 sırt çantası problemi için benzer bir dinamik programlama çözümü de sözde polinom zamanda çalışır. Varsaymak ${displaystyle w_ {1} ,, w_ {2} ,, ldots ,, w_ {n} ,, W}$ kesinlikle pozitif tamsayılardır. Tanımlamak ${displaystyle m [i, w]}$ daha az veya eşit ağırlıkta elde edilebilecek maksimum değer olmak ${displaystyle w}$ kadar öğe kullanma ${displaystyle i}$ (ilk ${displaystyle i}$ öğeler).

Tanımlayabiliriz ${displaystyle m [i, w]}$ aşağıdaki gibi yinelemeli olarak: (Tanım A)

• ${displaystyle m [0,, w] = 0}$
• ${displaystyle m [i ,, w] = m [i-1,, w]}$ Eğer ${displaystyle w_ {i}> w ,!}$ (yeni ürün mevcut ağırlık limitinden fazla)
• ${displaystyle m [i ,, w] = max (m [i-1,, w] ,, m [i-1, w-w_ {i}] + v_ {i})}$ Eğer ${displaystyle w_ {i} leqslant w}$.

Çözüm daha sonra hesaplanarak bulunabilir ${displaystyle m [n, W]}$. Bunu verimli bir şekilde yapmak için, önceki hesaplamaları depolamak için bir tablo kullanabiliriz.

Aşağıdaki dinamik program için sözde koddur:

 1 // Girdi: 2 // Değerler (dizi v'de saklanır) 3 // Ağırlıklar (w dizisinde saklanır) 4 // Farklı öğe sayısı (n) 5 // Sırt çantası kapasitesi (W) 6 // NOT: "v" dizisi ve "w" dizisinin, dizin 1'den başlayarak tüm ilgili değerleri depoladığı varsayılır. 7  8 için j itibaren 0 -e W yapmak: 9     m[0, j] := 010 11 için ben itibaren 1 -e n yapmak:12     için j itibaren 0 -e W yapmak:13         Eğer w[ben] > j sonra:14             m[ben, j] := m[ben-1, j]15         Başka:16             m[ben, j] := max(m[ben-1, j], m[ben-1, j-w[ben]] + v[ben])

Bu çözüm bu nedenle çalışacak ${displaystyle O (nW)}$ zaman ve ${displaystyle O (nW)}$ Uzay.

Bununla birlikte, bir veya iki adım daha ileri götürürsek, yöntemin aradaki zamanda çalışacağını bilmeliyiz. ${displaystyle O (nW)}$ ve ${displaystyle O (2 ^ {n})}$. Nereden Tanım A, seçtiğimiz öğelerin sayısı ve öğelerin kendileri sabit olduğunda tüm ağırlıkları hesaplamaya gerek olmadığını bilebiliriz. Yani, yukarıdaki program beklenenden daha fazla hesaplar çünkü ağırlık her zaman 0'dan W'ye değişir. Tek yapmamız gereken, m [i, j] için m [i-1, j] ve m [i-1, jw [i]] + v [i] 'yi karşılaştırmak ve m [i-1, jw [i]] aralık dışında, sadece m [i-1, j] 'nin değerini m [i, j]' ye veriyoruz. Bu perspektiften, bu yöntemi yinelemeli olarak çalışacak şekilde programlayabiliriz.

 1 // Girdi: 2 // Değerler (dizi v'de saklanır) 3 // Ağırlıklar (w dizisinde saklanır) 4 // Farklı öğe sayısı (n) 5 // Sırt çantası kapasitesi (W) 6 // NOT: "v" dizisi ve "w" dizisinin, dizin 1'den başlayarak tüm ilgili değerleri depoladığı varsayılır. 7  8 Tanımlamak değer[n, W] 9 10 Başlat Herşey değer[ben, j] = -111 12 Tanımlamak m:=(ben,j)         // m işlevini, koşul altında alabileceğimiz maksimum değeri temsil edecek şekilde tanımlayın: ilk i öğeleri kullanın, toplam ağırlık sınırı j'dir13 {14     Eğer ben == 0 veya j <= 0 sonra:15         değer[ben, j] = 016         dönüş17 18     Eğer (değer[ben-1, j] == -1) sonra:     // m [i-1, j] hesaplanmadı, m fonksiyonunu çağırmalıyız19         değer[ben-1, j] = m(ben-1, j)20 21     Eğer w[ben] > j sonra:                      // eşya çantaya sığmıyor (BU ÖNCEKİ ALGORİTMEDEN KAYIP)22         değer[ben, j] = değer[ben-1, j]23     Başka: 24         Eğer (değer[ben-1, j-w[ben]] == -1) sonra:     // m [i-1, j-w [i]] hesaplanmadı, m fonksiyonunu çağırmalıyız25             değer[ben-1, j-w[ben]] = m(ben-1, j-w[ben])26         değer[ben, j] = max(değer[ben-1,j], değer[ben-1, j-w[ben]] + v[ben])27 }28 29 Koşmak m(n, W)

Örneğin 10 farklı ürün var ve ağırlık limiti 67. Yani,

${displaystyle {egin {hizalı} & w [1] = 23, w [2] = 26, w [3] = 20, w [4] = 18, w [5] = 32, w [6] = 27, w [7] = 29, w [8] = 26, w [9] = 30, w [10] = 27 & v [1] = 505, v [2] = 352, v [3] = 458, v [ 4] = 220, v [5] = 354, v [6] = 414, v [7] = 498, v [8] = 545, v [9] = 473, v [10] = 543 end {hizalı }}}$

Hesaplamak için yukarıdaki yöntemi kullanırsanız ${displaystyle m (10,67)}$, Alacaksın (m (i, j) = 0 üreten çağrılar hariç):

${displaystyle {egin {hizalı} & m (10,67) = 1270 & m (9,67) = 1270, m (9,40) = 678 & m (8,67) = 1270, m (8,40) = 678, m (8,37) = 545 & m (7,67) = 1183, m (7,41) = 725, m (7,40) = 678, m (7,37) = 505 & m (6 , 67) = 1183, m (6,41) = 725, m (6,40) = 678, m (6,38) = 678, m (6,37) = 505 & m (5,67) = 1183 , m (5,41) = 725, m (5,40) = 678, m (5,38) = 678, m (5,37) = 505 & m (4,67) = 1183, m (4, 41) = 725, m (4,40) = 678, m (4,38) = 678, m (4,37) = 505, m (4,35) = 505 & m (3,67) = 963, m (3,49) = 963, m (3,41) = 505, m (3,40) = 505, m (3,38) = 505, m (3,37) = 505, m (3,35 ) = 505, m (3,23) = 505, m (3,22) = 458, m (3,20) = 458 & m (2,67) = 857, m (2,49) = 857, m (2,47) = 505, m (2,41) = 505, m (2,40) = 505, m (2,38) = 505, m (2,37) = 505, m (2,35) = 505, m (2,29) = 505, m (2,23) = 505 & m (1,67) = 505, m (1,49) = 505, m (1,47) = 505, m ( 1,41) = 505, m (1,40) = 505, m (1,38) = 505, m (1,37) = 505, m (1,35) = 505, m (1,29) = 505, m (1,23) = 505 end {hizalı}}}$

Ayrıca özyinelemeyi kırıp bir ağaca dönüştürebiliriz. Daha sonra bazı yaprakları kesebilir ve bu yöntemin çalışmasını hızlandırmak için paralel hesaplamayı kullanabiliriz.

Ortada buluşmak

0-1 sırt çantası için başka bir algoritma, 1974'te keşfedildi^[18] ve bazen paralelliklerinden dolayı "ortada buluşma" olarak adlandırılır kriptografide benzer şekilde adlandırılmış bir algoritma, farklı öğelerin sayısında üsteldir ancak DP algoritmasına tercih edilebilir ${displaystyle W}$ ile karşılaştırıldığında büyük n. Özellikle, eğer ${displaystyle w_ {i}}$ negatif değildir ancak tamsayı değildir, dinamik programlama algoritmasını ölçekleyerek ve yuvarlayarak (ör. sabit noktalı aritmetik ), ancak sorun gerektiriyorsa ${displaystyle d}$ Doğru cevaba ulaşmak için kesirli kesinlik basamakları, ${displaystyle W}$ ölçeklenmesi gerekecek ${displaystyle 10 ^ {d}}$ve DP algoritması şunları gerektirecektir: ${displaystyle O (W10 ^ {d})}$ uzay ve ${displaystyle O (nW10 ^ {d})}$ zaman.

algoritma Ortada buluşmak dır-dir    giriş: Ağırlık ve değerlere sahip bir dizi öğe. çıktı: Bir alt kümenin en büyük birleşik değeri. kümeyi bölümle {1 ...n} iki küme halinde Bir ve B yaklaşık olarak eşit büyüklükte olan her bir setin tüm alt kümelerinin ağırlıklarını ve değerlerini hesaplar her biri için alt küme nın-nin Bir yapmak        alt kümesini bul B en yüksek değere sahip, öyle ki birleşik ağırlık, W    şimdiye kadar görülen en büyük birleşik değeri takip edin

Algoritma alır ${displaystyle O (2 ^ {n / 2})}$ alan ve adım 3'ün verimli uygulamaları (örneğin, B'nin alt kümelerini ağırlığa göre sıralamak, B'nin diğer alt kümelerinden daha büyük veya eşit değere sahip alt kümelerini atmak ve en iyi eşleşmeyi bulmak için ikili aramayı kullanmak) çalışma zamanı ${displaystyle O (n2 ^ {n / 2})}$. Olduğu gibi orta atakta buluşmak kriptografide bu, ${displaystyle O (n2 ^ {n})}$ saf kaba kuvvet yaklaşımının çalışma zamanı (tüm alt kümeleri inceleyerek ${displaystyle {1 ... n}}$), sabit alan yerine üstel alan kullanma pahasına (ayrıca bkz. bebek adımı dev adım ).

Yaklaşık algoritmalar

NP-tam sorunların çoğuna gelince, optimal olmasalar bile uygulanabilir çözümler bulmak yeterli olabilir. Bununla birlikte, tercihen, yaklaşım, bulunan çözümün değeri ile optimal çözümün değeri arasındaki farkın garantisiyle birlikte gelir.

Yararlı ancak hesaplama açısından karmaşık birçok algoritmada olduğu gibi, bir çözüme yaklaşan algoritmalar oluşturma ve analiz etme konusunda önemli araştırmalar yapılmıştır. Sırt çantası problemi, NP-Hard olsa da, yine de belirli bir dereceye yaklaştırılabilen bir algoritma koleksiyonundan biridir. Bu, sorunun bir polinom zaman yaklaşım şemasına sahip olduğu anlamına gelir. Kesin olarak, sırt çantası problemi tamamen polinom zaman yaklaşım şemasına (FPTAS) sahiptir.^[19]

Açgözlü yaklaşım algoritması

George Dantzig önerdi açgözlü yaklaşım algoritması Sınırsız sırt çantası sorununu çözmek için.^[20] Onun sürümü, öğeleri ağırlık birimi başına düşen değer sırasına göre sıralar, ${displaystyle v_ {1} / w_ {1} geq cdots geq v_ {n} / w_ {n}}$. Ardından, çuvalda daha fazla yer kalmayana kadar birinci türden mümkün olduğunca çok sayıda kopya ile başlayarak onları çuvala yerleştirmeye devam eder. Her tür ürün için sınırsız tedarik olması koşuluyla, ${displaystyle m}$ çuvala uyan öğelerin maksimum değeridir, bu durumda açgözlü algoritmanın en azından şu değeri elde etmesi garanti edilir: ${displaystyle m / 2}$.

Her tür öğenin arzının sınırlı olduğu sınırlı problem için, yukarıdaki algoritma optimal olmaktan uzak olabilir. Yine de basit bir değişiklik bu durumu çözmemizi sağlar: Bir çözüm oluşturun ${displaystyle S_ {1}}$ öğeleri mümkün olduğunca uzun süre açgözlülükle paketleyerek, yani ${displaystyle S_ {1} = sol {1, ldots, kight}}$ nerede ${displaystyle k = extstyle max _ {1leq k'leq n} extstyle toplam _ {i = 1} ^ {k} w_ {i} leq W}$. Dahası, ikinci bir çözüm oluşturun ${displaystyle S_ {2} = sol {k + 1gece}}$ uymayan ilk öğeyi içeren. Dan beri ${displaystyle S_ {1} fincan S_ {2}}$ için bir üst sınır sağlar LP gevşemesi problemin en azından setlerden birinin değeri olmalıdır ${displaystyle m / 2}$; böylece hangisini iade ederiz ${displaystyle S_ {1}}$ ve ${displaystyle S_ {2}}$ elde etmek için daha iyi bir değere sahiptir ${displaystyle 1/2}$-yaklaşıklık.

Tamamen polinom zaman yaklaşım şeması

tam polinom zaman yaklaşımı şeması Sırt çantası problemi için (FPTAS), sorunun bilinen polinom zaman çözümlerine sahip olmamasının nedeninin, öğelerle ilişkili kârların kısıtlanmaması gerçeğinden yararlanmaktadır. Biri, kar değerlerinin en önemsiz rakamlarından bazılarını yuvarlarsa, o zaman bunlar bir polinom ve 1 / ile sınırlanır; burada ε, çözümün doğruluğuna bağlıdır. Bu kısıtlama, daha sonra bir algoritmanın, polinom zamanında, optimal çözümün (1-) faktörü içinde doğru olan bir çözüm bulabileceği anlamına gelir.^[19]

algoritma FPTAS dır-dir     giriş: ε ∈ (0,1] değerleri ile belirtilen n öğeden oluşan bir A listesi, ${displaystyle v_ {i}}$ve ağırlıklar çıktı: S 'FPTAS çözümü P: = maks ${displaystyle {v_ {i} orta 1 leq ileq n}}$  // en yüksek öğe değeri K: = ε ${displaystyle {frac {P} {n}}}$    için ben itibaren 1 -e n yapmak        ${displaystyle v '_ {i}}$ := ${displaystyle leftlfloor {frac {v_ {i}} {K}} ightfloor}$    sonu için    dönüş çözüm, S ', kullanarak ${displaystyle v '_ {i}}$ yukarıda özetlenen dinamik programdaki değerler

Teorem: Set ${görüntü stili S '}$ Yukarıdaki algoritma tarafından hesaplanan tatmin edici ${displaystyle mathrm {kar} (S ') geq (1-varepsilon) cdot mathrm {kâr} (S ^ {*})}$, nerede ${görüntü stili S ^ {*}}$ optimal bir çözümdür.

Hakimiyet ilişkileri

Sınırsız sırt çantası sorununu çözmek, asla ihtiyaç duyulmayacak eşyaları atarak daha kolay hale getirilebilir. Belirli bir öğe için ${displaystyle i}$bir dizi öğe bulabileceğimizi varsayalım ${displaystyle J}$ öyle ki toplam ağırlıkları, ${displaystyle i}$ve bunların toplam değeri, değerinden daha büyük ${displaystyle i}$. Sonra ${displaystyle i}$ en uygun çözümde görünemez, çünkü her zaman olası bir çözümü iyileştirebiliriz. ${displaystyle i}$ değiştirerek ${displaystyle i}$ set ile ${displaystyle J}$. Bu nedenle, göz ardı edebiliriz ${displaystyle i}$-nci öğe tamamen. Bu gibi durumlarda, ${displaystyle J}$ söylendi hakim olmak ${displaystyle i}$. (Bu, sınırlı sırt çantası sorunları için geçerli değildir, çünkü öğeleri daha önce ${displaystyle J}$.)

Hakimiyet ilişkilerini bulmak, arama alanının boyutunu önemli ölçüde azaltmamızı sağlar. Birkaç farklı tür vardır hakimiyet ilişkileri,^[11] hepsi biçim eşitsizliğini tatmin eder:

${displaystyle qquad toplamı _ {jin J} w_ {j}, x_ {j} leq alfa, w_ {i}}$, ve ${displaystyle sum _ {jin J} v_ {j}, x_ {j} geq alpha, v_ {i},}$ bazı ${displaystyle xin Z _ {+} ^ {n}}$

nerede${Z _ {+} ,, Jsubsetneq N'deki görüntü stili alfa$ ve ${görüntü stili J olarak}$. Vektör ${displaystyle x}$ her bir üyenin kopya sayısını gösterir ${displaystyle J}$.

Kolektif hakimiyet

${displaystyle i}$-nci öğe toplu olarak hakim tarafından ${displaystyle J}$, olarak yazılmıştır ${görüntü tarzı kötü J}$, içindeki bazı öğe kombinasyonlarının toplam ağırlığı ${displaystyle J}$ daha az w_ben ve toplam değeri şundan büyük v_ben. Resmen, ${displaystyle sum _ {jin J} w_ {j}, x_ {j} leq w_ {i}}$ ve ${displaystyle sum _ {jin J} v_ {j}, x_ {j} geq v_ {i}}$ bazı ${displaystyle xin Z _ {+} ^ {n}}$yani ${displaystyle alpha = 1}$. Bu hakimiyetin doğrulanması hesaplama açısından zordur, bu nedenle yalnızca dinamik bir programlama yaklaşımıyla kullanılabilir. Aslında bu, daha küçük bir sırt çantası karar problemini çözmeye eşdeğerdir. ${displaystyle V = v_ {i}}$, ${displaystyle W = w_ {i}}$ve öğeler şunlarla sınırlıdır: ${displaystyle J}$.

Eşik hakimiyeti

${displaystyle i}$-nci öğe eşik hakim tarafından ${displaystyle J}$, olarak yazılmıştır ${displaystyle iprec Prec J}$, eğer birkaç kopya ${displaystyle i}$ hakimdir ${displaystyle J}$. Resmen, ${displaystyle sum _ {jin J} w_ {j}, x_ {j} leq alpha, w_ {i}}$, ve ${displaystyle sum _ {jin J} v_ {j}, x_ {j} geq alpha, v_ {i},}$ bazı ${displaystyle xin Z _ {+} ^ {n}}$ ve ${displaystyle alpha geq 1}$. Bu, ilk olarak^[13] ve EDUK algoritmasında kullanılmıştır. En küçüğü böyle ${displaystyle alpha}$ tanımlar eşik öğenin ${displaystyle i}$, yazılı ${displaystyle t_ {i} = (alfa -1) w_ {i}}$. Bu durumda, en uygun çözüm en fazla ${displaystyle alpha -1}$ Kopyaları ${displaystyle i}$.

Çoklu hakimiyet

${displaystyle i}$-nci öğe çoğalmak tek bir öğeyle ${displaystyle j}$, olarak yazılmıştır ${displaystyle ill _ {m} j}$, Eğer ${displaystyle i}$ bazı kopyaların baskın olduğu ${displaystyle j}$. Resmen, ${displaystyle w_ {j}, x_ {j} leq w_ {i}}$, ve ${displaystyle v_ {j}, x_ {j} geq v_ {i}}$ bazı ${displaystyle x_ {j}, Z _ {+}}$ yani ${displaystyle J = {j}, alpha = 1, x_ {j} = lfloor {frac {w_ {i}} {w_ {j}}} kat}$. Bu hakimiyet, nispeten kolay tespit edilebildiği için ön işlem sırasında verimli bir şekilde kullanılabilir.

Modüler hakimiyet

İzin Vermek ${displaystyle b}$ ol en iyi eşyayani ${displaystyle {frac {v_ {b}} {w_ {b}}} geq {frac {v_ {i}} {w_ {i}}},}$ hepsi için ${displaystyle i}$. Bu, en yüksek değer yoğunluğuna sahip öğedir. ${displaystyle i}$-nci öğe modüler hakim tek bir öğeyle ${displaystyle j}$, olarak yazılmıştır ${displaystyle ill _ {equiv} j}$, Eğer ${displaystyle i}$ hakimdir ${displaystyle j}$ artı birkaç kopyası ${displaystyle b}$. Resmen, ${displaystyle w_ {j} + tw_ {b} leq w_ {i}}$, ve ${displaystyle v_ {j} + tv_ {b} geq v_ {i}}$ yani ${displaystyle J = {b, j}, alpha = 1, x_ {b} = t, x_ {j} = 1}$.

Varyasyonlar

Temel problemin çok sayıda uygulamasından ortaya çıkan sırt çantası probleminin birçok çeşidi vardır. Ana varyasyonlar, öğe sayısı, hedef sayısı ve hatta sırt çantası sayısı gibi bazı sorun parametrelerinin sayısını değiştirerek meydana gelir.

Çok amaçlı sırt çantası sorunu

Bu varyasyon, sırt çantasını dolduran kişinin amacını değiştirir. Parasal kârı maksimize etmek gibi tek bir amaç yerine, hedefin birkaç boyutu olabilir. Örneğin, ekonomik hedeflerin yanı sıra çevresel veya sosyal endişeler olabilir. Sıklıkla ele alınan sorunlar portföy ve nakliye lojistik optimizasyonlarını içerir.^[21][22]

Örnek olarak, bir yolcu gemisi işlettiğinizi varsayalım. Kaç ünlü komedyeni tutacağınıza karar vermelisiniz. Bu tekne bir tondan fazla yolcu taşıyamaz ve eğlencelerin ağırlığı 1000 lbs'den az olmalıdır. Her komedyenin bir ağırlığı vardır, popülerliklerine göre iş yapar ve belirli bir maaş ister. Bu örnekte, birden çok hedefiniz var. Tabii ki, maaşlarını en aza indirirken eğlencelerinizin popülaritesini en üst düzeye çıkarmak istiyorsunuz. Ayrıca, olabildiğince çok eğlenceye sahip olmak istersiniz.

Çok boyutlu sırt çantası sorunu

Bu varyasyonda, sırt çantası öğesinin ağırlığı ${displaystyle i}$ D boyutlu bir vektörle verilir ${displaystyle {overline {w_ {i}}} = (w_ {i1}, ldots, w_ {iD})}$ ve sırt çantasının D boyutlu bir kapasite vektörü vardır ${displaystyle (W_ {1}, ldots, W_ {D})}$. Hedef, sırt çantasındaki öğelerin değerlerinin toplamını maksimize etmektir, böylece her boyuttaki ağırlıkların toplamı ${displaystyle d}$ aşmaz ${displaystyle W_ {d}}$.

Çok boyutlu sırt çantası hesaplama açısından sırt çantasından daha zordur; için bile ${görüntü stili D = 2}$sorun yok EPTAŞ P hariç${displaystyle =}$NP.^[23] Ancak, algoritma^[24] seyrek örnekleri verimli bir şekilde çözdüğü gösterilmiştir. Çok boyutlu sırt çantası örneği, bir set varsa seyrekleşir ${displaystyle J = {1,2, ldots, m}}$ için ${displaystyle m$ öyle ki her sırt çantası için ${displaystyle i}$, ${görüntü stili vardır z> m}$ öyle ki ${displaystyle forall jin Jcup {z}, w_ {ij} geq 0}$ ve ${displaystyle forall yotin Jcup {z}, w_ {iy} = 0}$. Bu tür durumlar, örneğin, röle düğümleri olan bir kablosuz ağdaki paketleri planlarken meydana gelir.^[24] Algoritma^[24] aynı zamanda çoktan seçmeli varyant, çoktan seçmeli çok boyutlu sırt çantasının seyrek örneklerini de çözer.

IHS (Artan Yükseklik Rafı) algoritması, 2D sırt çantası (kareleri iki boyutlu birim boyutunda bir kareye paketleme) için idealdir: optimal bir paketlemede en fazla beş kare olduğunda.^[25]

Birden fazla sırt çantası sorunu

Bu varyasyon şuna benzer Kutu Paketleme Sorunu. Kutu Paketleme Probleminden farklı olarak, bir öğe alt kümesinin seçilebilmesi, oysa Kutu Paketleme Probleminde tüm öğelerin belirli kutulara paketlenmesi gerekir. Kavram, birden fazla sırt çantası olmasıdır. Bu önemsiz bir değişiklik gibi görünebilir, ancak ilk sırt çantasının kapasitesine katkıda bulunmaya eşdeğer değildir. Bu varyasyon Yöneylem Araştırmasında birçok yükleme ve çizelgeleme probleminde kullanılır ve bir Polinom zaman yaklaşım şeması.^[26]

İkinci dereceden sırt çantası sorunu

İkinci dereceden sırt çantası problemi, ikili ve doğrusal kapasite kısıtlamalarına tabi ikinci dereceden bir amaç fonksiyonunu en üst düzeye çıkarır.^[27] Sorun 1980'de Gallo, Hammer ve Simeone tarafından ortaya atıldı,^[28] ancak sorunun ilk tedavisi 1975'te Witzgall'a kadar uzanıyor.^[29]

Alt küme toplamı sorunu

alt küme toplamı sorunu her bir öğe türünün ağırlığının değere eşit olduğu, kararın ve 0-1 sorununun özel bir durumudur: ${displaystyle w_ {i} = v_ {i}}$. Nın alanında kriptografi, dönem sırt çantası sorunu genellikle, özellikle alt küme toplam sorununa atıfta bulunmak için kullanılır ve genellikle aşağıdakilerden biri olarak bilinir: Karp'ın 21 NP-tam problemi.^[30]

Alt küme toplam probleminin genelleştirilmesine, aynı kapasiteye sahip birden çok bölmenin bulunduğu çoklu alt küme toplamı problemi denir. Genellemenin bir FPTAS'a sahip olmadığı gösterilmiştir.^[31]

Ayrıca bakınız

Notlar

Referanslar

• Garey, Michael R.; David S. Johnson (1979). Bilgisayarlar ve İnatçılık: NP-Tamlık Teorisine Bir Kılavuz. W.H. Özgür adam. ISBN  978-0-7167-1045-5. A6: MP9, sayfa 247.
• Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Sırt Çantası Sorunları. Springer. doi:10.1007/978-3-540-24777-7. ISBN  978-3-540-40286-2. BAY  2161720.
• Martello, Silvano; Toth, Paolo (1990). Sırt çantası problemleri: Algoritmalar ve bilgisayar uygulamaları. Wiley-Interscience. ISBN  978-0-471-92420-3. BAY  1086874.

Dış bağlantılar

• Silvano Martello ve Paolo Toth'un hazırladığı "Sırt çantası sorunları: Algoritmalar ve bilgisayar uygulamaları" kitabının ücretsiz indirilmesi
• Sırt çantası sorunu üzerine ders slaytları
• PYAsUKP: Sınırsız Sırt Çantası Sorununu Bir Başka Çözücü, hibrit bir algoritmadaki baskınlık ilişkilerinden yararlanan kod ile, bazı makalelerin karşılaştırmaları ve indirilebilir kopyaları.
• David Pisinger'ın ana sayfası yayın listesindeki bazı makalelerin indirilebilir kopyaları ("Zor sırt çantası sorunları nerede?" dahil)
• Birçok dilde Sırt Çantası Problem çözümleri -de Rosetta Kodu
• 0/1 Sırt çantası problemine Dinamik Programlama algoritması
• Sırt Çantası Problem çözücü (çevrimiçi)
• Ruby'de Genetik Algoritmalarla 0-1-KNAPSACK'i Çözme
• İkinci Dereceden Sırt Çantası Problemi Kodları

• Üç Boyutlu Kutu Paketlemeyi Optimize Etme
• Python'da Sırt Çantası Tam Sayı Programlama Çözümü Gekko (optimizasyon yazılımı)