Heuristics

Heuristics: the “kinda, sorta, maybe” of computing

Until now, problem solving with computers has been discussed in terms of algorithms. Algorithms are guaranteed to give a “correct” answer if the proper, specific steps are followed using sequence, selection, and repetition. However, what about problems that we do not know how to solve? Problems that no known algorithm can sufficiently address? What about problems that can be solved, but would take too much time or resources?

Although there are some problems that cannot be solved efficiently through computation (or in some cases solved at all), often a method for deriving an approximate solution may be defined through the use of heuristics. Heuristics are a problem solver’s “Rules of Thumb”; they serve as general guidelines meant to encourage progress toward a good answer, but with no guarantee of actually generating “the correct answer”.

A Heuristic Approach: Hill Climbing

“Sometimes, ‘good enough’ is good enough.”

Mathematician George Pólya’s second principle of problem solving asks a potential problem solver to devise a plan, perhaps by examining known problems and solutions that may be related. Computer scientists are continually building a cookbook of these related problems and applying them to a broadening scope of more complex situations. Let’s focus on a very basic recipe in our cookbook that is applied often to emergent computational problems—an example heuristic called hill climbing.

Imagine that you have created autonomous robots that are programmed to dig for gold. You can set a number of these robots down in a location, and they will explore the terrain and scan for signs of precious metals. In the past, your company has lost many of these robots to rain. Although the rain itself is not harmful to them, the flooding that often occurs as a result leaves them completely submerged for long periods of time.

You are tasked with writing an emergency routine to—quite literally—climb hills. Here’s the catch: your robots will be deployed in many different locations, and it is impossible to know where all of the hills and highest locations actually are in any situation. All that the robot is able to sense is when it is raining, and it current position, including its altitude.

We can’t use an algorithm to find the safest spot and park there, because given our constraints, that would mean visiting and searching every possible location in the area to locate the highest point, and then traveling back to it. The time it would take to perform this is intractable; the robots would have their circuits flooded long before they could accomplish their goal.

Let’s apply an heuristic. The hill climbing heuristic suggests that you will probably reach a high point (a local maximum)—not necessarily the highest point (the global maximum)—if you search your immediate vicinity, choose the highest point available, and relocate there. Repeating this process is likely to get you to a local maximum.