“A heuristic technique, often called simply a heuristic, is any approach to problem solving, learning, or discovery that employs a practical method not guaranteed to be optimal or perfect, but sufficient for the immediate goals. Where finding an optimal solution is impossible or impractical, heuristic methods can be used to speed up the process of finding a satisfactory solution. Heuristics can be mental shortcuts that ease the cognitive load of making a decision. Examples of this method include using a rule of thumb, an educated guess, an intuitive judgement, guesstimate, stereotyping, profiling, or common sense.” (Source: Wikipedia)
“In computer science, 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. In a way, it can be considered a shortcut.” (Source: Wikipedia)
The objective of a heuristic algorithm is to apply a rule of thumb approach to produce a solution in a reasonable time frame that is good enough for solving the problem at hand. There is no guarantee that the solution found will be the most accurate or optimal solution for the given problem. We often refer the solution as “good enough” in most cases.
Heuristic Algorithms?
Heuristic Algorithms can be found in:
Artificial Intelligence
E.g. When a computer algorithm plays a
game of Chess (e.g. Deep Blue) or a
game of Go (e.g. AlphaGo), the computer cannot investigate every single move that can be played. Instead it will apply a few
rules of thumb to quickly discard some moves while focusing on key moves that are more likely to lead to a victory.
Language recognition
When analysing the meaning of a user input, for instance when a user asks a question on a search engine or interacts with a Google Home or Amazon Echo device, an algorithm tries to make sense of the user inputs. Word associations, analysis of context, previous searches history and current trends/search engine statistics can be used in a heuristic algorithm to speed up the search process.
Big Data Analysis
When there are large amounts of data to analyse. This is the case for search engines to return search results very efficiently, profiling algorithms which can be used by a marketing department to identify members of a target audience and their behaviours, data analysis in scientific research (e.g. medicine to identify cause/effect correlations between large data sets).
Shortest Path Algorithms
used by GPS systems and self-driving cars also use a heuristic approach to decide on the best route to go from A to Z (e.g. A* Search Algorithm). More advanced algorithms can also take into consideration a range of factors including the type of roads, the speed limits, live traffic data, etc. which can result in extremely complex algorithms.
Machine Learning
Artificial Intelligence algorithms based on machine learning where the computer builds up a knowledge base from previous experiences is another application of heuristic algorithms. In this case the algorithm uses a self-maintained knowledge base to inform decisions and make “educated guesses” based on previous experiences.
Let’s investigate a few basic examples where a heuristic algorithm can be used:
Noughts & CrossesGame of ChessTop TrumpsLanguage RecognitionShortest Path Algorithms
To help the computer make a decision as to where to place a token on a 3×3 noughts and crosses grid, a basic heuristic algorithm should be based on the rule of thumb that some cells of the grid are more likely to lead to a win:
Based on this approach, can you think of how a similar approach could be used for an algorithm to play:
- Othello (a.k.a. Reversi Game)
- A Battleship game?
- Rock/Paper/Scissors?
When playing a game of chess, expert players can “see” several moves ahead. It would be tempting to design an algorithm that could investigate every single possible move that players can make and investigate the impacts of such moves on the outcome of the game. However such an algorithm would have to investigate far too many possible moves and would quickly become too slow and too demanding in terms of memory resources in order to perform effectively.
It is hence essential to use a heuristic approach to quickly discard some moves which would most likely lead to a defeat while focusing on moves that would seem to be a good step towards a win!
Let’s consider the above scenario when investigating all the possible moves for this white pawn. Can the computer make a quick decision as to what would most likely be the best option?
Heuristic approaches do not always give you the best solution. Can you explain how this could be the case with this scenario?
Sometimes your algorithm need to collect or analyse data before applying heuristic to make a decision. This can be done by providing the computer with some data or by implementing an algorithm based on
machine learning.
For instance in a game of Top Trumps, if your algorithm knows the average value of each card for each category, it will be able to select the criteria which is most likely going to win the round.
Alternatively, a machine learning algorithm could play the game and record and update statistics after playing each card to progressively learn which criteria is more likely to win the round for each card in the deck.
You can investigate how machine learning can be used in a game of Top Trumps by reading this blog post.
Heuristic methods can be used when developing algorithms which try to understand what the user is saying, or asking for. For instance, by looking for words associations, an algorithm can narrow down the meaning of words especially when a word can have two different meanings:
e.g. When using Google search a user types: “Raspeberry Pi Hardware” We can deduct that in this case Raspberry has nothing to do with the piece of fruit, so there is no need to give results on healthy eating, cooking recipes or grocery stores…
However if the user searches for “Raspeberry Pie ingredients”, we can deduct that the user is searching for a recipe and is less likely to be interested in programming blogs or computer hardware online shops.
Short Path Algorithms used by GPS systems and self-driving cars also use a heuristic approach to decide on the best route to go from A to Z. This is for instance the case for the A* Search algorithm which takes into consideration the distance as the crow flies between two nodes to decide which paths to explore first and hence more effectively find the shortest path between two nodes.
You can compare two different algorithms used to find the shortest route from two nodes of a graph:
LMC Simulator
Flowchart Studio
Python Syntax