Combinatorial Search and Heuristic Methods

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.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