Pronalaženje najduljeg puta u grafu koristeći optimizacijske algoritme

diplomski rad

• Naslov (engleski): Finding the longest path in a graph using optimization algorithms
• Autor: Laura Torić
• Mentor: Domagoj Jakobović (mentor)
• Član povjerenstva: Domagoj Jakobović (predsjednik povjerenstva)
• Član povjerenstva: Marko Đurasević (član povjerenstva)
• Član povjerenstva: Leonardo Jelenković (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2022-06-28, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Graf problemi su jedni od najvažnijih i najizazovnijih problema u računarskoj znanosti. Razlog tome je što mogu modelirati svijet oko nas na jednostavan i strukturiran način, te se primjenjuju u mnogim stvarnim situacijama.

Ovaj rad se fokusira na problem najdužeg puta u netežinskim cikličkim grafovima. Predložena su dva različita pristupa, evolucijski algoritam i algoritam zamjene puteva. Pokazuje se da algoritam zamjene puteva dominira nad evolucijskim algoritmom, kako u smislu vremena izvršavanja, tako i u kvaliteti izlaznih rješenja. Algoritam proizvodi rješenja koja se razlikuju za samo $1\%$ od najbolje-do-sada-izračunatih rješenja u samo nekoliko minuta. Glavna ideja algoritma je iterativno nadograđivati put pronalaženjem novih puteva između čvorova u trenutnom putu.

Algoritmi su testirani na skupu podataka Kalodont koji se sastoji od $159,836$ riječi. Graf stvoren nad tim podacima sadrži $159,836$ vrhova i $120,053,427$ rubova. Najbolje-do-sada-izračunato rješenje sastoji se od $26,552$ riječi, a naš je algoritam uspio pronaći rješenje koje se sastoji od $26,521$ riječi.

Sažetak (engleski)

Graph problems are one of the most important, and most challenging problems in Computer Science. This is because they can model the world around us in a simple and structured way and are applied in many real life situations.

This thesis focuses on the Longest Path Problem in Unweighted Cyclic Graphs. Two different approaches are proposed, Evolutionary algorithm and Switch Path algorithm. The Switch Path algorithm shows to dominate the Evolutionary algorithm, both in the terms of execution time, and in the quality of output solutions. It produces solutions that differ in only $1\%$ from the best-so-far-computed solution in just a few minutes. The main idea of the algorithm is to iteratively build upon a path by finding new paths between nodes in the current path.

The algorithms are tested on the Kalodont dataset which consists of $159,836$ words. This creates a graph with $159,836$ vertices and $120,053,427$ edges. The best-so-far-computed solution consists of $26,552$ words, and our algorithm managed to find a solution consisting of $26,521$ words.

• Ključne riječi: Teorija grafova; Problem najduljeg puta; Kalodont; Genetski algoritam; Evolucijski algoritam; Pretraživanje u dubinu
• Ključne riječi (engleski): Graph theory; Longest path problem; Kalodont; Genetic algorithm; Evolutionary algorithm; Depth first search
• Jezik: engleski
• URN:NBN: urn:nbn:hr:168:396934
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-13 14:04:59