Bizkar-zorroaren buruketa optimizazio-buruketa konbinatoriala da. Pisu eta balio ezaguneko gauzakien multzo batean guztizko gehieneko balioko azpimultzoa aurkitzean datza, azpimultzoko gauzakien guztizko pisua muga batetik behera egotera murriztuta dagoen kasuan. Neurri mugatuko bizkar-zorro batean gauzakiak sartu behar diren kasuari aipamen eginez ematen zaio buruketari halako izena; bizkar-zorroan sartutako gauzakien balioen baturak gehienekoa izan behar du. 

Aplikazio asko ditu, hala nola biosendagintzan, gaixoari eman beharreko sendagaiak aukeratzeko orduan, antibiotiko-zama mugatua denean. Igogailuak marraztean ere maiz ezartzen da, pisu jakin baterako zenbat pertsona eta nolakoak sar daitezkeen erabakitzeko.

Motxilaren arazoa Richard Karp informatikako teorikoak identifikatutako 21 NP-osoak arazoetako bat da, zeinak 1972an argitaratutako artikulu eragingarri batean sartu zituen ^[1]. Arazo hori sakon aztertu da XX. mendearen erdialdetik, eta lehen erreferentziak 1897an egin ziren, George Mathews Ballarden artikulu batean ^[2].

Planteamendua erraza bada ere, arazoa konpontzea oso konplexua da. Hainbat algoritmo daude praktikan tamaina handiko instantzientzat lantzeko gai direnak, baina bere egitura bereziak eta arazo zabalagoen osagai gisa maiz agertzen denez, ikerketa operatiboaren esparruan behin eta berriz aztertzen den gaia da.

Bizkar-zorroaren buruketa mundu errealeko hainbat alorretan erabakiak hartzean sortzen dira, hala nola lehengaiak alferrikako hondakinik gabe mozteko metodo eraginkorrak bilatzean, inbertsioak hautatzean eta zorroak osatzean, aktiboek babestutako titulizaziorako aktiboak aukeratzean eta kriptosistemetan (Merkle-Hellman, adibidez) gakoak sortzean, besteak beste.

Motxila-algoritmoen lehen aplikazioetako bat azterketen eraikuntzan eta kalifikazioan izan zen, ikasleek erantzun nahi dituzten galderak aukera ditzaten. Kasu errazetarako, hau maneiagarria da: adibidez, 10 puntuko 12 galdera dituen azterketa batean, ikasleak 10 galdera erantzun ditzake, gehienez 100 puntu lortzeko. Hala ere, galderek puntuazio-balio desberdinak dituztenean, aukera hori eskaintzea konplexuagoa da. Feuermanek eta Weissek metodo bat proposatu zuten, non ikasleei 125 puntu posibleko azterketa heterogeneo bat ematen zaien, eta ikasleek galdera guztiei erantzun behar diete, beren aukeren arabera. Puntuen batura 100era iristen den galderen azpimultzoetatik, motxila-algoritmo batek ikasle bakoitzarentzat puntuazioa maximizatzen duen azpimultzoa identifika lezake.

Stony Brook-eko Unibertsitateko Algoritmoen Biltegiak 1999an egindako ikerketa batek erakutsi zuen ezen, algoritmo konbinatorioen eta algoritmoen ingeniaritzaren arloarekin zerikusia zuten 75 arazo algoritmikoetatik, motxilaren arazoa 19. arazo ezagunena zela.

Jarraian, modu formalean azaltzen da arazoa ^[3]. Demagun n objektu mota desberdinak daudela, 1etik n-ra zenbakituak. Objektu mota bakoitzetik qi unitate daude eskuragarri, non qi zenbaki oso positibo bat den, 1 <= qi < inf betetzen duena.

Objektu mota bakoitzak vi balioa eta wi pisua ditu lotuta eta positiboak direla onartzen da. Notazioa sinplifikatzeko, objektuak pisu txikienetik handienera ordenatzen dira. Objektuez gain, objektu horiek gordeko dituen motxila ere badago, W pisuko gehienezko edukierarekin.

Helburua da hautatutako objektuen guztizko balioa maximizatzen duten objektuak hautatzea eta motxilan jartzea, guztizko pisuak motxilaren gehienezko W edukiera gainditu gabe. Problemaren konponbidea x1, x2,..., xn aldagaien bidez adierazten da, non xi bakoitzak i objektuaren zenbat unitate sartuko diren motxilan adierazten duen. Hau da, soluzioa zenbaki oso positiboen bektore baten bidez irudikatuko da. Bektorearen zenbaki bakoitzak objektu horren motxilan sartuko diren kopia kopurua adierazten du.

Matematikoki, problema honako programa lineal honen bidez adieraz daiteke daiteke:

