Vozliščno pokritje s plešočimi kazalciPUSTOSLEMŠEK, JURE (Avtor) Čibej, Uroš (Mentor) plešoči kazalcivozliščno pokritjerazbitjekraljiceV diplomskem delu smo implementirali Knuthove algoritme X, C in C$^\$$. S temi algoritmi smo reševali problem $n$ kraljic in iskanja minimalnega vozliščnega pokritja grafa. Definirali smo pojma posplošenega in pobarvanega razbitja. Problem $n$ kraljic smo prevedli na iskanje posplošenega razbitja, iskanje minimalnega vozliščnega pokritja pa na iskanje najcenejšega pobarvanega razbitja. Primerjali smo učinkovitost algoritmov X in C$^\$$ v primerjavi z običajnimi algoritmi za reševanje teh problemov. Videli smo, da je algoritem X učinkovit pri reševanju problema $n$ kraljic, za iskanje minimalnega vozliščnega pokritja pa so bolj primerni namenski algoritmi, vendar pa je algoritem C$^\$$ kljub temu uporaben pri reševanju tega problema na manjših in gostih grafih.20222022-09-05 09:30:00Diplomsko delo/naloga139573VisID: 34987COBISS_ID: 120747523sl