Vozliščno pokritje s plešočimi kazalci

PUSTOSLEMŠEK, JURE (author), Čibej, Uroš (mentor)

V 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.

• Language: Slovenian
• Keywords: plešoči kazalci, vozliščno pokritje, razbitje, kraljice
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2022
• PID: 20.500.12556/RUL-139573
• COBISS.SI-ID: 120747523
• Publication date in RUL: 05.09.2022

Secondary language

• Language: English
• Title: Vertex cover with dancing links

Abstract

In this thesis we have implemented Knuth's algorithms X, C and C$^\$$. With these algorithms, we solved the $n$ queens problem and the minimum vertex cover problem. We defined generalized and colored exact covers. We reduced the $n$ queens problem to the generalized exact cover problem, and the minimum vertex cover problem to the optimal colored exact cover problem. We compared the efficiency of algorithms X and C$^\$$ to the efficiency of regular algorithms for solving those problems. We say that algorithm X is efficient for solving the $n$ queens problem, however, purpose-specific algorithms are better for the minimum vertex cover problem, but algorithm C$^\$$ is still effective for solving this problem on small and dense graph.

• Keywords: dancing links, vertex cover, exact cover, queens