1. Introduction
In this tutorial, we’ll discuss heuristics and algorithms, which are computer science concepts used in problem-solving, learning, and decision making. First, we’ll give a detailed definition of each of the terms. Then we’ll look at some examples. Finally, we’ll highlight the major differences between them.
2. What Is a Heuristic?
Heuristics usually refers to a technique for problem-solving. They’re used when classical approaches are time consuming, as well as when an appropriate solution can’t be found with a classical approach. In other words, they allow us to quickly obtain an appropriate solution to a problem through exploration, intuition, and sometimes an educated guess.
As such, heuristics begin by exploring possible solutions to a problem. The first step is to search the solution space to find an area in which the solution might be located. Then the search for a solution is focused on this area.
The goal here is to obtain an acceptable solution to a problem in a timely manner. As a result, the solution obtained isn’t necessarily the best or most precise solution. This is known as a trade-off between precision and speed.
In addition to the precision-speed trade-off, there are other points to consider, such as:
- completeness – are all the possible solutions found?
- optimality – is the solution the best solution?
Furthermore, heuristics can’t be mathematically proven because the methodology used to solve problems is often based on intuition and explorations. Consequently, they can’t be replicated by other users, and won’t always yield the same results.
3. Applications of Heuristics
Heuristics are attractive because they find solutions in a timely manner. Therefore, they’re suitable for use in optimization problems and algorithms. To better understand this, let’s discuss some examples:
3.1. Traveling Salesperson Problem
The Traveling Salesperson Problem (TSP) is an optimization problem in which the objective is to find an optimal route between a set of nodes. The question is, given a set of cities (nodes) and distances between these cities, what is the shortest possible route that visits each city:
The TSP problem is difficult to solve and is often classified as NP-hard. In other words, it’s complex and hard to verify. However, heuristics help us here to approximate an optimal route to all the cities.
3.2. Greedy Algorithms
Greedy algorithms attempt to find locally optimal solutions at each stage in solving a problem. To clarify, the assumption is that a set of locally optimal solutions may eventually lead to a globally optimal solution in the end. Hence, they’re often applied to the TSP problem we just discussed.
3.3. Antivirus Software
When scanning for viruses, heuristics are used to search for samples of code that resemble viruses in files. This significantly reduces the number of files that have to be searched for viruses.
Some additional applications of heuristics include searching, simulated annealing, and hill-climbing.
4. What Is an Algorithm?
In contrast, an algorithm is a precise set of rules or procedures for solving a problem or completing a specific task. Algorithms don’t depend on intuition or guesses, but rather provide instructions to obtain a solution. Therefore, algorithms guarantee that the given set of rules will ultimately lead us to the correct answer.
An algorithm will usually consist of a sequence of steps with a starting point and a known endpoint. For instance, consider an algorithm to add three numbers. First, we’ll start by applying the addition operator on the three numbers. As a result, we’ll obtain a value that is a sum of all three numbers:
Algorithms are usually represented in one of three ways: programming language, pseudocode, or flowcharts. Furthermore, they can be proven mathematically to show how they generate an answer. Due to this characteristic, most algorithms can be replicated by other users.
5. Applications of Algorithms
Algorithms are precise, and this makes them suitable for use in various areas of computer science. They’re used to produce outputs from a given set of inputs. Let’s review some of these applications.
5.1. Search
Search algorithms are used to retrieve data elements, usually from data structures or within a search space. It’s important to note that they differ in the approach used for searching. For instance, a linear search scans each element at a time, whereas a binary search splits the search range in half and starts with the middle value.
5.2. Sorting
Sorting algorithms are used to order or arrange elements. For example, elements can be arranged in ascending or descending order. Specifically, given an unsorted list of elements as input, a sorting algorithm will arrange the elements and return a sorted list according to the specified order. Some examples include quicksort, selection sort, and heapsort.
5.3. Cryptography
In cryptography, algorithms are used for authentication, encryption, and decryption of messages. They prevent unauthorized access to data and resources. Some examples of these are symmetric and asymmetric key algorithms.
5.4. Artificial Intelligence
In artificial intelligence, algorithms are used to train computer programs, as well as to teach machines how to learn and function on their own. Some classes of algorithms for artificial intelligence are supervised, unsupervised, and reinforcement learning algorithms.
6. Understanding the Difference Between Heuristics and Algorithms?
It’s important to note that a heuristic can also be an algorithm in the sense that it describes how to solve a problem. However, the major differences can be summed up as follows:
Heuristic
Algorithm
It’s based on intuition, guesses, or explorations
It’s based on a finite set of instructions
Will usually yield a sub-optimal result; however, optimal results are possible
Guaranteed to yield an optimal result
Cannot be proven mathematically; however, this isn’t always the case
Can be mathematically proven
Won’t yield the same answer every time, thus not reproducible
Will always yield the same answer, thus they’re reproducible
7. Conclusions
In this article, we discussed heuristics and algorithms. We explored how they work, and listed examples of where they’re used. Finally, we highlighted the major differences between the two concepts.