Analiza problema obilaska šahovske ploče skakačem

završni rad

• Naslov (engleski): Analysis of Knight's Tour Problem
• Autor: Marko Palameta
• Mentor: Lana Horvat Dmitrović (mentor)
• Član povjerenstva: Lana Horvat Dmitrović (predsjednik povjerenstva)
• Član povjerenstva: Ana Žgaljić Keko (član povjerenstva)
• Član povjerenstva: Mate Puljiz (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2021-09-01, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Problem obilaska skakača na ploči je problem iz domene teorije grafova. Šahovska figura skakač, svojim potezima u obliku slova L, posjećuje polja šahovske ploče na način da ih posjeti samo jedanput. Općenito, riječ je o problemu pronalaska hamiltonovskog puta u neusmjerenom grafu. Za rješavanje problema koristi se Backtracking algoritam, uz primjenu Warnsdorffovog pravila za optimizaciju.

Sažetak (engleski)

A knight's tour problem is a problem from the domain of graph theory. The knight chess piece, with its moves in the shape of a letter L, traverses the squares of the chessboard in a way that visits each square only once. In general, this is a problem of finding a hamiltonian path in an undirected graph. The problem is solved using Backtracking algorithm, with the application of Warnsdorff's rule for optimization.

• Ključne riječi: Šah; Skakač; Graf; Hamiltonovski put; Warnsdorffovo pravilo; Pretraživanje prostora stanja; Algoritam DFS; Tremaux stablo; Backtracking
• Ključne riječi (engleski): Chess; Knight; Graph; Hamiltonian path; Warnsdorff's rule; State space search; DFS algorithm; Tremaux tree; Backtracking
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:755399
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-14 09:37:56