Alt küme toplamı sorunu - Subset sum problem

alt küme toplamı sorunu bir karar problemi içinde bilgisayar Bilimi. Sorunun birkaç eşdeğer formülasyonu vardır. Bunlardan biri: verilen bir çoklu set tamsayılar, toplamı sıfır olan boş olmayan bir alt küme var mı? Örneğin, set verildiğinde ${displaystyle {-7, -3, -2,9000,5,8}}$, cevap Evet çünkü alt küme ${displaystyle {-3, -2,5}}$ sıfıra eşittir. Bir başka eşdeğer formülasyon şudur: pozitif tamsayılar ve hedef toplam T, sayıların herhangi bir alt kümesinin toplamı tam olarak T?^[1] Alt küme toplamı da bir optimizasyon sorunu: toplamı mümkün olduğunca yakın olan bir alt küme bulun T.

Alt küme toplamı diğer birkaç sorunla ilgilidir:

• bölüm sorunu özel bir alt küme durumudur; burada hedef toplam T tüm giriş sayılarının toplamının tam olarak yarısıdır (yani, ${displaystyle T = {frac {1} {2}} (a_ {1} + noktalar + a_ {n})}$ ).
• sırt çantası sorunu alt küme toplamının bir genellemesidir.^[2]

Alt küme toplamı problemi NP tamamlandı, ancak pratikte makul derecede hızlı çözebilen birkaç algoritma vardır.

Karmaşıklık

karmaşıklık Alt küme toplam sorununun% 50'si iki parametreye bağlıdır: n - giriş tam sayılarının sayısı ve L - problemi ifade etmek için gereken ikili basamak değerlerinin sayısı olarak ifade edilen problemin kesinliği.

• Eğer n (tam sayıların sayısı) küçük bir sabit sayıdır, sonra bir Ayrıntılı arama çünkü çözüm pratiktir.
• Eğer L (ikili basamak sayısı) küçük bir sabit sayıdır, o zaman dinamik program tam olarak çözebilecek algoritmalar.

Sorun her ikisi de n ve L büyüktür. En iyi bilinen algoritmaların karmaşıklığı üstel iki parametreden daha küçük olanı n ve L.

Üstel zaman algoritmaları

Alt küme toplamını zaman içinde üstel olarak çözmenin birkaç yolu vardır. n.^[3]

Dahil etme hariç tutma

En çok saf algoritma tüm alt kümeleri arasında geçiş yapmak olacaktır n sayılar ve her biri için, alt kümenin doğru sayıya ulaşıp ulaşmadığını kontrol edin. Çalışma süresi düzenli ${displaystyle O (2 ^ {n} cdot n)}$olduğundan beri ${displaystyle 2 ^ {n}}$ alt kümeler ve her alt kümeyi kontrol etmek için en fazla n elementler.

Algoritma şu şekilde uygulanabilir: derinlik öncelikli arama ikili ağaç için: ağaçtaki her seviye bir giriş numarasına karşılık gelir; sol dal, sayının kümeden çıkarılmasına karşılık gelir ve sağ dal, sayının dahil edilmesine karşılık gelir (dolayısıyla Dahil Etme-Dışlama adı). Gerekli hafıza ${displaystyle O (n)}$. Çalışma zamanı birkaç buluşsal yöntemle geliştirilebilir:^[3]

• Girdi numaralarını azalan sırada işleyin.
• Belirli bir düğümde bulunan tam sayılar şimdiye kadar bulunan en iyi alt kümenin toplamını aşarsa, düğüm budanır.
• Belirli bir düğüme dahil olan tam sayılar artı kalan tüm tam sayılar, şimdiye kadar bulunan en iyi alt kümenin toplamından daha azsa, düğüm budanır.

Horowitz ve Sanhi

Horowitz ve Sahni^[4] zamanında çalışan daha hızlı bir üstel zaman algoritması yayınladı ${displaystyle O (2 ^ {n / 2} cdot (n / 2))}$, ancak çok daha fazla alan gerektirir - ${displaystyle O (2 ^ {n / 2})}$. Algoritma keyfi olarak böler n öğeleri iki set halinde ${displaystyle n / 2}$ her biri. Bu iki kümenin her biri için, tümünün toplamlarının bir listesini saklar. ${displaystyle 2 ^ {n / 2}}$ öğelerinin olası alt kümeleri. Bu iki listenin her biri daha sonra sıralanır. Bu adım için standart bir karşılaştırmalı sıralama algoritması kullanmak zaman alır ${displaystyle O (2 ^ {n / 2} n)}$. Ancak, sıralı bir toplam listesi verildiğinde ${displaystyle k}$ öğeler, liste iki sıralı listeye genişletilebilir.${displaystyle k + 1}$) inci öğe ve bu iki sıralı liste zaman içinde birleştirilebilir ${displaystyle O (2 ^ {k})}$. Böylelikle her liste zaman içinde sıralı biçimde oluşturulabilir. ${displaystyle O (2 ^ {n / 2})}$. Sıralanan iki liste göz önüne alındığında, algoritma, birinci dizinin bir öğesinin ve ikinci dizinin bir öğesinin toplamı olup olmadığını kontrol edebilir T zamanında ${displaystyle O (2 ^ {n / 2})}$. Bunu yapmak için, algoritma azalan sırada (en büyük öğeden başlayarak) birinci diziden ve artan sırada (en küçük öğeden başlayarak) ikinci diziden geçer. İlk dizideki geçerli öğe ile ikinci dizideki geçerli öğenin toplamı, Talgoritma, ilk dizideki sonraki öğeye geçer. Daha az ise Talgoritma, ikinci dizideki sonraki öğeye geçer. Toplamı olan iki öğe T bulunursa durur.

