Učitavanje video playera...
01:09:50
Juraj Brigljević: Rješavanje problema maksimalnog težinskog nezavisnog skupa
Sažetak: Problem 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.
