Heuristics for Problem Solving (OCR A Level Computer Science)

Heuristics for Problem Solving

What are Heuristics?

• 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 (known as 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