Eksperimentalno ovrednotenje algoritmov za problem razmeščanja centrov

magistrsko delo

Miha Eleršič (Avtor), Jurij Mihelič (Mentor)

Povzetek

V magistrskem delu predstavimo in implementiramo algoritme za reševanje problema razmeščanja centrov. Osredotočimo se na obstoječe približne algoritme. Razvijemo tudi nov natančen algoritem, ki je občutno hitrejši od izčrpnega preiskovanja. Za potrebe testiranja implementiramo generator naključnih testnih primerov za različne strukture grafov. Ta podpira generiranje naključnih povezanih grafov, dvodimenzionalnih mrež in brezlestvičnih omrežij. Našo implementacijo približnih algoritmov preverimo na standardni knjižnici testnih primerov in na primerih, generiranih z našim generatorjem. Za približne algoritme primerjamo razmerje med časom izvajanja in kakovostjo rešitve.

Ključne besede

algoritmi na grafih;kombinatorična optimizacija;razmeščanje centrov;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2018
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[M. Eleršič]
UDK:	519.8
COBISS:	18455129
Št. ogledov:	1211
Št. prenosov:	213
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Experimental Evaluation of Algorithms for the Vertex k-center Problem
Sekundarni povzetek:	In this thesis we present and implement algorithms for the $k$-center problem. We focus on existing heuristic algorithms. We also develop a new exact algorithm and show its superiority over the exhaustive enumeration. For testing purposes we implemented a random graph generator. It can generate random connected graphs, two-dimensional grids and scale-free networks. Our implementation of algorithms was tested on the standard test suite and the graphs generated by our generator. We also compare the ratio between computation time and result quality of heuristic algorithms.
Sekundarne ključne besede:	graph algorithms;combinatorial optimization;vertex k-center;
Vrsta dela (COBISS):	Magistrsko delo/naloga
Študijski program:	0
Komentar na gradivo:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Računalništvo in matematika - 2. stopnja
Strani:	VII, 56 str.
ID:	10962322