miniatura|El problema de la motxilla: quines capses cal triar per tal de maximitzar la quantitat que es porta sense passar-se dels 15 kg autoritzats ? El problema de la motxilla, altrament dit KP (en anglès, Knapsack Problem) és un problema d'optimització combinatòria. Modelitza una situació anàloga al fet d'omplir una motxilla, en la que no es pot posar més d'un cert pes, amb tot o una part d'un conjunt d'objectes. Aquests objectes tenen un pes i un valor determinat. Els objectes que es posen dins la motxilla han de maximitzar el valor total sense sobrepassar el pes màxim.
Història Recerca El problema de la motxilla és un dels 21 problemes NP-complets de Richard Karp, exposats en el seu article de 1972. Ha estat estudiat des de meitats del segle XX i se'n troben referències des de 1897, en un article de George Ballard Mathews. G.B. Mathews, On the partition of numbers, Proceedings of the London Mathematical Society, 28:486-490, 1897. La formulació del problema és força senzilla, però la seva solució és més complexa. Els algorismes existents poden resoldre casos concrets però l'estructura singular del problema i el fet que és un sub-problema d'altres problemes més generals, fan que actualment encara sigui estudiat per diferents grups de recerca científica.
Complexitat i criptografia Aquest problema és l'origen del primer algorisme de criptografia asimètrica (o de clau pública) presentat per Martin Hellman, Ralph Merkle i Whitfield Diffie a la Universitat Stanford el 1976. Public Key Cryptography , a la part d'Història d'un projecte de Eric Robert's Sophomore College class "The Intellectual Excitement of Computer Science" a la Universitat Stanford. La publicació corresponent és: R.C. Merkle et M.E. Hellman, "Hiding Information and Receipts in Trap Door Knapsacks", Internal Symposium on Information Theory, Cornell University, Ithaca, New York, October 1977. De totes maneres, encara que la idea és deguda al problema de la motxilla, RSA és considerat com el veritable algorisme de xifratge asimètric.
La versió NP-difícil d'aquest problema ha estat utilitzat en algunes primitives i alguns protocols de criptografia, com el criptosistema de Merkle-Hellman o el criptosistema de Chor-Rivest. El seu avantatge amb respecte als criptosistemes asimètrics basats en la dificultat de la descomposició en producte de factors primers és la seva velocitat de xifratge i dexifratge. Però, l'algorisme de Hellman, Merkle i Diffie està subjecte a "portes posteriors " algorítmiques, la qual cosa implica que s'ha « trencat», és a dir criptoanalitzat. A. Shamir, A Polynomial-Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem, IEEE Transactions on Information Theory, Vol. IT-30, p. 699-704, 1984. (Première publication en avril 1982.) El problema de la motxilla és un exemple clàssic que menysprea tot allò que té a veure amb els lligams entre els problemes NP-complets i la criptografia. Una versió revisada de l'algorisme, amb una iteració del problema de la motxilla, va ser presentada però es va trencar ben aviat. Knapsack Encryption Scheme Broken , « Math Matrix », Département de mathématiques de l'Ohio State University, printemps 1985, Vol. 1, No. 3. Fins a l'actualitat, tots els algorismes de xifratge asimètrics basats en el problema de la motxilla han estat desxifrats, l'últim el de Chor-Rivest. S. Vaudenay, Cryptanalysis of the Chor-Rivest Cryptosystem .
Altres àmbits relacionats També s'utilitza per a modelitzar les següents situacions, algunes vegades utilitzant-lo com a sub-problema: en sistemes de suport a la gestió del portafolis: per equilibrar la selecció i la diversificació amb l'objectiu de trobar el millor equilibri entre el rendiment i el risc d'un capital col·locat en diferents actius financers (accions...); en la càrrega d'un vaixell o d'un avió: tot l'equipatge que es pot portar sense sobrepès
en el tall dels materials: per minimitzar les pèrdues degudes als talls (de diferents mides) realitzats en barres de ferro.
Una altra raó per la qual és interessant aquest problema és que apareix en alguns mètodes de generació de columnes (així com pel problema de bin packing).
Anecdòticament aquest problema es pot aplicar a la decisió que ha de prendre un excursionista quan ha de planificar la seva excursió: la motxilla té una capacitat limitada, per tant, cal decidir què emportar-se (per exemple, dues llaunes de conserva i una carmanyola de cinquanta centilitres o només una sola capsa de conserva i una carmanyola d'un litre.
Enunciat matemàtic Les dades del problema es poden expressar en termes matemàtics. Els objectes es numeren mitjançant un índex i que varia d1 a n. Els nombres i representen respectivament el pes i el valor de l'objecte numerat i. Anomenarem W a la capacitat de la motxilla.
Hi ha moltes maneres d'omplir la motxilla. Per descriure qualsevol d'elles només cal indicar si l'hem agafat o no. Es pot utilitzar un codi binari per codificar aquesta situació: l'estat de l'element i-èsim valdrà si s'ha ficat l'element a la motxilla, o si no s'ha ficat. Per tant, una manera qualsevol d'omplir la motxilla queda completament descrita per un vector, anomenat vector del contingut, o simplement contingut: . Per tant, el pes associat, així com el valor associat a aquesta manera d'omplir la motxilla es poden expressar com una funció del vector del contingut.
Donat un contingut X, el valor total contingut en la motxilla és, evidentment:
De la mateixa manera, la suma dels pesos dels objectes escollits és:
Per tant, el problema es pot reformular com la recerca d'un vector de contingut (les components del qual valen 0 o 1), tal que maximitzin la funció valor total , amb les restriccions: (1) És a dir que la suma dels pesos dels objectes escollits no passi la capacitat de la motxilla.
En general, s'afegeixen les restriccions següents per tal d'evitar casos singulars: : no es poden ficar tots els objectes; : tots els objectes aporten algun benefici; : tot objecte consumeix recursos (i.e. ocupa lloc).
Terminologia : s'anomena funció objectiu; tot vector que verifica la restricció (1) s'anomena realitzable; si el valor de és màxim, llavors es diu que és òptim.
NP-complet El problema de la motxilla es pot representar sota una forma de decisió canviant la maximització per la qüestió següent: donat un nombre , existeix un valor de les pel qual , tot respectant la restricció? Hi ha un lligam entre la versió « decisió » i la versió « optimització» del problema tenint en compte que hi ha un algorisme polinòmic que resol la versió de « decisió », de la mateixa manera que es pot trobar el valor màxim pel problema d'optimització de manera polinomial aplicant iterativament aquest algorisme mentre es va augmentant el valor de k. Per d'altra banda, si un algorisme troba el valor òptim del problema d'optimització en un temps polinomial, llavors el problema de decisió es pot resoldre en temps polinomial comparant el valor de la solució proporcionada per aquest algorisme amb el valor de k. Per tant, les dues versions del problema són de dificultat similar. Sota la forma de decisió, el problema és NP-complet, cosa que significa que no es coneix cap mètode general per construir una solució òptima, a part l'examen sistemàtic de totes les possibles solucions. El problema d'optimització és NP-complet, la seva resolució és com a mínim tan difícil que la del problema de decisió, i no existeix cap algorisme polinomial conegut que, donada una solució, pugui dir si és òptima (cosa que voldria dir que no existeix cap solució amb un més gran, per tant, resoldre el problema de decisió NP-complet).
Procediment d'exploració sistemàtica Arbre d'exploració binària Aquest examen sistemàtic es pot realitzar amb ajuda d'un arbre d'exploració binaria..... el representat aquí al costat (els triangles representen sub-arbres).
L'arbre es descriu baixant des del cim fins a la part baixa dels triangles (les fulles de l'arbre). Cada cas correspon a un únic recorregut possible. Seguint les indicacions donades al llarg de les arestes de l'arbre, a cada camí li correspon una tira de valors per formant un vector contingut. Per tant, és possible dir en cada cas el valor total i el pes total corresponent al contingut. Només queda eliminar els casos que no satisfan la restricció, i escollir entre aquelles que queden, aquella (o una d'aquelles) que fa assolir el màxim a la funció objectiu.
Cada vegada que un objecte s'afegeix a la llista dels objectes disponibles s'afegeix un nivell a l'arbre d'exploració binari, i el nombre de casos es multiplica per 2. L'exploració de l'arbre i la completació de casos tenen un cost que creix exponencialment amb el nombre d'objectes.
Prova de la NP-completesa Aquesta prova de la NP-completitud va ser presentat per Maichail G. Lagoudakis Michail G. Lagoudakis, The 0-1 Knapsack Problem - An Introductory Survey , 1996. recuperant un article de Richard Karp i un article de J.E. Savage.
Pertinença a NP Abans de res s'ha de provar que (KP) pertany a la classe NP, és a dir que existeix un algorisme polinomial que, donada una solució del problema, pot verificar que aquesta solució és la bona. Per verificar una solució simplement cal calcular la suma dels pesos dels objectes escollits i comparar-la amb W, de la mateixa manera que la suma dels seus valors s'han de comparar amb . El total és evidentment polinomial. (KP) pertany per tant a la classe dels problemes NP.
Pertinença a NP-difícil Es demostra també que (SSE) és un problema NP-difícil transformant el problema de la cobertura exacta (notat (EC), de l'anglès exact cover) en un problema (SSE). El problema (EC) s'expressa així:
Sigui U un conjunt d'elements i un conjunt de sub-conjunts dU. Existeix un sub-conjunt de S tal que : : tots els elements d'U hi siguin; : cada element dU està únicament en un sol dels subconjunts escollits.
El problema (EC) és NP-complet. Si s'arriba a demostrar que en tota instància d'''(EC) es pot transformar polinomialment en una instància de (SSE) llavors haurem pogut provar que (SSE) (i per tant (KP)) pertany a la classe de problemes NP-complets.
Sigui I = (U,S) una instància qualsevol de (EC). Sense perdre la generalitat, considerem que . Notarem: l'estat del conjunt ( si i només si ) ; la pertinença del valor j al conjunt ( si i només si ).
Sigui . Les variables del problema (SSE) són les del problema (EC). Definim el seu pes de la manera següent: .
Definim la capacitat W per .
El pes de l'objecte i és una suma de potències de b i està a si i només si . Per tant, hi ha una correspondència d'u a u entre la solució del problema(SSE) construït i la instància d(EC). Cada valor es calcula en i la valor de W es calcula en O(1). La transformació té per tant una complexitat temporal en . El problema (SSE) (i per tant el problema(KP)) pertany a la classe dels problemes NP-difícil.
Conclusió Hem provat que (KP) és NP i NP-difícil. Per tant, el problema (KP) pertany a la classe de problemes NP-complets.
Resolució aproximada Com a la majoria dels problemes NP-complets, pot ser interessant trobar possibles solucions encara que no siguin òptimes. Preferentment amb un control sobre la diferència entre el valor de la solució i el valor de la solució òptima.
S'adopta la següent terminologia:
s'anomena eficàcia d'un objecte la raó (quocient) del seu valor entre el seu pes. Com més gran és el valor de l'objecte comparat amb el que consumeix, més interessant és l'objecte;
Algorisme golafre L'algorisme més senzill és un algorisme golafre. La idea és afegir primer els objectes més eficaços, fins a omplir la motxilla:
triar els objectes per ordre decreixent d'eficàcia w_conso := 0
per i de 1 a n si w[i] + w_conso <= W llavors x[i] := 1 w_conso := w_conso + w[i] sino x[i] := 0 fi si fi per