Search

Problem ovog završnog rada je bio proširiti postojeću digitalnu igru s alatom za ispitivanje rješivosti razina i prikaz njihovih rješenja. U igri se osim igranja razina mogu uređivati i dodavati i nove s pomoću alata Level Editor. Cilj rada bio je dodati novi alat za provjeru rješivosti razina i prikaz tog rješenja. Do rješenja razina se dolazi pretraživanjem prostora stanja. Za pretraživanje prostora stanja postoje razni algoritmi. U ovom radu obrađeni su algoritam Depth-First Search (DFS) i njegova manja modifikacija. The topic of this thesis was to extend the existing digital game with a tool to examine the solvability of the levels and display their solutions. In the game, in addition to playing levels, one can also edit and add new levels by using the Level Editor tool. A new tool was added to check the solvability of levels and display this solution. The solution of the levels is reached by searching the state space. There are various algorithms for searching the state space. The Depth-First Search (DFS) algorithm and its minor modification are discussed.

U suparničkim igrama za više igrača važno je donositi ispravne odluke u stvarnom vremenu. U igri Zatacka, to se odnosi na odabir trajektorije koja osigurava najduže preživljavanje i ostvarivanje što boljeg konačnog rezultata. Algoritam pretraživanja korišten za planiranje je pretraživanje u dubinu s ograničenom dubinom. Algoritam na temelju početne pozicije agenta određuje moguće pozicije do kojih agent može doći u budućnosti. Na temelju ukupnog broja skretanja potrebnih za dolazak do svake buduće pozicije određuje se najsigurniji put kojim se agent treba kretati. Making the right decisions in real time is one of the most important things in adversarial multiplayer games. In the game called Zatacka, this refers to the selection of the trajectory that ensures the longest survival and the best possible final result. The search algorithm used for planning is Depth-first search with limited depth. Based on the initial position of the agent, the algorithm determines positions that the agent may reach in the future. Based on the total number of turns required to reach each future position, the safest route for the agent to move is determined.

U ovom radu, pod naslovom „Apstraktni tip podataka graf“ je definiran sami graf te su napravljene implementacije u programskim jezicima Python te C++. Preciznije, graf predstavlja vrstu podatkovne strukture putem koje se implementira matematički koncept grafa. Isti se uglavnom sastoji od konačnog (promjenjivog) skupa uređenih parova koji se zovu lukovi (bridovi) i od entiteta koji se zovu čvorovi. Naime, postoje dvije glavne vrste grafa, a to su usmjereni te neusmjereni. Oni se razlikuju po načinu na koji se crtaju, ali i po implementaciji. Osim toga, postoje i dvije vrste pretraživanja grafa, a to su pretraživanje u dubinu i u širinu. Također, opisani su još razni algoritmi te implementirani, a to su Primov, Kruskalov, Dijkstrin, Floyd- Warshall i Bellman- Ford algoritam. In this graduation thesis, the "Abstract data type graph" is defined graph itself and implemented in the programming languages of Python and C++. More precisely, the graph represents the type of data structure by which the mathematical concept of the graph is implemented. The same is mainly composed of the final (variable) set of arranged pairs called the arches (edges) and of the entities called the nodes. Namely, there are two main types of graphs that are directed and undirected. They differ in the way they are drawn but also by their implementation. In addition, there are also two types of graph lookups, which are search depth and breadth. Also various algorithms have been introduced, such as Prim's, Kruskal's, Dijkstra's, Floyd-Warshall and Bellman-Ford algorithm.

U ovom radu prezentirani su osnovni algoritmi pretraživanja grafa u širinu i dubinu, te kako se njihova struktura može iskoristiti za napredniji algoritam A* te algoritme testiranja 2-obojivosti grafa i topološkog sortiranja koji se koriste za mnoge učestale probleme u teoriji grafova. Definirani su osnovni pojmovi teorije grafova potrebni za razumijevanje danih algoritama. Dodatno, pokazana je implementacija algoritama u Javi te je objašnjeno kako koristiti isti programski kod za više algoritama. This paper presents basic graph search algorithms Breadth-First Search and Depth- First Search and how their structure can be used for more advanced algorithms such as A*, bipartiteness testing and topological search algorithm which are used for many graph theory problems. Basic graph theory definitions are given in order to understand the given algorithms. Additionally, the implementation of the algorithms is shown in Java and it is explained how to reuse programming code for multiple algorithms.

