diplomsko delo
Matej Strašek (Avtor), Janez Brest (Mentor), Aleš Zamuda (Komentor)

Povzetek

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.

Ključne besede

problem trgovskega potnika;simulirano ohlajanje;paralelizacija simuliranega ohlajanja;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Založnik: M. Strašek
UDK: 004.021:519.8(043.2)
COBISS: 19113238 Povezava se bo odprla v novem oknu
Št. ogledov: 1838
Št. prenosov: 74
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Solving travelling salesman problem with parallel simulated annealing
Sekundarni povzetek: 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.
Sekundarne ključne besede: traveling salesman problem;simulated annealing;simulated annealing parallelization;
URN: URN:SI:UM:
Vrsta dela (COBISS): Diplomsko delo/naloga
Komentar na gradivo: Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informacijske tehnologije
Strani: VI, 30 f.
ID: 9063593