Kombinatorno pretraživanje i heurističke metode

diplomski rad

• Naslov (engleski): Combinatorial Search and Heuristic Methods
• Autor: Domagoj Magaš
• Mentor: Andrea Aglić-Aljinović (mentor)
• Član povjerenstva: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Član povjerenstva: Mario Krnić (član povjerenstva)
• Član povjerenstva: Mario Bukal (č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: 2016-07-07, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Kombinatorno pretraživanje proučava algoritme za pronalaženje različitih rješenja problema za koje se vjeruje da su veoma teški u praksi. Algoritmi neiscrpnog pretraživanja zasigurno će dati rješenje, no nisu prihvatljivi zbog vremenske neoptimalnosti i ekponencijalne složenosti. Unatražno pretraživanje uz korištenje odsijecanja nevaljanih rješenja daleko je bolji izbor. Uniformna pretraga i različite varijacije heurističkih metoda koje izdvajaju djelomična saznanja o strukturi prostora pretraživanja poput oblikovanja ograničenja i osiguravanja lokalne konzistencije nude brži i efikasniji način do pronalaska odgovarajućeg prihvatljivog rješenja. Optimalnost, točnost i konačnost značajna su svojstva takvih algoritama.

Sažetak (engleski)

Combinatorial search study algorithms to find different solutions for problems that are believed to be very difficult in practise. Brute force algorithms will yield correct solution, but they have exponential complexity, they need huge ammount of time, so they are not optimaly acceptable. Backtracking algorithms with pruning of wrong partialy solutions are much better option to choose. Uniform search and different variations of heuristic methods which separate partial knowledge of space search structure like designing constraints and providing local consistency, give faster and more efficient way to find respective acceptable solution. Optimality, correctness and completeness are significant properties of those algorithms.

• Ključne riječi: algoritmi; kombinatorika; pretraživanje; heuristika; metoda; složenost
• Ključne riječi (engleski): algorithms; combinatorial; search; heuristic; method; complexity
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:360508
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 10:13:59