Heuristics for Problem Solving
What are heuristics?
- In A Level Computer Science, heuristics is making use of experience to find a solution to a problem quickly
- It uses concepts like ‘rules of thumb’ and ‘educated guesses’ to find a solution faster than traditional methods
- It prioritises speed and not accuracy
- It aims to find a solution that is ‘good enough’ rather than perfect
Trade-off between speed and accuracy
A game is called ‘Hot and Cold’ and the rules are as follows:
- A person (the searcher) tries to locate a hidden object by listening to clues from another person, who can only say “hotter” or “colder” based on the seeker’s proximity to the hidden object
- “Hotter” or “colder” clues are indicators of where the object is, but they don’t give an exact location
Thinking about the use of heuristics in this game:
- If the searcher misinterprets the clues, they may get stuck in a spot that seems “hot” but is not the actual target
- This predicament also happens in heuristic algorithms and is known as getting stuck in a local optimum
- The searcher responds to feedback and gains more intelligence to find the object, usually resulting in them finding the object
- The method finds the object more quickly than random searching, but it doesn’t guarantee the quickest or most direct route will be taken
- This is the same for heuristic methods, where there is a trade-off between speed and accuracy
Heuristic methods in software
- The A* algorithm is a common example that uses heuristics in pathfinding and graph traversal
- The aim of the A* algorithm is to use heuristics to find a path from a start node to an end node quickly, however, the path that it finds may not always be the most efficient path possible
- Learn more about A* Algorithm
| Benefits | Drawbacks |
|---|---|
| Heuristics can usually find a solution close to the best solution available. | It will not guarantee that you will find the ‘best’ solution as it aims to find a solution quickly that is ‘good enough.‘ |
| Heuristics save time as you may not to investigate every single possibility to get a definite answer. | There needs to be careful consideration to be made between accuracy and time. |
| Heuristics is very practical and can be easily implemented. | The heuristic values may be incorrect which can lead to inaccurate solutions being found. |