Pohlepni algoritmi za rješavanje problema trgovačkog putnika

undergraduate thesis

• Title (english): Greedy Algorithms for Solving Travelling Salesman Problem
• Author: Mateo Pejić
• Mentor: Tomislav Burić (mentor)
• Committee member: Tomislav Burić (predsjednik povjerenstva)
• Committee member: Ilko Brnetić (član povjerenstva)
• Committee member: Josipa Pina Milišić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2019-07-12, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Problem trgovačkog putnika je jedan od najčuvenijih i najintrigantijih problema koji se jednostavno modeliraju i preformuliraju pomoću grafova.
On gledan kroz prizmu teorije grafova glasi ovako: U potpunom težinskom grafu nađi hamiltonovski ciklus minimalne duljine.
Pri rješavanju ovog problema koriste se razne metode među kojima su i pohlepni algoritmi. Prednosti pohlepnih algoritama su jednostavnost, intuitivnost i mala kompleksnost, a nedostaci su kratkovidni pogled (gleda se najbolje rješenje za taj korak) zbog čega ne garantira dobra globalna rješenja, te dosta ovise o instanci problema zbog čega je teško napraviti robustan algoritam koji radi za sve instance problema.

Abstract (english)

Travelling salesman problem is one of the most famous and the most intriguing problems which can be easily modelled using graph theory. When defined by graph theory this problem looks like this: In complete weighted graph find the Hamiltonian cycle of the minimum length.
Because travelling salesman problem is Np-hard problem we use a variety of methods to solve it.
The simplest methods are greedy algorithms. Benefits of greedy algorithms are simplicity, intuition and small complexity. Disadvantages of greedy algorithms are shortsightedness (they are only looking for the best choice for a next step) and their dependency on instance of a problem, which makes it difficult to create a robust algorithm that works for all instances of the problem.

• Keywords: Hamiltonovski ciklus; Pohlepni algoritam; Problem trgovačkog putnika; Graf; Matrica susjedstva
• Keywords (english): Hamiltonian cycle; Greedy algorithms; Graph; Travelling salesman problem; Neighborhood matrix
• Language: croatian
• URN:NBN: urn:nbn:hr:168:592307
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2020-01-07 21:11:05