Paketlemeyi ayarla - Set packing

Paketlemeyi ayarla bir klasik NP tamamlandı sorun hesaplama karmaşıklığı teorisi ve kombinatorik ve şunlardan biriydi Karp'ın 21 NP-tam problemi.

Varsayalım ki bir Sınırlı set S ve bir listesi alt kümeler nın-nin S. Daha sonra, set paketleme problemi bazılarının k Listedeki alt kümeler çiftlidir ayrık (başka bir deyişle, hiçbiri bir unsuru paylaşmaz).

Daha resmi olarak, bir evren verildiğinde ${ displaystyle { mathcal {U}}}$ ve bir aile ${ displaystyle { mathcal {S}}}$ alt kümelerinin ${ displaystyle { mathcal {U}}}$, bir paketleme bir alt ailedir ${ displaystyle { mathcal {C}} subseteq { mathcal {S}}}$ tüm setler olacak şekilde ${ displaystyle { mathcal {C}}}$ ikili ayrıktır. Ambalajın boyutu ${ displaystyle | { mathcal {C}} |}$. Set ambalajında karar problemi giriş bir çift ${ displaystyle ({ mathcal {U}}, { mathcal {S}})}$ ve bir tam sayı ${ displaystyle k}$; soru, belirli bir boyut paketinin olup olmadığıdır. ${ displaystyle k}$ yada daha fazla. Set ambalajında optimizasyon sorunu giriş bir çift ${ displaystyle ({ mathcal {U}}, { mathcal {S}})}$ve görev, en çok seti kullanan bir set paketi bulmaktır.

Sorun açıkça NP o zamandan beri k alt kümeler, ikilide ayrık olduklarını kolayca doğrulayabiliriz polinom zamanı.

optimizasyon versiyonu problemin, maksimum set paketleme, listedeki maksimum ikili ayrık küme sayısını sorar. Doğal olarak formüle edilebilen bir maksimizasyon problemidir. tamsayı doğrusal program, sınıfına ait paketleme sorunları.

Tamsayı doğrusal program formülasyonu

Maksimum set paketleme problemi aşağıdaki gibi formüle edilebilir tamsayı doğrusal program.

