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's no known way to find an optimal solution, or when it's 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.[citation needed]
Judea Pearl states that heuristic methods are based upon intelligent search strategies for computer problem solving, using several alternative approaches[1].
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".
See also
Here is a sample story for Heuristic and application in artificial intelligence.
Consider a chess board, with 8x8 black & white squares, so at whole 64 squares. Consider removing from that board the 2 extremes squares of the big black diagonal.
The remaining chess board does now contains 62 squares. Consider you have 31 dominos, each one of the size of two square(dominos are rectangular and equal to 2 adjacent squares).
The question is: Is it possible to put the 31 dominos on the mutilated chess board in order to hide all the 62 squares?
Each domino is two square surface so the global surface of the 31 dominos is effectively 62 but we don't know if there is a matching position on the board. It may succeed as it may fail.
There can be at least two approach for this problem: the brute force(say combinatory) solution which is to try all the position, to finally find it will fail... the heuristic one, which is to say that a domino always maps a white and a black squares, but we removed to black squares, so there are two white squares exceeding, so it is not possible.
The heuristic uses another problem solving scheme to map the original problem with a valuable solution.
References
- ^ Pearl, Judea (April 1984). Heuristics. Addison-Wesley Pub. ISBN 0201055945.
- 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.