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

diplomsko delo

Jure Pustoslemšek (Author), Uroš Čibej (Mentor)

Abstract

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.

Keywords

plešoči kazalci;vozliščno pokritje;razbitje;kraljice;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Data

Language:	Slovenian
Year of publishing:	2022
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[J. Pustoslemšek]
UDC:	004:51(043.2)
COBISS:	120747523
Views:	23
Downloads:	14
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Vertex cover with dancing links
Secondary 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.
Secondary keywords:	dancing links;vertex cover;exact cover;queens;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;Računalništvo;Univerzitetna in visokošolska dela;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000407
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	54 str.
ID:	16372684