Matija Horvat

Python Backtracking

You can check out the slides here (direct PDF link): What is Backtracking? Backtracking is a general approach, i.e. a variant of a depth-first search algorithm, suited for solving constraint satisfaction problems. ???? Idea: Backtracking incrementally validates candidates, tests the solutions, and backtracks from a candidate value if it determines that the final solution is […]

Python Jump Search First Algorithm

As you watch the video, you can have a look at the slides as PDF: download slides in a new tab here. What is the Jump Point Search Algorithm? The jump point search algorithm — or shorter JPS — is a variant of the A* search algorithm, optimized for pathfinding on grid maps, i.e., in

Python A* Search Algorithm

This tutorial guides you into the fascinating A* (A-Star) using the Python programming language. First, feel free to watch the video guide—we’ll give a detailed textual explanation below. The slides can be found as a Gif here: Okay, so let’s dive into the algorithm motivation, explanation, and Python code next! What is the A* Search

Python Dijkstra Algorithm

You can download the PDF file of the presentation here. Also, watch the presentation as a Gif here: What is Dijkstra’s Algorithm? Dijkstra’s algorithm solves the single-source shortest path (SSSP) problem. Generally, it enables finding the shortest route between two vertices in a graph. Its author is dr. Edsger W. Dijkstra, a pioneering contributor to

Python Best-First Search (BFS) Algorithm

You can watch the slides as a GIF here: And download the slides as PDF here. What’s the Best-First Search Algorithm? After several articles on uninformed search algorithms, we continue our journey to informed search algorithms. The first one in the series is the Best-First search algorithm. In general, informed search algorithms use some kind

Python Iterative Deepening Depth-First Search (DFS) Algorithm

What is an Iterative Deepening Depth-First Search Algorithm? Continuing our story even further, after introducing graphs and basic graph traversal algorithms, we will refine the Depth-First Search Algorithm by introducing the iterative depth limitation. An iterative deepening depth-search algorithm also traverses a graph by exploring it vertex-by-vertex, but it does it by following the vertical

Python Depth First Search (DFS) Algorithm

What is a Depth-First Search (DFS) Algorithm? Building on our previous story about graphs and graph traversal algorithms, this time we will look into a depth-first search algorithm. A depth-search algorithm also traverses a graph by exploring it vertex-by-vertex, but it does it by following the vertical order of the vertices. Although the depth-first search