Is BFS/DFS a Greedy Algorithm? What’s The Difference Between Greedy and Heuristic Algorithm?

Photo by Kevin Ku on Unsplash

Is BFS/DFS a Greedy Algorithm and Why?

Greedy algorithms supply an exact solution! Heuristic algorithms use probability and statistics in order to avoid running through all the possibilities and provide an “estimated best solution” (which means that if a better solution exists, it will be only slightly better).

A greedy algorithms follow locally optimal solution at each stage. While searching for the best solution, the best so far solution is only updated if the search finds a better solution. Whereas this is not always the case with heuristic algorithms (e.g. genetic, evolutionary, Tabu search, ant search, and so forth). Heuristic algorithms may update the best so far even if it’s worse than the best so far to avoid getting trapped in a local optimal solution.

Therefore, in nutshell BFS/DFS generally fall under greedy algorithms.

Breadth First Search vs Greedy Algorithm

BFS is not specifically for solving optimization problems, so it doesn’t make sense (i.e., it’s not even wrong) to say that BFS is a greedy algorithm unless you are applying it to an optimization problem. In that case, the statement is true or not depending on how it is applied.

The “reputable algorithm book” probably refers to BFS in the context of a specific optimization problem, and is probably correct to say that it is a greedy algorithm in that context… which you have omitted in your question.

Greedy Algorithms

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

For example, a greedy strategy for the travelling salesman problem (which is of high computational complexity) is the following heuristic: “At each step of the journey, visit the nearest unvisited city.” This heuristic does not intend to find the best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps. In mathematical optimization, greedy algorithms optimally solve combinatorial problems having the properties of matroids and give constant-factor approximations to optimization problems with the submodular structure.

Heuristic Algorithms

Traveling Salesmen Problem

Figure 1: Example of how the nearest neighbor algorithm functions.

These are the steps of the NN algorithm:

  1. Start at a random vertex
  2. Determine the shortest distance connecting the current vertex and an unvisited vertex V
  3. Make the current vertex the unvisited vertex V
  4. Make V visited
  5. Record the distance traveled
  6. Terminate if no other unvisited vertices remain
  7. Repeat step 2.5

This algorithm is heuristic in that it does not take into account the possibility of better steps being excluded due to the selection process. For n cities, the NN algorithm creates a path that is approximately 25% longer than the most optimal solution.

What’s the difference between greedy and heuristic algorithm?

their main characteristic is to choose the best (local) option at each iteration

Not at all true for heuristics. Heuristic algorithms are making choices that are know to be suboptimal in theory, but have been proved in practice to produce reasonable results. Heuristics usually find an approximate solution:

In computer science, artificial intelligence, and mathematical optimization, a heuristic is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution. This is achieved by trading optimality, completeness, accuracy, or precision for speed.

Greedy is an example of heuristic (make the best local choice and hope for the optimal global result), but that does not mean heuristics are greedy. There are many heuristics completely unrelated to greedy, eg. genetic algorithms are considered heuristic:

In the computer science field of artificial intelligence, a genetic algorithm (GA) is a search heuristic that mimics the process of natural selection.

Wrapping up…

  • Are all Heuristics, Greedy Algorithms — No
  • Are all Greedy Algorithms, Heuristics — In general, yes.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store