Uzdevums par mugursomu

Uzdevums par mugursomu ir viena no kombinatoriskās optimizācijas problēmām. Savu nosaukumu ieguvis no uzdevuma nosacījumiem: ielikt mugursomā, kuras ietilpība ir ierobežota, pēc iespējas vairāk vērtīgu mantu. Ir sastopamas vairākas uzdevuma par mugursomu nosacījuma variācijas ekonomikā, lietišķā matemātikā, kriptogrāfijā un loģistikā.

Vispārīgi uzdevuma nosacījumus var noformulēt tā: no dotas priekšmetu kopas ar īpašībām “vērtība” un “svars” ir jāizveido apakškopu ar maksimālu vērtību, ievērojot summārā svara ierobežojumu.

 Klasiska uzdevuma nostādne 

Pieņemsim, ka mums ir priekšmetu kopa, kurai ir divi parametri – svars un vērtība. Mums arī ir mugursoma ar noteiktu ietilpību. Uzdevums ir piepildīt mugursomu ar maksimālo priekšmetu vērtību tā,  lai ievērotu tās summāra svara ierobežojumu.

Matemātiski uzdevums tiek formulēts sekojoši: dots  svari. Katram -tam svaram ir noteikts svars  un vērtība , . Mugursomas summārā svara robežas noteic ar celtspēju . Ir nepieciešams maksimizēt  ar ierobežojumu  un .

 Uzdevuma par mugursomu variācijas 
Šai problēmai eksistē daudz vispārinājumu, tie atkarīgi no nosacījumiem, kuri attiecas uz pašu mugursomu, citiem priekšmetiem vai citu priekšmetu izvēli. Populārākie mugursomas problēmas veidi ir:
 Mugursoma 0-1 (): ne vairāk kā viens eksemplārs katram priekšmetam.
 Ierobežota mugursoma (): ne vairāk par noteikto eksemplāru skaitu katram priekšmetam.
 Neierobežota mugursoma (): patvaļīgs eksemplāru skaits katram priekšmetam.
 Mugursoma ar vairākiem izvēles veidiem (): priekšmeti ir sadalīti grupās un no katras grupas ir iespējams izvēlēties tikai vienu.
 Vairākas mugursomas (): ir vairākas mugursomas, katra ar savu maksimālo svaru. Katru priekšmetu var vai nu atstāt, vai ievietot jebkurā mugursomā.
 Daudzdimensiju mugursoma (): doti dažādi resursi, piemēram, svars, tilpums un kraušanas laiks. Katrs priekšmets patērē iepriekš noteikto resursa summu. Jāizvēlas priekšmetu apakškopu tā, lai katra resursa kopējās izmaksas nepārsniegtu šī resursa maksimumu, pie tam lai priekšmetu kopējā vērtība būtu maksimāla.
 Kvadrātiskā mugursomas problēma (): kopējā vērtība ir noteikta ar nenegatīvu kvadrātisko formu.

 Pielikumi 
Nav zināms, kurš tieši formulēja matemātisko formulu mugursomas problēmai. Viens no pirmajiem, kurš to pieminēja, bija Džordžs Ballards Metjūss savā rakstā 1897. gadā. Šīs problēmas intensīva pētīšana sākās pēc D.B. Danciga 1957. gadā izdotās grāmatas (). 20. gadsimta 70 – 90 gados to sāka pētīt gan teorētiķi, gan praktiķi. Lielu interesi pret uzdevumu izraisa tas, ka nosacījumi bija viegli formulēti, uzdevumam bija varākas variācijas un tā risinājums nebija elementārs. 1972. gadā uzdevums par mugursomu tika iekļauts K.Menninga NP-pilno uzdevumu skaitā.

Uzskatāma uzdevuma interpretācija veicināja, ka to iesāka izmantot dažādās zināšanu jomās: matemātikā, informātikā un šo zinātņu savienojumā – kriptogrāfijā. Vienā no matemātiskās lingvistikas darbiem bija piedāvāts automātiskās tekstu referēšanas uzdevums, kura īpašs gadījums atbilst mugursomas uzdevuma formulējumam.

Balstoties uz uzdevumu par mugursomu tika izveidots pirmais asimetriskās šifrēšanas algoritms.

 Mugursomas problēma kriptogrāfijā 
1978. gadā Ralfs Merkls un Martins Hellmans izstrādāja pirmo algoritmu vispārējai šifrēšanai izmantojot publisko atslēgu - Merkļa-Hellmaņa kriptosistēmu. Viņi to izveidoja, balstoties uz mugursomas problēmu. Viņi publicēja vienpakāpju (angl. singly-iterated) un daudzpakāpju versijas un algoritmu varēja izmantot tikai šifrēšanai. Tomēr Adi Šamirs pielāgoja to arī digitālo parakstu izmantošanai.

Vēlāk tika izveidotas daudzas Merkļa-Hellmaņa kriptosistēmas modifikācijas, kā arī pavisam jaunas kriptosistēmas, kas balstījās uz mugursomas problēmu. Starp tām ir:
 Greihama-Šamira mugursoma;
 Gudmana - Makkolija mugursoma;
 Nakaša-Šterna mugursoma
 Šora-Rivesta mugursoma.

 Šifrēšana, izmantojot mugursomas problēmu 
Risinājuma sarežģitība ļauj šifrēt pārraidāmos ziņojumus kā risinājumu mugursomas problēmai.

Definīcija. Mugursomas vektoru    sauksim par sakārtotu priekšmeta kopu n, kur  - priekšmeta  svars.

Lai nošifrētu tekstu, to sadala blokos  bitu garumā (piemērām, atklāts teksts  atbilst četru priekšmetu klātbūtnei no sešiem iespējamiem). Tiek uzskatīts, ka 1 norāda uz priekšmeta esamību mugursomā un 0 uz pretējo.

Pēc tam tiek uzskatīts kopējais priekšmetu svars mugursomā un tas tiek padots kā šifrēts teksts.

Piemērs šifrēšanai ar šo algoritmu:

Pieņemsim, ka ir uzdots mugursomas vektors  ar garumu .
 Atklāts teksts  1 1 1 1 1 0  0 0 1 1 0 0  0 0 0 0 0 0  0 0 0 0 0 1 Priekšmeti mugursomā  3 4 6 7 10  6 7   11 Sašifrēts teksts 3 + 4 + 6 + 7 + 10 = 30  6 + 7 = 13  0  11
Konkrētajām  eksistē skaitļi, kuri nepārsniedz 41, t.i. kopējais priekšmetu svars mugursomas vektorā.

Praksē šifrēšanai ir nepieciešama paaugstinoša mugursoma, t.i. sakārtoti mugursomas vektora elementi ir paaugstinoši. Tādā gadījumā katram atklātam tekstam eksistē tikai viens šifrēts teksts. Dotajā piemērā mugursoma nav paaugstinoša - ir iespējams saņemt to pašu šifrēto tekstu 100010 un 001100 vektoriem.

Kategorija:Kriptogrāfija