Seminar za teorijsko računarstvo i Seminar za matematičku logiku i osnove matematike

lokacija: 
PMF Matematički odsjek
vrijeme: 
13.11.2023 - 17:15 - 19:00
Na zajedničkom sastanku Seminara za teorijsko računarstvo te Seminara za matematičku logiku i osnove matematike,
u ponedjeljak 13. studenoga 2023. godine u 17:15 sati, u predavaonici 201,
Juraj Brigljević će održati predavanje
 
Rješavanje problema maksimalnog težinskog nezavisnog skupa
 
SažetakProblem maksimalnog težinskog nezavisnog skupa (MWIS) spada u područje diskretne optimizacije na grafovima. S obzirom da je riječ o NP-teškom problemu, opravdano je korištenje heuristika za njegovo rješavanje u općenitom slučaju. Heuristika koju smo proučili utemeljena je na dvjema paradigmama: ponavljanom lokalnom pretraživanju (ILS) odnosno varijabilnom spustu uz korištenje susjedstava (VND). Testiranjem na bazama podataka BHOSLIB i DIMACS uvjerili smo se da navedena heuristika može izrazito brzo pronaći dobra rješenja, a vrlo često i optimalna odnosno najbolja poznata rješenja. Osim heuristike ILS-VND, koja radi na općenitim grafovima, proučili smo postoji li bolje rješenje za jednu posebnu vrstu grafova, a to su stabla. Pokazalo se da se pomoću paradigme dinamičkog programiranja može definirati egzaktni algoritam koji rješava MWIS problem na stablima u linearnom vremenu s obzirom na broj vrhova.
 
Share this