20.500.12556/RUL-159389 Reševanje problema geometrijskega 0/1-nahrbtnika Solving the geometric knapsack problem V diplomski nalogi obravnavamo problem geometrijskega 0/1-nahrbtnika. Cilj tega NP-težkega problema je iskanje optimalne zapolnjenosti pravokotnih vsebnikov z naborom predmetov različnih velikosti. V raziskavi smo uporabili več determinističnih in stohastičnih pristopov za reševanje tega problema. Implementirali in testirali smo strategijo najboljšega prileganja, konstruktivni hevristični algoritem in hevristiko skupnega obsega. Zmogljivost teh metod smo izboljšali z uporabo globalnih optimizacijskih algoritmov, kot so simulirano ohlajanje in genetski algoritem. Izkazalo se je, da je izmed vseh algoritmov vstavljanja najbolj uspešna hevristika skupnega obsega, največje izboljšanje rešitev pa je pri vseh algoritmih vstavljanja prinesla uporaba v kombinaciji z genetskim algoritmom. This thesis addresses the geometric 0/1 knapsack problem. The goal of this NP-hard problem is finding the optimal packing of a rectangular container with a set of items of different sizes. We employed and tested various deterministic and stochastic approaches to solve this problem, including the best-fit-first strategy, the constructive heuristic algorithm, and the common perimeter heuristic. Additionally, we improved the performance of the insertion algorithms using global optimization algorithms such as simulated annealing and genetic algorithms. Among the employed insertion algorithms, the common perimeter heuristic performed the best. For all insertion algorithms, the greatest improvement was attained by using them in combination with the genetic algorithm. algoritmi metahevristika genetski algoritem simulirano ohlajanje optimizacija algorithms metaheuristics genetic algorithm simulated annealing optimization true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2024-07-09 09:45:00 2024-07-09 09:45:04 2024-07-19 08:40:51 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 37577 202276099 Skrbec_Nejc_-_Resevanje_problema_geometrijskega_0-1-nahrbtnika.pdf Skrbec_Nejc_-_Resevanje_problema_geometrijskega_0-1-nahrbtnika.pdf 1 E6F0188A67F753B0405EAB026B665262 6012eac06b460660cf52c715ad33b9c215e3a665d784b4468c76c7f3abce2832 264243c4-3dc7-11ef-8f74-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=187391 Fakulteta za računalništvo in informatiko 0 0 0