Uzdevums par mugursomu

Uzdevums par mugursomu — ir viens no kombinatoriskās optimizācijas NP-pilnām problēmām. Savu nosaukumu dabūja 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ā.

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.

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 noteikto ietilpību. Uzdevums ir savākt mugursomu ar maksimālo priekšmetu vērtību tā, lai ievērotu tās summāra svara ierobežojumu.

Matemātiski uzdevums tie 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āra 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}\leq W$ un $x_{i}\in \{0,1\}$.

Uzdevuma par mugursomu variācijas

Eksistē daudz vispārinājumu šai problēmai,atkarīgi no nosacījumiem, kuri virzās 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 (angļu: 0-1 Knapsack Problem): ne vairāk kā viens eksemplārs katram priekšmietam.
2. Ierobežota mugursoma (angļu: Bounded Knapsack Problem): ne vairāk par noteikto eksemplāru skaitu katram priekšmietam.
3. Neierobežota mugursoma (angļu: Unbounded Knapsack Problem): patvaļīgais eksemplāru skaits katram priekšmetam.
4. Mugursoma ar vairākiem izvēles veidiem (angļu: Multiple-choice Knapsack Problem): priekšmeti ir sadalīti grupās un no katras grupas ir iespējams izvēlēties tikai vienu.
5. Salikta mugursoma (angļu: Multiple Knapsack Problem): ir dažas mugursomas, katras ar savu maksimālo svaru. Katru priekšmetu var vai nu atstāt, vai nu ievietot jebkurā mugursomā.
6. Daudzdimensiju mugursoma (angļu: Multy-dimensional knapsack problem): svaru vietā ir doti dažādi resursi, piemērām, svars, tilpums un kraušanas laiks. Katrs priekšmēts tērē iepriekš noteikto resursa summu. Jāizvēlās priekšmētu apakškopu tā, lai katra resursu kopējās izmaksas neparsniedza šī resursa maksimumu, pie tām lai priekšmetu kopēja vērtība būtu maksimāla.
7. Kvadrātiskā mugursomas problēma (angļu: Quadratic knapsack problem): kopējā vērtība ir noteikta ar nenegatīvu kvadratīsko formu.

Pielikumi

Nav zināms, kurš tieši formulēja matemātisko formulu mugursomas problēmai. Viens no pirmiem, kuri to pieminēja, bija Džordžs Ballards Metjūss savā rakstā 1897. gadā. Šīs problēmas intensīva pētīšana iesākas pēc D.B. Danciga 1957. gadā savā grāmatā «angļu: Discrete Variable Extremum Problem». It īpaši 70 – 90 gados, 20. gadsimtā, 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-pilnu 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 salaidē – kriptogrāfijā. Vienā no matemātiskas lingvistikas darbiem bija piedāvāta 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 uzbūvēja to 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 izveidoti daudzas Merkļa-Hellmaņa kriptosistēmas modifikācijas, ka arī pavisam jaunie kriptosistēmas, kuri balstījas uz mugursomas problēmu. Starp tiem 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 sarēžģ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 uzrāda uz priekšmēta klātbūtni mugursomā un 0 uz to prombūtni.

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=(3\ 4\ 6\ 7\ 10\ 11)$ 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 nepiecešama pieaugstinoša mugursoma, t.i. sakārtoti mugursomas vektora elementi ir pieaugstinoši. Tādā gadījumā katram atklātam tekstam eksistē tikai viens sašifrēts teksts. Dotajā piemērā mugursoma nav pieaugstinoša - ir iespējams saņemt to pašu sašifrētu tekstu 100010 un 001100 vektoriem.