Complexitatea temporală a algoritmului de căutare exhaustivă

Am seturile $S_1=\{2,10,20,6\}$ și $S_2=\{25,26,20\}$ și vreau să aflu ce numere însumează 32. Acest lucru este foarte ușor prin inspecție; 6 și 26. Pare similară cu problema rucsacului, dar nu sunt expert.

Cu toate acestea, să spunem că am 1000 de seturi, fiecare cu 500 de elemente, astfel încât însumarea unui termen din fiecare set vă oferă întotdeauna o valoare unică. Acest lucru este mult mai greu de inspectat și rezolvat, mai ales dacă seturile urmează o structură care va apărea aleatorie (ar fi construite din seturi structurate cu care au fost încurcate și ar fi aproape imposibil să ghicim amestecul și să inversezi seturile).

Deci, singura modalitate trebuie să fie un algoritm de căutare exhaustiv. Dat fiind că numărul meu este 52.485.332, există $1000^{500}$ opțiuni posibile de analizat. Într-adevăr, vor exista modalități de a scurta această căutare (cum ar fi atunci când un set are numere mai mari decât valoarea țintă, puteți ignora acele numere). Dar altfel s-ar putea să te uiți în continuare la $750^{500}$ posibile alegeri.

Deci, care este complexitatea de timp a unui astfel de algoritm de căutare? $O(n^{k})$, cu $n$ numărul de seturi și $k$ numărul de elemente din acele seturi? Ei trebuie să verifice „toate” combinațiile posibile de termeni până când unul se potrivește cu valoarea dată.

Principalele întrebări par să fie „câte seturi există?” și „cât de mari sunt seturile?”. Într-adevăr, seturile pot fi toate de diferite dimensiuni, nu doar uniforme.

Nu sunt o persoană cu criptografie; cercetarea mea doar cochetează cu ideea la îndemână. Orice ajutor ar fi apreciat.

Deci, singura modalitate trebuie să fie un algoritm de căutare exhaustiv

După cum am menționat în comentariul meu, există metode practice pentru valori non-uriașe ale $m$ (și $m=52485332$ nu este imens). Iată schița unei astfel de metode (care presupune că toate mulțimile constau din numere întregi nenegative):

• Avem o matrice $A_{n, m+1}$; fiecare element al matricei $A_{a, b}$ va observa cum putem genera suma $b$ din prima $a$ seturi (sau $\perp$ dacă nu s-a găsit încă o astfel de cale).

• Inițializați toate elementele $A$ la $\perp$

• Pentru $i := 1$ la $n$ cauta elementele $A_{i-1}$ pentru non-$\perp$ element (și pentru $i=1$, al 0-lea element este tratat ca singurul non-$\perp$ element. Pentru fiecare astfel de element $A_{i-1, x}$, a stabilit $A_{i, x + S_{i,j}}$ la $j$ (pentru fiecare element $S_{i,j}$ a setului $S_i$) Dacă $x + S_{i,j} > m$, ignora.

• În fine, dacă $A_{n,m} = \perp$, nu există nicio submulțime care să conducă la sumă $m$. Dacă este altceva, putem recupera termenii revenind înapoi prin matrice $A$.

Acesta ar trebui să fie un algoritm practic pentru recuperarea termenilor având în vedere parametrii pe care i-ați specificat.

Acesta este mai mult un răspuns la motivul pentru care unicitatea sumelor afectează atât de mult dimensiunea încât este cazul $52485332$ devine banal (modul său de a tânji după un comentariu).

Când toate sumele trebuie să fie unice, atunci ele trebuie să rezulte în numere întregi diferite. Pentru ca sunt acolo $500^{1000}$ sume posibile, există și $500^{1000}$ rezultate întregi diferite pentru asta. cel mai mic caz ar fi toate numerele întregi din $0$ la $500^{1000}-1$.

De exemplu,

$S_1 = \{0, 1, 2, ..., 499\}$

$S_2 = \{0, 500, 1000, ..., 249500\}$

$S_3 = \{0, 250000, 500000, ..., 124750000\}$

...

$S_{1000} = \{0, 500^{999}, 2*500^{999}, ..., 499*500^{999}\}$

ar fi o modalitate de a asigura unicitatea rezultatului. După cum puteți vedea, numerele devin foarte mari, foarte repede.

În acest exemplu particular, este ușor să găsiți rezultatul (doar alegeți întotdeauna cel mai mare număr care se potrivește de la ultimul până la primul set). Chiar și majoritatea numerelor este $S_3$ sunt mai mari decât $52485332$ și, prin urmare, poate fi ignorat.

Probabil că ați dori valori relativ aleatorii în seturile dvs. În acest caz, intervalul de valori trebuie să fie cel puțin puțin mai mare.

Cu toate acestea, este foarte puțin probabil ca vreo valoare să fie mai mică sau egală cu $52485332$ (când alegi uniform $500000$ valori din $500^{1000}$)

Programarea dinamică, așa cum a sugerat @poncho, într-adevăr funcționează doar pentru numere mici și performanța sa nu este cu mult mai bună decât căutarea exhaustivă (diferența liniară a numărului de seturi), deoarece sub-suma, care pot fi refolosite sunt unice, avantajul a nu se uita la alte posibilități nu există. Timpul de rulare ar trebui să fie în aceeași ordine ca și căutarea exhaustivă. Doar îmbunătățirea este să vă integrați atunci când valorile sunt prea mari sau mici pentru a atinge ținta, dar pentru ținte rezonabile, acest lucru nu reprezintă un mare avantaj.

Activat ar putea reduce cu ușurință problema sumei subsetului sau problema rucsacului la aceasta, folosind doar același set de câte ori numărul cu care doriți să însumați.Problema cu aceasta este că aceasta nu este o reducere de timp polinomială și, prin urmare, nu este suficientă pentru a demonstra dacă problema este NP grea.