maximizatu ${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

non ${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$ eta ${\displaystyle 0\leq x_{i}\leq q_{i}}$

Bestalde, objektuak bakarrak badira, hau da, kopia bat baino gehiago ez badago, 0-1 motxilaren arazoa da. Matematikoki honela adierazten da:

maximizatu ${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

non ${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$ eta ${\displaystyle x_{i}\in \{0,1\}}$

Kopia infinituak izanez gero, motxila mugatugabearen arazoaren aurrean gaude, motxila osoaren arazoa ere esaten zaio. Matematikoki honela adierazten da:

maximizatu ${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

Motxilaren arazoa NP-osoa da, eta horrek esan nahi du ez dagoela kasu guztiak ebazteko ezagutzen den algoritmo eraginkor eta zehatzik. Era berean, ez da ezagutzen algoritmo polinomikorik soluzio bat optimoa den egiaztatzeko. Teorian konplexua bada ere, kasu praktiko asko ebatzi daitezke. Gainera, erabakitzeko arazoa modu eraginkorrean ebazten bada, denbora polinomikoan optimizatzeko arazoaren ebazpen optimoa aurki daiteke.

Ikerketa-ildo garrantzitsu bat arazoaren "instantzia zailak" ulertzea da, kasu txarrenean baino erabilgarriagoak izan daitezkeenak. Instantzia horiek garrantzitsuak dira kriptografian, Merkle–Hellman-en kriptosisteman bezala. Zailtasuna, halaber, sarrerako datuak irudikatzen diren moduaren araberakoa da; izan ere, pisuak eta irabaziak osoak badira, arazoa ahulki NP-osoa da; arrazionalak badira, sendo NP-osoa da.

NP arazoaren zailtasuna eredu konputazionalekin ere lotuta dago, non zenbaki osoen tamainak garrantzia duen, Turing makinan bezala. Arazoa konpontzeko kota baxuagoak eta altuagoak ezarri dira hainbat ereduetan, hala nola erabaki-zuhaitzetan eta ausazko sarbiderako makinetan. Horrek arazoaren mugak eta konplexutasunak erakusten ditu hainbat ikuspegitan.

Bizkar-zorroaren buruketa, "Knapsack problem" izenez ere ezagutzen denak, hainbat ebazpen-metodo ditu ikerketa operatiboaren esparruan, bakoitza aldaera espezifikoei eta arazoaren dimentsio desberdinei heltzeko diseinatua. Jarraian, horiek ebazteko erabilitako metodo nagusiak deskribatzen dira:

[aldatu | aldatu iturburu kodea] Metodo hau asko erabiltzen da motxila bitarraren arazorako (0-1 Knapsack Problem), non balio agregatua maximizatzea bilatzen den, aurrez zehaztutako pisu-muga gainditu gabe. Programazio dinamikoak azpiproblema txikietan deskonposatzen du arazoa, eta bakoitzaren emaitzak konpontzen eta biltegiratzen ditu, kalkulu erredundanteak saihesteko. Tamaina ertaineko arazoetarako efizientzia egokia bada ere, memoria-eskaera handia izan daiteke.

[aldatu | aldatu iturburu kodea] Ikuspegi hori bereziki eraginkorra da bizkar-zorroaren arazoaren zatikizko aldaerarako, objektuen zatikiak hautatzeko aukera ematen baitu. Algoritmoak elementuak ordenatzen ditu balio/pisu erlazioaren arabera, eta ordena horretan hautatzen ditu, bizkar-zorroaren edukierara iritsi arte. Hala ere, 0-1 arazo bitarraren kasuan, algoritmo irenskorrek ez dute konponbide optimoa bermatzen.

[aldatu | aldatu iturburu kodea] Metodo honek programazio linealeko eredu gisa formulatzen du arazoa, eta aldagaiek osoak izan behar dute. Teknika hau erabilgarria da murrizketa gehigarriak daudenean, eta maiz ezartzen da adarkatze- eta inausketa-algoritmoekin batera (branch and bound) soluzio optimoak lortzeko. Hala ere, baliteke denbora asko behar izatea tamaina handiko instantzietan.

[aldatu | aldatu iturburu kodea] Ikuspegi horrek sistematikoki aztertzen ditu soluzio bat osa dezaketen elementuen konbinazio posible guztiak, eta orain arte aurkitutako soluzio optimoa hobetzen ez duten erabaki-zuhaitzaren adarrak ezabatzen ditu. Eskala handiagoko arazoetarako egokia bada ere, gauzatze-denbora esponentzialki haz daiteke instantziaren tamainarekin.

[aldatu | aldatu iturburu kodea] Neurri handiko arazoetan edo murrizketa konplexu gehigarrietan, algoritmo metaheuristikoek, hala nola algoritmo genetikoek, suberaketa simulatuak eta partikula-multzo bidezko optimizazioak, gutxi gorabeherako soluzioak ematen dituzte. Konponbide optimoa lortzen ez badute ere, eraginkorrak dira kalitate handiko konponbideak arrazoizko epeetan aurkitzeko.