Uzdevums par mugursomu

Uzdevuma par mugursomu piemērs: ir nepieciešams ielikt kastes mugursomā, ar ietilpību 15 kg, tā, lai ieliktu kastu vērtība būtu maksimāla.

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āra 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 $n$ svari. Katram $i$-tam svaram ir noteikts svars $w_i>0$ un vērtība $v_i>0$, $i=1,2,...,n$. Mugursomas summārā svara robežas noteic ar celtspēju $W$. Ir nepieciešams maksimizēt $\sum _{i=1}^n{v}_i{x}_i$ ar ierobežojumu $\sum _{i=1}^n{w}_i{x}_i\le W$ un $x_i\in \{0,1\}$.

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:

1. Mugursoma 0-1 (Veidne:Lang-en): ne vairāk kā viens eksemplārs katram priekšmetam.
2. Ierobežota mugursoma (Veidne:Lang-en): ne vairāk par noteikto eksemplāru skaitu katram priekšmetam.
3. Neierobežota mugursoma (Veidne:Lang-en): patvaļīgs eksemplāru skaits katram priekšmetam.
4. Mugursoma ar vairākiem izvēles veidiem (Veidne:Lang-en): priekšmeti ir sadalīti grupās un no katras grupas ir iespējams izvēlēties tikai vienu.
5. Vairākas mugursomas (Veidne:Lang-en): ir vairākas mugursomas, katra ar savu maksimālo svaru. Katru priekšmetu var vai nu atstāt, vai ievietot jebkurā mugursomā.
6. Daudzdimensiju mugursoma (Veidne:Lang-en): 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.
7. Kvadrātiskā mugursomas problēma (Veidne:Lang-en): 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 (Veidne:Lang-en). 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:

1. Greihama-Šamira mugursoma;
2. Gudmana - Makkolija mugursoma;
3. Nakaša-Šterna mugursoma
4. Š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 $A=(a_1,...,a_n)$ sauksim par sakārtotu priekšmeta kopu n, kur $a_i$ - priekšmeta $i$ svars.

Lai nošifrētu tekstu, to sadala blokos $n$ bitu garumā (piemērām, atklāts teksts $(111100)$ 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 $A=(34671011)$ ar garumu $n=6$.

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 $A$ 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.