20.500.12556/DKUM-45202 Reševanje problema trgovskega potnika s paralelnim simuliranim ohlajanjem Solving travelling salesman problem with parallel simulated annealing V diplomskem delu skušamo s paralelizacijo algoritma simuliranega ohlajanja izboljšati čas reševanja problema trgovskega potnika. S pomočjo vmesnika OpenMP implementiramo paralelizacije algoritmov sosednosti k-opt, simulirano ohlajanje in izboljšavo le-tega – sprejemljivo simulirano ohlajanje. Predstavimo algoritme in zberemo njihove rezultate za paralelizacijo zanke, paralelizacijo particij, paralelizacijo z različnim razponom in prilagodljivo paralelizacijo simuliranega ohlajanja. Prvi del predstavlja opis problema trgovskega potnika, vmesnika OpenMP, opis implementiranih algoritmov in njihovih paralelizacij. V zadnjem delu so predstavljeni rezultati na problemih trgovskega potnika iz knjižnice TSPLIB, njihova medsebojna primerjava ter možnosti za nadaljnje raziskave. The diploma thesis focuses on improving the solving time for the travelling salesman problem, by parallelizing the simulated annealing algorithm. We implement parallelization of local k-opt algorithms, simulated annealing, and an improvement of this - the acceptance simulated annealing, by using OpenMP interface. We present algorithms and gather their results using the parallelization of the loops, parallelization of the partitions, parallelization with different range, and adaptable parallelization of simulated annealing. The first part covers the presentation of the travelling salesman problem, the OpenMP interface, and the description of the implemented algorithms and their parallelization. The last part features the results based on the travelling salesman problems from the TSPLIB library, their mutual comparison, and the possibilities for further research. problem trgovskega potnika simulirano ohlajanje paralelizacija simuliranega ohlajanja traveling salesman problem simulated annealing simulated annealing parallelization true true false M. Strašek Slovenski jezik Angleški jezik Diplomsko delo/naloga 2014-08-18 11:45:45 2015-11-06 13:21:00 2022-05-15 03:06:21 2021-05-02 03:09:39 2014 0 [Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.41.021:519.8(043.2) 19113238 URN:SI:UM:DK:VXKTAMD5 UNI_Strasek_Matej_2014.pdf UNI_Strasek_Matej_2014.pdf 1 2E698E4F3A905169AF55802573F84F03 567c120d51ce3282f3abb59ae33c1415c39e9a4d6e2ade58d887401c7afec10d 08bed643-7c0b-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=65306 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0