U moderno vrijeme, primjene teorije grafova su sveprisutne. Pojam grafa, osnovna klasifikacija grafova te reprezentacija grafa u memoriji, nužni su razumijevanje složenijih postupaka obilaska grafa i pronalaska najkraćeg puta, pronalaska povezanih komponenti i minimalnog razapinjućeg stabla. Pretraživanjem u širinu ili BFS algoritmom sustavno se pretražuju vrhovi jedne razine grafa prije prelaska na sljedeću razinu. Suprotno, pretraživanjem u dubinu ili DFS algoritmom obilaze se vrhovi najdublje razine, prije nego se backtrackingom algoritam vraća na pliće razine. U slučaju težinskog grafa, Dijkstrinim algoritmom pronalazi se put s najkraćom cijenom. Pretraživanje u širinu specijalan je slučaj Dijkstrinog algoritma, u kojem su težine bridova konstantne. Osnovna povezanost komponenti definirana nad neusmjerenim grafom, u slučaju usmjerenog grafa dijeli se na slabu i jaku povezanost. Svi oblici povezanosti rješivi su algoritmima BFS i DFS. Neovisan o njima, problem pronalaska minimalnog razapinjućeg stabla rješava se Kruskalovim algoritmom. Efikasno rješenje ostvaruje se specifičnom podatkovnom strukturom za upravljanje nepreklapajućim podskupovima inicijalnog skupa, tzv. strukturom Union-find. In modern times, applications of graph theory are omnipresent. Concept of graph, basic graph classification and the representation of the graph in the memory are necessary to understand the more complex procedures of traversing the graph and finding the shortest path, finding connected components and the minimum spanning tree. Breadth-first search or BFS systematically scans vertices of one level before going to the next level. On the contrary, depth-first search or DFS visits the vertices at the deepest level before the algorithm, using backtracking technique, returns to shallower levels. In the case of a weighted graph, Dijkstra's algorithm finds the path with the lowest cost. Breadth-first search is a special case of Dijkstra's algorithm, in which edge weights are constant. Basic definition of connectivity defined for an undirected graph, in case of a directed graph is divided into weak and strong connectivity. All forms of connectivity are solved by BFS or DFS. Regardless of them, the problem of finding the minimum spanning tree is solved by Kruskal's algorithm. An efficient solution is achieved through usage of the specific data structure for managing non-overlapping subsets of the initial set, so-called Union-find.

Značajan razvoj algoritma pretraživanja usmjerenog grafa nalazimo 50-ih godina prošlog stoljeća. E. W. Dijkstra konstruirao je algoritam na temelju kojeg su kasnije proizašle različite inačice i poopćeni oblici. Svima je zajedničko otkrivanje puta, koji ne mora uvijek biti optimalan. Zbog nedostatka memorije umjesto pretraživanja s jednolikom cijenom, tj. pretraživanja u širinu, možemo koristiti pretraživanje u dubinu. Isto tako, imamo mogućnost kombiniranja prednosti obje vrste algoritma te time dobivamo algoritam iterativnog pretraživanja u dubinu. Svakodnevno se susrećemo s problemom pretraživanja usmjerenog grafa, često ni ne razmišljajući o tome. Prilikom povezivanja na Internet, ili korištenja aplikacije koja sadrži digitalni zapis karte, Dijkstrin algoritam i njegovi oblici, poput algoritma pretraživanja s jednolikom cijenom, osiguravaju nam njihovo nesmetano korištenje. E. W. Dijkstra posvetio je gotovo cijeli svoj život razvoju računarstva i na tome smo mu zahvalni. Significant development of algorithms for finding the shortest paths between nodes in a graph has begun in 1950s. E. W. Dijkstra has conceived an algorithm, on which later on were based many others. All algorithms have in common discovering the path between two nodes, which sometimes is not the optimal one. Because of the lack of memory or computer resource, we prefer to use depth-first search instead of breadth-first search, in case of uniform transition costs. Furthermore, we can combine the benefits from each algorithm and therefore use iterative search in depth. Finding the shortest path is almost an everyday problem. For an example, it is used when we connect to the Internet or when we want to find directions on digital map. In these cases, uniform-cost search algorithm does all the work in the background. E. W. Dijkstra has dedicated his whole life to computer science and its development and we are very thankful for that.