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

master's thesis

• Title (english): Finding the longest path in a graph using optimization algorithms
• Author: Laura Torić
• Mentor: Domagoj Jakobović (mentor)
• Committee member: Domagoj Jakobović (predsjednik povjerenstva)
• Committee member: Marko Đurasević (član povjerenstva)
• Committee member: Leonardo Jelenković (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2022-06-28, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: Teorija grafova; Problem najduljeg puta; Kalodont; Genetski algoritam; Evolucijski algoritam; Pretraživanje u dubinu
• Keywords (english): Graph theory; Longest path problem; Kalodont; Genetic algorithm; Evolutionary algorithm; Depth first search
• Language: english
• URN:NBN: urn:nbn:hr:168:396934
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-13 14:04:59