Heuristics (Math Lair)

Math Lair Home > Topics > Heuristics

Heuristics can be defined as the study or practice of the methods and rules of learning, discovery, and problem solving. The word heuristics can also be used to describe these methods and rules. A good reference on heuristics is George Polya's classic book How to Solve It.

There are several differences between heuristics and algorithms that are worth mentioning:

Heuristics are generalized, able to deal with a wide range of problems, while algorithms typically deal with a specific type of problem.
There's no guarantee that a given heuristic will necessarily point the way to a solution.
Algorithms are more formal than heuristics. Heuristics can encompass rules of thumb, hunches, intuitive judgements, common sense, and techniques of that nature. As such, heuristic methods sometimes fall short of rigourous mathematical proof, but often point the way to obtaining such a proof.

For well-defined, straightforward problems such as those commonly found in mathematics textbooks, the method of solving the problem is obvious, and all that is required is to directly apply the theorems, formulae, and algorithms that you already know to solve the problem. However, other problems, both in everyday life and in advanced mathematical inquiry, are not always well-defined, and having a knowledge of what methods may be useful in solving them can be helpful.

Common Heuristics

Here is a list of several common heuristics used in solving mathematical problems. This list is by no means complete.

Assume the Opposite

If you're trying to prove something, you could assume the opposite of what you're trying to prove and show that it has to be false. If the opposite assumption to what you want to prove is false, then, by the law of excluded middle, the assumption that you want to prove must be true. This approach is used in three related methods of proof:

Reductio ad absurdum involves assuming the opposite of what you want to prove, and showing that that assumption leads to a contradiction or other absurdity.
Indirect proof involves showing that the assumption opposite to that which you want to prove is false.
Infinite descent involves showing that, if a solution exists, that implies that a smaller solution exists, which implies that an even smaller one exists, and so on and so on. However, if the solution space is the natural numbers or some other set with a smallest element, then it isn't possible to have an infinite number of ever-smaller solutions; therefore, no solutions can exist.

Backtracking

In backtracking you make an assumption about the solution and see what follows from that assumption. If it seems to work out, make another assumption and so on until you've solved the problem. If it doesn't work (e.g. it results in a contradiction), backtrack to a previous choice point and try another assumption. If you've ever worked on a Sudoku puzzle, you've likely used backtracking.

Break the Problem Up

Find a way to solve part of the problem. Then, look at the rest of the problem as a sub-problem and solve it, breaking it up in turn as required.

Consider Another Problem

This method involves considering a problem into a problem that is either logically equivalent to (but usually simpler than) the original problem, a (usually simpler) variant of the problem for which the answer can lead to an answer for the original problem, or some other related problem that may be helpful.

Create a Diagram, Graph, Table, Model, or Equation

Often, a problem is stated in an unhelpful way. How to proceed may become clear if you represent the data in the form of a diagram, graph, table of values, model, or equation.

Guess and Check (also known as Trial and Error, Generate and Test, and other names)

Generate possible solutions and then determine whether they meet the solution criteria. While it's often discouraged by teachers (it can, after all, be excessively time-consuming), it's as valid a method of reaching a solution as any other.

Inductive Reasoning

If you're given a bunch of data that may be related, it may help to reason inductively to seek a pattern that ties the data together. Once you've found a pattern, you can use regular mathematical methods of proof to confirm it.

Mathematical Induction

The method of mathematical induction can be useful in proofs.

Reasoning by Analogy

Given a previously solved problem, use that problem to determine an analogous solution to the current problem. Related to "Consider Another Problem", above.

Restate the Problem

It can be helpful to restate the problem in another way. You could turn an algebraic problem into a geometrical problem or vice versa, or you could turn a problem into a logically equivalent problem.

Work Backwards

If you know what the goal or solution is, you can analyze the last step needed to achieve the goal, then the next-to-last step and so on until you get to the initial state. When you were young, you may have used this approach to solve mazes. As well, I find myself using this method for a real-life problem as I'm writing this. Tomorrow morning I have an appointment for 9:00 am. For what time should I set my alarm clock? Well, if I know that I need to be at the appointment at 9, that means that I have to be in the car at 8:50, which means that I need to take the dog for a walk at 8:20, which means that... and so on until I've worked backwards to what time I need to get up.

Generalize

Sometimes a problem can be easier to understand when it is generalized. Abstracting can provide a broader perspective and suggest other techniques.