Member-only story
Greedy Algorithm in Python
Using the Greedy Algorithm to find a solution to a graph-modeled problem
Hi everyone, one of my first articles in medium talked about Search Algorithms. These algorithms are applied in graphs, which model a given problem, creating the search space of the problem. They search in the search space (graph) to find the best or at least a quite efficient solution. Particularly, we have implemented the Breadth-First Search (BFS) and the Depth First Search (DFS) to solve the maze problem and a sudoku puzzle respectively. Today we are going to talk about the Greedy algorithm. More specifically, we will talk about the following topics:
1. Introduction
2. Pseudocode
3. Pen and Paper Example
4. Python implementation
5. Example
6. ConclusionWe have a lot of stuff to cover, so let’s get started.
Introduction
Search Algorithms are used to find a solution to a given problem, that can be modeled as a Graph. If you want to learn more about graphs, please read the related article. Every node in the graph represents a state of the problem and each edge between two nodes represents a valid action that drives us from one state (node) to the other. Each Search Algorithm starts from a node (initial state — node) searching the final state node that represents a solution for the given problem. Search Algorithms are divided into two main categories. The first category contains the so-called “blind” algorithms, that don’t take into account the cost between the nodes. Breadth-First Search and Depth First Search algorithms we talked about in previous articles are in this category. The algorithms in the second category execute the heuristic search. The Greedy algorithm belongs to the latter category.
Heuristic search methods try to find the optimal solution in a reasonable time for a given problem. In contrast to “blind” search methods and algorithms that use brute force to find a solution, the heuristic algorithms use information about the distance between nodes…
