Vaš brskalnik ne omogoča JavaScript!
JavaScript je nujen za pravilno delovanje teh spletnih strani. Omogočite JavaScript ali pa uporabite sodobnejši brskalnik.
Repozitorij Univerze v Ljubljani
Nacionalni portal odprte znanosti
Odprta znanost
DiKUL
slv
|
eng
Iskanje
Brskanje
Novo v RUL
Kaj je RUL
V številkah
Pomoč
Prijava
Podrobno
Optimizacija preiskovanja grafov z vložitvami grafov
ID
CIGLARIČ, TIMOTEJ
(
Avtor
),
ID
Robnik Šikonja, Marko
(
Mentor
)
Več o mentorju...
PDF - Predstavitvena datoteka,
prenos
(433,35 KB)
MD5: 4CD52369EA54C4E2CB91AA8A005066CE
Galerija slik
Izvleček
Problem usmerjanja vozil s kapaciteto je NP-poln kombinatorični problem. Poleg njegove uporabnosti za dostavne službe se lahko nanj učinkovito preslika tudi veliko drugih problemov. Za reševanje problema uporabim rekurenčno nevronsko mrežo GRU z mehanizmom pozornosti. Po fazi učenja, ki traja toliko časa kot uporaba stohastičnih optimizacijskih algoritmov na več tisoč primerih, dobimo na majhnih grafih primerljivo dobre rezultate, na večjih grafih pa se zaradi povečevanja kompleksnosti problema nevronski model ne uči več dovolj hitro in je slabši. Med vložitvami grafov, ki sem jih preizkusil, dajeta najboljše rezultate node2vec in GraRep.
Jezik:
Slovenski jezik
Ključne besede:
nevronska mreža
,
graf
,
kombinatorična optimizacija
,
problem usmerjanja vozil
,
vložitve grafov
Vrsta gradiva:
Diplomsko delo/naloga
Tipologija:
2.11 - Diplomsko delo
Organizacija:
FRI - Fakulteta za računalništvo in informatiko
Leto izida:
2021
PID:
20.500.12556/RUL-130322
COBISS.SI-ID:
77579779
Datum objave v RUL:
13.09.2021
Število ogledov:
1538
Število prenosov:
114
Metapodatki:
Citiraj gradivo
Navadno besedilo
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
CIGLARIČ, TIMOTEJ, 2021,
Optimizacija preiskovanja grafov z vložitvami grafov
[na spletu]. Diplomsko delo. [Dostopano 17 marec 2025]. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=130322
Kopiraj citat
Objavi na:
Sekundarni jezik
Jezik:
Angleški jezik
Naslov:
Graph search optimization using graph embeddings
Izvleček:
The capacitated vehicle routing problem is an NP-complete combinatorial problem. In addition to its usefulness for delivery services, many other problems can be efficiently mapped to it. To solve the problem, I use the GRU recurrent neural network with the attention mechanism. After a learning phase that lasts as long as using stochastic optimization algorithms on thousands of cases, we get comparatively good results on small graphs. On larger graphs the neural models do not learn fast enough and produce worse results due to an increasing problem complexity. Among the tested graph embedding methods, node2vec and GraRep give the best results.
Ključne besede:
neural net
,
graph
,
combinatorial optimization
,
vehicle routing problem
,
graph embeddings
Podobna dela
Podobna dela v RUL:
Kombinatorična igra Brstički
Anonimnost v protokolih za sledenje stikov
Strojno učenje za kombinatorično optimizacijo na problemu usmerjanja vozil
Optimizacija poizvedb SQL
Izdelava zbirke omrežij slovenskega izvora
Podobna dela v drugih slovenskih zbirkah:
Ni podobnih del
Nazaj