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

PUSTOSLEMŠEK, JURE (avtor), Č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.

• Jezik: Slovenski jezik
• Ključne besede: plešoči kazalci, vozliščno pokritje, razbitje, kraljice
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2022
• PID: 20.500.12556/RUL-139573
• COBISS.SI-ID: 120747523
• Datum objave v RUL: 05.09.2022

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Vertex cover with dancing links

Izvleček

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.

• Ključne besede: dancing links, vertex cover, exact cover, queens