Schroeppel ve Shamir

Schroeppel ve Shamir^[5] benzer çalışma süresi gerektiren Horowitz ve Sanhi'ye dayalı bir algoritma sundu - ${displaystyle O (2 ^ {n / 2} cdot (n / 4))}$, çok daha az alan - ${displaystyle O (2 ^ {n / 4})}$. Tüm alt kümelerini oluşturmak yerine n/ 2 öğe önceden, öğeleri 4 sete bölerler n/ 4 öğenin her biri ve alt kümelerini oluştur n/ 2 öğe dinamik olarak bir min yığın.

Alan gereksinimleri nedeniyle, HS algoritması yaklaşık 50 tam sayıya kadar pratiktir ve SS algoritması 100 tam sayıya kadar pratiktir.^[3]

Howgrave-Graham ve Joux

Howgrave-Graham ve Joux^[6] bir olasılık algoritması öncekilerden daha hızlı çalışan - zamanında ${displaystyle O (2 ^ {n / 3})}$. Yalnızca karar problemini çözer, belirli bir toplam için çözüm olmadığını ispatlayamaz ve en yakın alt küme toplamını döndürmez T.

Sözde polinom zaman dinamik programlama çözümü

Sorun şu şekilde çözülebilir sözde polinom zaman kullanma dinamik program. Sıranın şöyle olduğunu varsayalım

${displaystyle x_ {1}, ldots, x_ {N}}$

artan sırada sıralanır ve toplamı sıfır olan bir boş olmayan alt küme olup olmadığını belirlemek isteriz. Boole değerli işlevi tanımlayın ${displaystyle Q (i, s)}$ değer olmak (${displaystyle true}$ veya ${displaystyle false}$) nın-nin

"boş olmayan bir alt küme var ${displaystyle x_ {1}, ldots, x_ {i}}$ toplamı ${displaystyle s}$."

Böylece, "Bir tam sayı kümesi verildiğinde, toplamı sıfır olan boş olmayan bir alt küme var mı?" değeridir ${displaystyle Q (N, 0)}$.

