prikaz prve stranice dokumenta Problem maksimalnog težinskog nezavisnog skupa u grafu
  Preuzmi
PDF 1.55 MB
diplomski rad
Problem maksimalnog težinskog nezavisnog skupa u grafu
Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2023. urn:nbn:hr:217:516468
Brigljević, Juraj
Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Institucijski repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta

Citirajte ovaj rad

Brigljević, J. (2023). Problem maksimalnog težinskog nezavisnog skupa u grafu (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:217:516468

Brigljević, Juraj. "Problem maksimalnog težinskog nezavisnog skupa u grafu." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2023. https://urn.nsk.hr/urn:nbn:hr:217:516468

Brigljević, Juraj. "Problem maksimalnog težinskog nezavisnog skupa u grafu." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2023. https://urn.nsk.hr/urn:nbn:hr:217:516468

Brigljević, J. (2023). 'Problem maksimalnog težinskog nezavisnog skupa u grafu', Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 17.05.2024., https://urn.nsk.hr/urn:nbn:hr:217:516468

Brigljević J. Problem maksimalnog težinskog nezavisnog skupa u grafu [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2023 [pristupljeno 17.05.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:516468

J. Brigljević, "Problem maksimalnog težinskog nezavisnog skupa u grafu", Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2023. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:516468

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:516468
Podaci o radu
NaslovProblem maksimalnog težinskog nezavisnog skupa u grafu
Naslov (engleski)The maximum weight independent set problem in a graph
AutorJuraj Brigljević
MentorRobert Manger (mentor)
Član povjerenstvaRobert Manger (predsjednik povjerenstva)
Član povjerenstvaGoran Igaly (član povjerenstva)
Član povjerenstvaDijana Ilišević (član povjerenstva)
Član povjerenstvaZrinka Franušić (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
(Matematički odsjek)
Zagreb
Datum i država obrane2023-09-26, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Sažetak
Problem maksimalnog težinskog nezavisnog skupa u grafu jedan je NP-težak problem optimizacije. On ima primjene u stvarnome svijetu, koje zahtijevaju brze algoritme koji pronalaze kvalitetna rješenja. Osim toga, u bliskoj je vezi s problemima maksimalne težinske klike i maksimalnog težinskog vršnog pokrivača. U ovome radu definirani su navedeni problemi i iskazane su njihove međusobne veze. Proučena je njihova vremenska složenost u teorijskom smislu i iskazani su relevantni rezultati. Kako je problem maksimalnog težinskog nezavisnog skupa NP-težak, u njegovu rješavanju posežemo za heuristikom kako bismo na brz način pronašli kvalitetna rješenja u općenitom slučaju, a proučavamo i kako se problem može egzaktno riješiti u slučaju stabla. Heuristika koju smo proučili temeljena je na dvjema paradigmama: ponavljanom lokalnom pretraživanju i varijabilnim spustom uz korištenje susjedstava. Ponavljano lokalno pretraživanje heuristika je u kojoj se trudimo pronaći sve bolje rješenje pretraživanjem neke lokalne okoline trenutnoga rješenja. Ideja je da se na taj način trudimo doseći lokalni optimum pod pretpostavkom određene neprekidnosti područja pretraživanja. Kako na taj način možemo zapeti u lokalnom optimumu, u navedeni postupak uključujemo korak perturbacije koji nastoji pronaći ostale lokalne optimume. Da bismo uspjeli efikasno istražiti blizinu trenutnoga rješenja, potreban nam je dobar pojam bliskih rješnja. Iz tog razloga posežemo varijabilnom spustu uz korištenje susjedstava, u kojemu definiramo par susjedstava unutar kojih tražimo bolja rješenja od trenutnoga. Navedeni algoritam je implementiran i testiran na bazama podataka BHOSLIB i DIMACS, na kojima je uočeno da daje kvalitetna rješenja u izrazito malome vremenu.
Sažetak (engleski)
The maximum weight independent set is an NP-hard optimization problem. It has some real-world applications, which require quick algorithms that find quality solutions. Also, it is in a close relationship with the maximum weight clique problem and the maximum weight vertex cover problem. In this thesis, the listed problems are defined and their relationships are expressed and proven. Their time complexity is studied in a theoretical sense and the relevant results are expressed. Since the maximum weight independent set is NP-hard, quality solutions in the general case are found by solving it in a heuristic approach, while the problem is also solved exactly in the case of trees. The studied heuristic is based on two paradigms: iterated local search and variable neighborhood descent. Iterated local search is a heuristic in which we try to find better solutions by searching the local neighborhood of the current solution. The idea is that by doing so we try to reach a local optimum under the assumption of continuity of the search area. Since this can lead to the algorithm getting stuck in a local optimum, a perturbation step is included which attempts to find other local optima. In order to efficiently search the vicinity of the current solution, a good notion of similar solutions is required. For that goal, variable neighborhood descent is defined alongside two notions of neighborhoods which are deemed to contain similar solutions. The algorithm is implemented and tested on the BHOSLIB and DIMACS databases, where it is observed that it quickly finds quality solutions.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:217:516468
Studijski programNaziv: Računarstvo i matematika
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: sveučilišni magistar računarstva i matematike (univ. mag. inf. et math.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2024-01-30 12:10:01