1. Grafični prikaz Kruskalovega algoritma v 3D prostoru : diplomsko deloJurij Cerar, 2022, diplomsko delo Opis: V diplomskem delu smo implementirali aplikacijo za demonstracijo Kruskalovega
algoritma nad oblaki točk LiDAR v 3D prostoru ter izmerili čas algoritma in čas
upodabljanja, kakor tudi pomnilniško zahtevnost algoritma. Poleg tega smo tudi
primerjali uporabo evklidske razdalje in intenzitete kot cene povezav. Zato smo ustvarili namizno aplikacijo, ki prebere točke LiDAR in jih izriše v 3D prostoru. Nato izvede Kruskalov algoritem nad temi točkami ter prikaže vmesne rezultate algoritma. Zaradi velikega števila začetnih povezav grafa smo uvedli aproksimacijo s pomočjo enakomerne mreže. Ugotovili smo da je uporaba intenzitete kot cene hitrejša od uporabe evklidske razdalje. Ugotovili smo tudi, da poraba pomnilnika narašča linearno glede na število vozlišč. Poleg tega smo preučili, kako nam gradnja minimalnega vpetega drevesa omogoča lažje preučevanje točk.
Ključne besede: Kruskalov algoritem, graf, format LAS, OpenGL
Objavljeno v DKUM: 21.12.2022; Ogledov: 749; Prenosov: 85
 Celotno besedilo (1,54 MB) |
2. ISKANJE MINIMALNEGA VPETEGA DREVESA Z ALGORITMOM BORUVKEBenjamin Dobravec, 2015, diplomsko delo Opis: V diplomskem delu smo opisovali delovanje algoritmov za sikanje minimalnih vpetih dreves s posebnim poudarkom na algoritmu Boruvka. Vsi trije eksaktni algoritmi za iskanje minimalnih vpetih dreves so bili implementirani v testni aplikaciji, kjer lahko uporabnik izbira med Primovim, Kruskalovim in algoritmom Boruvke. Minimalno vpeto drevo lahko iščemo na naključnem polnem grafu, ki ga generira sama aplikacija ali pa na uporabniško generiranem grafu. V obeh primerih sta vhodni graf in rešitev grafično prikazana. Diplomo zaključujemo s primerjavo časovne zahtevnosti vseh treh algoritmov.
Ključne besede: minimalna vpeta drevesa, algoritem Boruvka, Kruskalov algoritem, Primov algoritem
Objavljeno v DKUM: 14.10.2015; Ogledov: 1846; Prenosov: 199
Celotno besedilo (2,55 MB) |
3. PROBLEM KITAJSKEGA POŠTARJA S PRIORITETNIMI VOZLIŠČITomaž Kramberger, 2010, doktorska disertacija Opis: V doktorski disertaciji z naslovom Problem kitajskega poštarja s prioritetnimi vozlišči je preučevana posplošitev problema kitajskega poštarja, v kateri je podmnožica vozlišč utežena in vrstni red obiska vozlišč vpliva na vrednost namenske funkcije. Preučevan problem je dokazano NP-težek. V disertaciji sta predstavljeni in preučevani dve konstrukcijski hevristiki. Za eno izmed njih je dokazano, da ob določenih pogojih vrne optimalne rešitve. Hevristiki sta implementirani in testirani na več razredih naključno tvorjenih instanc.
Ključne besede: problem kitajskega poštarja, problemi usmerjanja, Eulerjev graf, prioritetna vozlišča, modificiran algoritem Dijkstre, modificiran Kruskalov algoritem
Objavljeno v DKUM: 27.05.2010; Ogledov: 4016; Prenosov: 452
Celotno besedilo (10,28 MB) |
