Heuristic algorithm


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.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • heuristic algorithm — euristinis algoritmas statusas T sritis informatika apibrėžtis ↑Algoritmas paieškų variantų skaičiui mažinti siekiant sprendinio arba išvados, būdingos dirbtiniam intelektui. atitikmenys: angl. heuristic algorithm ryšiai: dar žiūrėk – algoritmas …   Enciklopedinis kompiuterijos žodynas

  • heuristic algorithm — algorithm that is based on empirical theory, algorithm that gives an effective solution for specific types of input …   English contemporary dictionary

  • Heuristic — (hyu̇ ˈris tik) is a method to help solve a problem, commonly an informal method. It is particularly used to rapidly come to a solution that is reasonably close to the best possible answer, or optimal solution . Heuristics are rules of thumb ,… …   Wikipedia

  • Heuristic function — A heuristic function or simply a heuristic is a function that ranks alternatives in various search algorithms at each branching step basing on an available information in order to make a decision which branch is to be followed during a… …   Wikipedia

  • Heuristic (disambiguation) — A heuristic is a method for helping in solving of a problem, commonly informal. The term may also have the following technical meanings.*Heuristic algorithm *Heuristic evaluation is an expert based usability evaluation method. *Heuristic function …   Wikipedia

  • Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

  • heuristic — A process, such as trial and error, for solving a problem for which no algorithm exists. A heuristic for a problem is a rule or method for approaching a solution …   Philosophy dictionary

  • heuristic program — program that is based on an algorithm that gives an effective solution for specific types of input …   English contemporary dictionary

  • heuristic — /hjuˈrɪstɪk / (say hyooh ristik) adjective 1. serving to find out; furthering investigation. 2. (of a teaching method) encouraging students to discover for themselves. 3. Mathematics (of a method of solving problems) one for which no algorithm… …   Australian English dictionary

  • Christofides algorithm — The goal of the Christofides heuristic algorithm (named after Nicos Christofides) is to find a solution to the instances of the traveling salesman problem where the edge weights satisfy the triangle inequality. Let G = (V,w) be an instance of TSP …   Wikipedia