maksimize etmek	${ mathcal {S}}} x_ {S}} içinde { displaystyle sum _ {S$		(toplam alt küme sayısını en üst düzeye çıkarın)
tabi	${ displaystyle toplam _ {S kolon e , S} x_ {S} leqslant 1}$	hepsi için ${ mathcal {U}}} içinde { displaystyle e$	(seçilen setler ikili olarak ayrık olmalıdır)
	${ displaystyle x_ {S} in {0,1 }}$	hepsi için ${ mathcal {S}}} içinde { displaystyle S$.	(her set set paketinde ya da değil)

Karmaşıklık

Set paketleme problemi sadece NP-tam değildir, aynı zamanda optimizasyon versiyonunun (genel maksimum set paketleme problemi) tahmin edilmesi kadar zor olduğu kanıtlanmıştır. maksimum klik sorunu; özellikle, herhangi bir sabit faktör içinde yaklaştırılamaz.^[1] En iyi bilinen algoritma, onu bir çarpan içinde yaklaştırır ${ displaystyle O ({ sqrt {| U |}})}$.^[2]Ağırlıklı varyant da tahmin edilebilir.^[3]

Bununla birlikte, sorunun daha anlaşılabilir bir çeşidi vardır: eğer hiçbir alt kümenin aşmadığını varsayarsak k≥3 element, cevap bir çarpan içinde tahmin edilebilir k/ 2 + ε herhangi bir ε> 0; özellikle, 3 elemanlı setlerle ilgili problem yaklaşık% 50 içinde yaklaşık olarak tahmin edilebilir. Başka bir daha izlenebilir varyantta, eğer hiçbir öğe k Alt kümelerin bir faktörü içinde yanıt yaklaşık olarak tahmin edilebilir k. Bu aynı zamanda ağırlıklı versiyon için de geçerlidir.

Eşdeğer sorunlar

Arasında bire bir polinom zaman azaltımı vardır. bağımsız küme problem ve set paketleme problemi:

• Bir koleksiyonda set paketleme problemi verildiğinde ${ displaystyle { mathcal {S}}}$her set için bir grafik oluşturun ${ mathcal {S}}} içinde { displaystyle S$ bir tepe var ${ displaystyle v_ {S}}$ve arasında bir kenar var ${ displaystyle v_ {S}}$ ve ${ displaystyle v_ {T}}$ Eğer ${ displaystyle S cap T neq varnothing}$. Artık, oluşturulan grafikteki her bağımsız köşe kümesi, ${ displaystyle { mathcal {S}}}$.
• Bir grafikte bağımsız bir köşe seti problemi verildiğinde ${ displaystyle G (V, E)}$, her köşe için bir set koleksiyonu oluşturun ${ displaystyle v}$ bir set var ${ displaystyle S_ {v}}$ bitişik tüm kenarları içeren ${ displaystyle v}$. Artık, oluşturulan koleksiyondaki her set paketleme, içindeki bağımsız bir köşe kümesine karşılık gelir. ${ displaystyle G (V, E)}$.

Bu aynı zamanda iki yönlü bir PTAS azaltma ve iki problemi birbirine yaklaştırmanın eşit derecede zor olduğunu gösteriyor.

Özel durumlar

Eşleştirme ve 3 boyutlu eşleştirme set paketlemenin özel durumlarıdır. Polinom zamanında bir maksimum boyut eşleşmesi bulunabilir, ancak en büyük 3 boyutlu eşleşmeyi veya en büyük bağımsız kümeyi bulmak NP-zordur.

Diğer ilgili sorunlar

Set paketleme, bir setin öğelerini örtmek veya bölmekle ilgili sorunlar ailesinden biridir. Yakından ilişkili bir sorun, kapak sorunu ayarla. Burada da bir set veriliyor S ve bir set listesi, ancak amaç seçip seçemeyeceğimizi belirlemektir. k tüm unsurlarını içeren kümeler S. Bu setler çakışabilir. Optimizasyon sürümü, bu tür kümelerin minimum sayısını bulur. Maksimum set paketinin olası her öğeyi kapsaması gerekmez.

NP-tamamlandı tam kapak problem ise her elemanın tam olarak alt kümelerden birinde yer almasını gerektirir. Boyuttan bağımsız olarak böylesine kesin bir örtü bulmak, NP tamamlandı sorun. Ancak, bir tekli set her unsuru için S ve bunları listeye eklediğinizde ortaya çıkan sorun, set paketleme kadar kolaydır.

Karp, başlangıçta set ambalajı NP-komple gösterdi. klik sorunu.

Ayrıca bakınız: Bir hipergrafta paketleme.

Notlar

Referanslar

• Maksimum Set Paketleme, Viggo Kann.
• "paketleme seti ". Algoritmalar ve Veri Yapıları Sözlüğü, editör Paul E. Black, Ulusal Standartlar ve Teknoloji Enstitüsü. Buradaki tanımın biraz farklı olduğunu unutmayın.
• Steven S. Skiena. "Paketleme Seti ". Algoritma Tasarım Kılavuzu.
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski ve Gerhard Woeginger. "Maksimum Set Paketleme ". NP optimizasyon problemlerinin bir özeti. En son 20 Mart 2000 tarihinde güncellenmiştir.
• Michael R. Garey ve 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. A3.1: SP3, sayfa 221.
• Vazirani, Vijay V. (2001). Yaklaşım Algoritmaları. Springer-Verlag. ISBN  978-3-540-65367-7.

Dış bağlantılar

• [1]: Problemi çözmek için bir Pascal programı. Nereden Pascal Programları ile Ayrık Optimizasyon Algoritmaları MacIej M. Syslo tarafından, ISBN  0-13-215509-5.
• Set Kaplama, Set Paketleme ve Kazanan Belirleme için Gizli Optimum Çözümlerle Karşılaştırmalar
• PHP'de paketleme sorununu çözme
• Üç Boyutlu Kutu Paketlemeyi Optimize Etme