İzin Vermek ${displaystyle A}$ negatif değerlerin toplamı ve ${displaystyle B}$ pozitif değerlerin toplamı. Açıkça, ${displaystyle Q (i, s) = yanlış}$, Eğer ${görüntü stili$ veya ${ekran stili> B}$. Dolayısıyla bu değerlerin saklanması veya hesaplanması gerekmez.

Değerleri tutmak için bir dizi oluşturun ${displaystyle Q (i, s)}$ için ${displaystyle 1leq ileq N}$ ve ${displaystyle Aleq sleq B}$.

Dizi artık basit bir özyineleme kullanılarak doldurulabilir. Başlangıçta ${displaystyle Aleq sleq B}$, Ayarlamak

${displaystyle Q (1, s): = (x_ {1} == s)}$

nerede ${displaystyle ==}$ true döndüren bir boole işlevidir ${displaystyle x_ {1}}$ eşittir ${displaystyle s}$aksi takdirde yanlış.

Bundan dolayı ${displaystyle i = 2, ldots, N}$, Ayarlamak

${displaystyle Q (i, s): = Q (i-1, s)}$ veya ${displaystyle (x_ {i} == s)}$ veya ${displaystyle Q (i-1, s-x_ {i}) ,Aleq sleq B için}$.

Her bir ödev için değerleri ${displaystyle Q}$ sağ taraf zaten biliniyor, çünkü bunlar, önceki değer için tabloda depolandılar. ${displaystyle i}$ veya çünkü ${displaystyle Q (i-1, s-x_ {i}) = yanlış}$ Eğer ${displaystyle s-x_ {i}$ veya ${displaystyle s-x_ {i}> B}$. Bu nedenle, toplam aritmetik işlem sayısı ${displaystyle O (N (B-A))}$. Örneğin, tüm değerler ${görüntü stili O (N ^ {k})}$ bazı ${displaystyle k}$, o zaman gerekli zaman ${displaystyle O (N ^ {k + 2})}$.

Bu algoritma, varsa, toplamı 0 olan alt kümeyi döndürmek için kolayca değiştirilebilir.

Dinamik programlama çözümünün çalışma süresi var ${displaystyle O (sN)}$ nerede ${displaystyle s}$ sette bulmak istediğimiz toplam ${displaystyle N}$ sayılar. Bu çözüm, karmaşıklık teorisinde polinom zaman olarak sayılmaz çünkü ${displaystyle B-A}$ polinom değildir boyut problemin, onu temsil etmek için kullanılan bit sayısıdır. Bu algoritma, değerlerinde polinomdur ${displaystyle A}$ ve ${displaystyle B}$bit sayılarında üstel olan.

Her biri için ${displaystyle x_ {i}}$ pozitiftir ve sabit bir sabitle sınırlıdır ${displaystyle C}$Pisinger, zaman karmaşıklığına sahip doğrusal bir zaman algoritması buldu ${displaystyle O (NC)}$ (Bunun, hedef toplamın mutlaka sıfır olmadığı problem versiyonu için olduğuna dikkat edin, aksi takdirde problem önemsiz olacaktır).^[7][8] 2015 yılında Koiliaris ve Xu belirleyici bir ${displaystyle {ilde {O}} (s {sqrt {N}})}$ alt küme toplamı problemi için algoritma nerede ${displaystyle s}$ bulmamız gereken miktar.^[9] Bringmann 2017'de bir randomize ${displaystyle {ilde {O}} (s)}$ zaman algoritması ^[10].

Polinom zaman yaklaşık algoritması

Bir yaklaşık alt küme toplamının versiyonu şöyle olacaktır: bir dizi verilir ${displaystyle N}$ sayılar ${displaystyle x_ {i}, ldots, x_ {N}}$ ve bir sayı ${displaystyle s}$, çıktı:

• Evet, özetleyen bir alt küme varsa ${displaystyle s}$.
• Hayır, aralarında bir sayıyı toplayan bir alt küme yoksa ${displaystyle (1-c) s}$ ve ${displaystyle s}$ bazıları için ${displaystyle c> 0}$.
• Aralarında bir sayıyı toplayan bir alt küme varsa herhangi bir cevap ${displaystyle (1-c) s}$ ve ${displaystyle s}$ ancak özetleyen alt küme yok ${displaystyle s}$.

Tüm sayılar negatif değilse, yaklaşık alt küme toplamı, zaman polinomunda çözülebilir. ${displaystyle N}$ ve ${displaystyle 1 / c}$.

Alt küme toplamının çözümü, sayıların küçük olduğu durumda (yine, negatif olmayan sayılar için) orijinal alt küme toplamı sorununa da çözüm sağlar. Sayıların herhangi bir toplamı en fazla ile belirtilebiliyorsa ${displaystyle P}$ bitler, ardından sorunu yaklaşık olarak çözme ${displaystyle c = 2 ^ {- P}}$ tam olarak çözmeye eşdeğerdir. Ardından, yaklaşık alt küme toplamı için polinom zaman algoritması, çalışma süresi polinomu ile kesin bir algoritma haline gelir. ${displaystyle N}$ ve ${displaystyle 2 ^ {P}}$ (yani üstel olarak ${displaystyle P}$).

Yaklaşık alt küme toplam problemi için algoritma aşağıdaki gibidir:

bir liste başlatmak S bir öğe içermesi 0.her biri için ben 1'den N yapmak    İzin Vermek T oluşan bir liste olmak xben + y, hepsi için y içinde S    İzin Vermek U birliği olmak T ve S    çeşit U    Yapmak S boş izin y en küçük unsur olmak U     Ekle y -e S    her biri için element z nın-nin U artan sırada yapmak        // Birbirine yakın sayıları ortadan kaldırarak listeyi kırpın // ve şundan büyük öğeleri atın s.        Eğer y + cs/N < z ≤ s sonra            y = z            Ekle z -e SEğer S arasında bir sayı içerir (1 - c)s ve s sonra    dönüş EvetBaşka    dönüş Hayır

Algoritma polinom zamandır çünkü listeler ${displaystyle S}$, ${displaystyle T}$ ve ${displaystyle U}$ daima boyutta polinom kalın ${displaystyle N}$ ve ${displaystyle 1 / c}$ ve polinom boyutunda oldukları sürece, üzerlerindeki tüm işlemler polinom zamanında yapılabilir. Listelerin boyutu, yalnızca bir sayı eklediğimiz kırpma adımıyla polinom olarak tutulur. ${displaystyle z}$ içine ${displaystyle S}$ öncekinden daha büyükse ${displaystyle cs / N}$ ve daha büyük değil ${displaystyle s}$.

Bu adım, her bir öğenin ${displaystyle S}$ en az bir sonrakinden daha küçük ${displaystyle cs / N}$ ve şundan büyük öğeler içermez ${displaystyle s}$. Bu özelliğe sahip herhangi bir liste, en fazla ${displaystyle N / c}$ elementler.

Algoritma doğrudur çünkü her adım, en fazla ${displaystyle cs / N}$ ve ${displaystyle N}$ birlikte adımlar, en fazla ${displaystyle cs}$.

Ayrıca bakınız

• 3 TOPLA
• Merkle – Hellman sırt çantası şifreleme sistemi

Referanslar

daha fazla okuma

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "35.5: Alt küme toplamı sorunu". Algoritmalara Giriş (2. baskı). MIT Press ve McGraw-Hill. ISBN  0-262-03293-7.
• 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  0-7167-1045-5. A3.2: SP13, sayfa 223.