This master's thesis deals with informed search algorithms. It's theoretical section summarizes basic theoretical ideas and terms which are related to this topic. It means especially discrete mathematics, graph theory, artificial intelligence and agent systems. Cardinal aim of this section is to provide theoretical analysis of search algorithms and to classify them into informed and uninformed classes. Theoretical section describes basic search strategies such as breadth first search, deep first search and modifications of these strategies, then it is focused on informed search algorithms, specifically A* (A-Star), IDA* (Iterative Deepening A-Star) and SMA* (Simplified Memory bounded A-star). It also describes topics related to informed search strategies -- heuristic functions and problem relaxation method. Given algorithms are analyzed in order to compare their time and space complexity. Main goal of practical part of this thesis is to design and implement software application, which will use informed and uninformed search strategies described in theoretical section. This application is intended to solve fifteen puzzle problem, so-called Lloyds fifteen puzzle game. First part of practical section analyses fifteen puzzle from mathematical and informatical perspective, then it examines possible implementation variants of algorithms and heuristics and proposes design of the application. Description of main interfaces and classes of the realized application follows. At the end of this section the analysis of informed algorithms and heuristics is performed using the implemented application and obtained results are compared to theoretical characteristics of these algorithms.

Assembling different kinds of items, everything from furniture to hobby models, takes a certain process to complete and this process can vary in complexity. An interesting aspect of this process is what components are available during assembly. The optimal scenario would be to have all required components available but sometimes that might not be the case. For a computer, this problem can be difficult to solve and requires specific environments to complete an assembly task. In this thesis work, block puzzles with various blueprints were used to complete assemblies with two different lists of components; one whole set of correct components and one with mixed that may or may not work for a blueprint. Three different methods were used to conduct the assemblies, one random based method, one that used the informed search method iterative deepening A* and one reinforcement learning method that used dueling deep Q-networks. The assembly time and accuracy between a completed configuration and the blueprint were measured for each method, where the informed search performed best in terms of accuracy but had a long assembly time. The reinforcement learning method did not perform well in terms of accu-racy between blueprint and configuration, but had fast assembly time, and in its current state would not be suitable to use to solve the given problem. / <p>Examensarbetet är utfört vid Institutionen för teknik och naturvetenskap (ITN) vid Tekniska fakulteten, Linköpings universitet</p>