Kombinatorno pretraživanje i heurističke metode

master's thesis

• Title (english): Combinatorial Search and Heuristic Methods
• Author: Domagoj Magaš
• Mentor: Andrea Aglić-Aljinović (mentor)
• Committee member: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Committee member: Mario Krnić (član povjerenstva)
• Committee member: Mario Bukal (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2016-07-07, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: algoritmi; kombinatorika; pretraživanje; heuristika; metoda; složenost
• Keywords (english): algorithms; combinatorial; search; heuristic; method; complexity
• Language: croatian
• URN:NBN: urn:nbn:hr:168:360508
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2018-02-06 10:13:59