Memoization

Memoization (or memoisation, in the UK) is a technique used in computer science and artificial intelligence that allows algorithms to search more efficiently by effectively remembering the solution to subproblems within the search, thereby avoiding repeat calculations.

The key to memoization is the effective use of subproblems within a task. Take for instance the task of determining the shortest route from Edinburgh to Rome. A typical brute force search will attempt to follow every path (within reason) from Edinburgh that ends up in Rome. One example might be a flight that goes from Edinburgh to London to Paris to Rome. If the algorithm were to then consider a second path, from Edinburgh to Amsterdam to Paris to Rome, it would have to recalculate the distance from Paris to Rome. This in effect is a "subproblem". In order to make this searching more efficient, we could simply store the distance from Paris to Rome and then recall it should we come across it later. This can be repeated for the other various subproblems in the task, avoiding unnecessary work.

Another example might be a task where you have to find a path from A to X, with the relations described below.

   B--------C
  /|
 / |
A--D
 \
  \E----F--J--------------X
   |       |
   G       |
    \      |
     H-----I

Now for this task, we simply need to find any route from A to X. We don't need to care about the shortest path; any route will do. Now within this search, perhaps the algorithm takes the path A-B-C and discovers that it is a dead end. It would be useful to store this information so if it starts down the path A-D-B..., it will know that B leads to C and is a bad route. Rather than following it all the way out to its conclusion, (which may be a much longer route than depicted here) the algorithm could stop as soon as it recognized the path.

Additionally, if we discover that E-F-J leads to X, we don't have to try the route E-G-H-I-J because we already have a sucessful path.

Memoization is a powerful tool that can be used in any task that involves subproblems, and simply consists of the retrieval rather than the recalculation of already encountered data. Non-search examples of where this method can be useful: Tower of Hanoi, Fibonacci Numbers, Date Sorting, and many more. This is especially useful when performing recursive tasks that may blindly recalculate the same sequence many times over.