Algorithms For Dummies

Considering the goals of heuristics

Heuristics can speed the long, exhaustive searches performed by other solutions, 

especially with NP-hard problems that require an exponential number of attempts 

based on the number of their inputs. For example, consider the traveling salesman 

problem or variants of the SAT problem, such as the MAX-3SAT (both problems 

appear in Chapter 18). Heuristics determine the search direction using an estima-

tion, which eliminates a large number of the combinations it would have to test 

otherwise.

Because a heuristic is an estimate or a guess, it can lead the algorithm that relies 

on it to a wrong conclusion, which could be an inexact solution or just a subopti-

mal solution, which is a solution that works but is far from being the best possible. 

For example, in a numerical estimation, a heuristic might answer that the solu-

tion is 41 instead of 42. Other problems often associated with heuristics are the 

impossibility of finding all best solutions and the variability of time and computa-

tions required to reach a solution.

A heuristic provides a perfect match when working with algorithms that would 

otherwise incur a higher cost when running using other algorithmic techniques. 

For instance, you can’t solve certain problems without heuristics because of the 

poor quality and overwhelming number of data inputs. The traveling salesman 

problem (TSP) is one of these: If you have to tour a large number of cities, you 

cannot use any exact method. TSP and other problems exclude any exact solution. 

AI  applications  fall  into  this  category  because  many  AI  problems,  such  as 

---

CHAPTER 20