|
|
Sub-optimal algorithms for solving sliding puzzles
Michalík, Petr ; Surynek, Pavel (advisor) ; Hric, Jan (referee)
Title: Sub-optimal algorithms for solving sliding puzzles Author: Petr Michalík Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: RNDr. Pavel Surynek, Ph.D. Supervisor's e-mail address: Pavel.Surynek@mff.cuni.cz In the present work techniques for solving the so-called sliding tiles puzzles, which generate optimal or sub-optimal solution, are studied. This thesis focuses especially on a specific variant of the puzzle: the (n^2-1)-puzzle. This work shows and compares current methods for solving this type of problem. A choosen method is a subject to a close analysis of complexity and is also implemented so that theoretical and experimental results could be confronted. An alternative sub-optimal algorithm is proposed and its theoretical analysis is presented. This algorithm is implemented as well and is compared with the existing algorithm. Both the theoretical analysis and the test results show that better (shorter) solutions can often be obtained using this alternative algorithm.
|
|
|
Efficient SAT Solver
Balyo, Tomáš ; Surynek, Pavel (advisor) ; Mareš, Martin (referee)
The boolean satisfaction problem (SAT) is one of the most important and most studied problems of artificial intelligence. Many theoretical and real life problems are transformed to SAT and solved using a SAT solver. During the research for this thesis two SAT solvers were developed. They are described and compared with several of today's state-of-art SAT solvers. The presented solvers in many cases outperform the 2007's SAT competition winner R-sat and other famous SAT solvers. These two new solvers thank their speed to the implementation techniques used and to their decision heuristic, which is very efficient while absolutely costless.
|
|
|
Generating of self-replicating cellular automata
Bardiovský, Vojtech ; Surynek, Pavel (advisor) ; Toropila, Daniel (referee)
The family of self-replicating cellular automata is interesting mainly for being able to demonstrate that even simple environments can make rise to structures capable of self-replication. Besides creating its own copy, a purposedly designed automaton can produce additional side patterns during its lifetime. The aim of the work is to create a cellular automata simulation environment that is flexible and fast, as some cellular automata become interesting only after thousands or millions of steps. The second aim of the work is to design and implement a generalisation of the Tempesti's loop using this environment. The outcome of the work is a generalisation that allows for automatized creation of rules and patterns for a given side pattern.
|
|
|
Automated Generation of Realistic Terrain Using Machine Learning Techniques
Střelský, Jakub ; Surynek, Pavel (advisor) ; Holan, Tomáš (referee)
Title: Automated Generation of Realistic Terrain Using Machine Learning Tech- niques Author: Jakub Střelský Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: RNDr. Pavel Surynek, Ph.D., Department of Theoretical Computer Science and Mathematical Logic Abstract: Artificial terrain is important component of computer games, simulati- ons and films. Manual terrain creation can be arduous process, hence automa- tization of this process would be convenient in many cases. Thanks to current advances in employing artifical neural networks on various generative tasks, the possibility of generating terrain using artificial neural networks should be investi- gated. We will focus on Generative Adversarial Networks as it is one of the most successful content generation method, and we will adjust this method to the task of artificial terrain generation. Resulting model is capable of generating realistic terrain based on raster sketch given by user and allows interactive modelling. Disadvantage of the model is it's requirement of a lot of training data. However, thanks to global elevation datasets providing us with more than enough training data, the model could be useful in certain applications. Keywords: procedural generation, terrain, neural networks, deep learning 1
|
|
|
Dynamic Constraint Satisfaction Problems
Surynek, Pavel ; Rudová, Hana (referee)
Constraint satisfaction problems (CSPs) are a type of combinatorial (optimization) problems that invite much interest in many practical applications. CSP is defined by a set of variables, to which values must be assigned, and a set of constraints that restrict these assignments. Since many problems of practical interest require a dynamic environment, the model of CSP was extended to a dynamic CSP (DCSP), in which the set of variables and/or constraints can be modified during the constraint resolution process. To simplify the constraint satisfaction problem for search algorithms, consistency (filtering) techniques like arc-consistency are usually applied. In this thesis, we study the problem of maintaining arc-consistency in DCSPs. We propose several new dynamic arc-consistency algorithms that yield a better compromise between time and space in comparison to similar existing algorithms like DNAC-4, DNAC-6 and AC|DC. The highlight of the work is a new algorithm that outperforms so far fastest algorithm for maintaining arc consistency in dynamic problems DNAC-6. In order to do performance experiments we have developed a library SPlan written in C++. This library solves DCSPs and the new algorithms as like as the comparable existing ones are implemented as a part of the library. Experimental results on randomly...
|
|
|
Software for Modeling Car Driving Properties
Malý, Ondřej ; Surynek, Pavel (advisor) ; Gregor, Petr (referee)
This work is intended for all interested in physical modelling, discrete computer simulations and motorism. Text part describes mathematical model of a car, description of forces and effects which occurs within car motion. Model is focused especially on the engine, trasferring the torque, braking and turning. Furthermore the thesis deals with electronic systems like ABS or ESP, which improves the steering control. The most important part of this work is a computer application for simulating and visualising the model. The program supports batch input and become a useful tool for experimenting with different settings of the car. Text part of the work includes screenshots taken during the tests and along with mathematical interpretation provides an insight into a physical principle of the car behaviour.
|
|
|
Algorithms for solving the Sokoban game
Galajda, Martin ; Surynek, Pavel (advisor) ; Petříček, Martin (referee)
The task of this work is to bring a complete guide for solving a SOKOBAN game problem. The work follow subsequently issues of studies of problem complexity, its definition, selection of appropriate algorithms, as well as their implementation and testing. The study demonstratethe manifest, that problem belongs to a NP-hard set of problems as well as PSPACE-complete set of problems. Fundamental and also advanced techniques of state space searching are studied as means for solving defined problem, memory and time characteristics of these techniques are presented and derived. In order to gain statistical information about efficiency of demonstrated algorithms and heuristics, an aplication SokobanSolver was built. This program can solve many SOKOBAN problems automatically. We described principles of functional parts and main data structures of this program and also we discuss program SokobanGenerator, aplication that was built to supply SokobanSolver with many random built SOKOBAN problems. Techniques explained are tested by lately named programs, and results are discussed at the very end of the paper.
|
|
|
Interpret and Debugging Environment for Prolog
Brunetto, Robert ; Hric, Jan (advisor) ; Surynek, Pavel (referee)
The main aim of this bachelor thesis is to implement interpreter of the language prolog with graphical debugger, which extends possibilities of classical text debugging, adds the ability to browse call stack easily, view the targets, which went through exit port and still have not been backtracked. This all displays and refreshes so the actual content of variables is always shown. Debugger and query run in separated threads, so the application always reacts. Query can be at any time stopped or suspended. Debugger is turned on when a query is suspended, so the call stack can be browsed. It is even possible to browse parts of call stack and exited goals while a query is running.
|
|
|
Vybrané problémy související s vehicle routing
Kuklis, Imrich ; Pergel, Martin (advisor) ; Surynek, Pavel (referee)
In our thesis we concentrate on a well-known problem which is popular among the scientists from the field of logistics, theoretical computer science and applied mathematics. This problem is called the Vehicle Routing Problem. We concentrate mainly on the Vehicle Routing Problem with Time Window. We implement some scheduling algorithms and compare their results. Powered by TCPDF (www.tcpdf.org)
|
|
|
Bitmap picture classification
Lukšová, Ivana ; Surynek, Pavel (advisor) ; Holan, Tomáš (referee)
In this work we propose a method of automatic content-based bitmap pictures classification into classes like buildings, landscapes, photographs etc. The method uses concepts of the machine learning, concretely the mechanism of a decision tree. We extract characteristics like the contrast, the distribution of colors, the presence of straight lines. On the basis of these characteristics the decision tree is built using the algorithm ID3. Creation of the program, which allows operations with the database of images based on the classification results - retrieval, sorting into directories etc. is also a part of the work. The method shows rate 75-85% correct within the classes.
|
guest ::
