izpis_h1_title_alt

Pregled hevristik za problem trgovskega potnika
GABERC ARTENJAK, JAKOB (Avtor), Robič, Borut (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (799,81 KB)

Izvleček
Problem trgovskega potnika je iskanje najkrajše poti med vsemi mesti, kjer obiščemo vsako mesto natanko enkrat in se vrnemo nazaj na začetno mesto. Na problem lahko gledamo kot na iskanje najcenejšega cikla v grafu, ki obišče vse točke natanko enkrat. Pridobivanje optimalne rešitve problema trgovskega potnika je praktično neuporabno zaradi časovne zahtevnosti problema. Hevristični algoritmi so dobra alternativa optimalnemu reševanju problema, saj pridobijo rešitev v praktično izvedljivem času, a izgubijo jamstvo optimalne rešitve. Uvod diplomske naloge vsebuje osnovni opis problema trgovskega potnika. Temu sledijo primeri praktične uporabe problema, natančnejši opis problema, opredelitev hevristik in opis testnega okolja. Glavni del naloge vsebuje šest hevrističnih algoritmov, ki smo jih implementirali in jih testirali. Izbrali smo algoritem Lokalnega iskanja z operacijo k-opt, Lin-Kernighanov algoritem, algoritem Simuliranega ohlajanja, algoritem Kolonije mravelj, algoritem Optimizacije z roji delcev in algoritem Oponašanja volkov. Končni del naloge vsebuje primerjavo eksperimentalnih rezultatov in komentar nad uporabljeno metodologijo za primerjavo algoritmov.

Jezik:Slovenski jezik
Ključne besede:hevristika, Problem trgovskega potnika, simetrični Problem trgovskega potnika, Lokalno iskanje, k-opt, Lin-Kerninghan, Simulirano ohlajanje, Kolonija mravelj, Optimizacija z roji delcev, Oponašanje volkov
Vrsta gradiva:Diplomsko delo/naloga (mb11)
Organizacija:FRI - Fakulteta za računalništvo in informatiko
Leto izida:2020
COBISS.SI-ID:30748419 Povezava se odpre v novem oknu
Število ogledov:113
Število prenosov:53
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
:
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Overview of heuristics for the traveling salesman problem
Izvleček:
The Traveling Salesman Problem is finding the shortest path through all the cities, where each city is visited precisely once, while the first and the last city are the same. This can be formulated as searching for the shortest cycle in a graph which visits each vertex exactly once. Finding the optimal solution is practically fruitless due to the time complexity of the problem. Heuristic algorithms are good alternatives to algorithms, which search for the optimal solution, because a solution can be found in a practically achievable time frame; however, the guarantee of the solution being optimal is lost. The introduction of this work includes a basic description of The Traveling Salesman Problem, which is followed by a list of practical applications, a detailed description of the problem, the classification of heuristic algorithms and the details of the experimental environment. The main part of this work includes six algorithms, which were implemented and tested. The selected algorithms are Local Search with the k-opt operation; Lin-Kernighan algorithm; Simulated Annealing; Ant Colony Algorithm; Particle Swarm Optimization and Wolfpack algorithm. The final part of this work is a comparison of the results from each algorithm and a commentary on the methodology that was used for the comparison of the algorithms.

Ključne besede:heuristic, Traveling Salesman Problem, symetric Traveling Salesman Problem, Local search, k-opt, Lin-Kerninghan, Simulated annealing, Ant colony, Particle swarm optimization, Wolfpack

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj