In computer science, a heuristic algorithm, or simply a heuristic, is an algorithm that is able to produce an acceptable solution to a problem in many practical scenarios, in the fashion of a general heuristic, but for which there is no formal proof of its correctness.  Alternatively, it may be correct, but may not be proven to produce an optimal solution, or to use reasonable resources.  Heuristics are typically used when there is no known method to find an optimal solution, under the given constraints (of time, space etc.) or at all.

Two fundamental goals in computer science are finding algorithms with provably good run times and with provably good or optimal solution quality.  A heuristic is an algorithm that abandons one or both of these goals; for example, it usually finds pretty good solutions, but there is no proof the solutions could not get arbitrarily bad; or it usually runs reasonably quickly, but there is no argument that this will always be the case.

For instance, say you are packing odd-shaped items into a box.  Finding a perfect solution is a hard problem: there is no known way to do it that is significantly faster than trying every possible way of packing them.  What most people do, then, is “put the largest items in first, then fit the smaller items into the spaces left around them.”  This will not necessarily be perfect packing, but it will usually give a packing that is pretty good.  It is an example of a heuristic solution.

Several heuristic methods are used by antivirus software to detect viruses and other malware.

Judea Pearl states that heuristic methods are based upon intelligent search strategies for computer problem solving, using several alternative approaches.

Often, one can find specially crafted problem instances where the heuristic will in fact produce very bad results or run very slowly; however, such pathological instances might never occur in practice because of their special structure.  Therefore, the use of heuristics is very common in real world implementations. For many practical problems, a heuristic algorithm may be the only way to get good solutions in a reasonable amount of time.  There is a class of general heuristic strategies called metaheuristics, which often use randomized search for example. They can be applied to a wide range of problems, but good performance is never guaranteed.

I found this to be an interesting concept.  We don’t know the optimal method to solving K4 but we can develop heuristic algorithms that may not be perfect but are pretty good ideas.  That and it’s just interesting to think of an aspect of programming/algorithms that allows variability and chance into the output while still maintaining quality results or speedy results.

–Kryptosfan