Naslov
Heuristički algoritmi za 0-1 problem naprtnjače
(Heuristic algorithms for 0-1 knapsack problem)

Autori
Nakić, Anamari

Izvornik
Math.e : hrvatski matematički elektronski časopis (1334-6083) 4 (2005);

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, ostalo

Ključne riječi
0-1 problem naprtnjače; heuristički algoritmi
(0-1 knapsack problem; heuristic algorithms)

Sažetak
Spremajući se za put, vjerojatno se uvijek trudite ponijeti što manje stvari, a opet dovoljno da imate sve što vam može zatrebati. To vjerojatno činite odoka, imate već iskustva u pakiranju. No, u nekom skladištu ponekad je teško procijeniti koju robu staviti u kamion tako da bude maksimalno popunjen, a da zarada nakon istovara bude najveća moguća uz postojeća ograničenja (npr. veličina kamiona ili ukupna težina tereta). Optimalno je rješenje, kao i kod problema trgovačkog putnika, za velik broj predmeta (uz memorijska i procesorska ograničenja današnjih računala) teško pronaći pa ćemo se poslužiti heurističkim algoritmima. Naziv heuristički algoritam koristi se za opisivanje algoritma koji se bazira na heuristici. Takvi su algoritmi obično iterativni. Potragu za rješenjem počinju nekim trivijalnim dopustivim rješenjem problema koje je često daleko od optimalnog. Pri svakoj iteraciji modificiraju trenutno rješenje kako bi došli što bliže optimalnom. Heuristika se koristi prilikom odabira parametara za iduću iteraciju unutar algoritma kao i prilikom odabira konstanti koje se koriste tijekom algoritma. Heuristički algoritmi baziraju se na različitim strategijama: tako neki pronalaze ideju oponašajući kaljenje metala (eng. simulated annealing), neki penjanje uz planinu (eng. hill-climbing), a neki evolucijske procese.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA