Heuristic algorithm

In computer science, a heuristic algorithm or simply a heuristic is an algorithm that ignores whether the solution to the problem can be proven to be correct, but which usually produces a good solution or solves a simpler problem that contains or intersects with the solution of the more complex problem. Heuristics are typically used when there is no known way to find an optimal solution, or when it is desirable to give up finding the optimal solution for an improvement in run time.

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 essentially no way to do it without 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.

Many commercial anti-virus scanners use heuristic signatures to look for specific attributes and characteristics for detecting viruses and other forms of malware.Fact|date=April 2008

Judea Pearl states that heuristic methods are based upon intelligent search strategies for computer problem solving, using several alternative approaches [cite book
first=Judea
last=Pearl
authorlink=Judea Pearl
publisher=Addison-Wesley Pub
date=April 1984
title=Heuristics
isbn=0201055945] .

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.

In Arthur C. Clarke's "Space Odyssey" saga, the HAL 9000 computer is named after "Heuristic Algorithmic".

ee also

*Heuristic function
*Artificial Intelligence
*Expert System
*Logic Programming

References

* S. E. Goodman, S. T. Hedetniemi, "Introduction to the Design and Analysis of Algorithms", McGraw-Hill, 1977.
* Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, "Data Structures and Algorithms", Addison-Wesley.