All Topics  
Heuristic (computer science)

 

 
   Email Print
   Bookmark   Link
 

 

Heuristic (computer science)
 
 
  Topics Heuristic (computer science) Topic Home

In computer science
Computer science

Computer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems....
, a heuristic algorithm, or simply a heuristic
Heuristic

Heuristic is an adjective for methods that help in problem solving, in turn leading to learning and discovery. These methods in most cases employ experimentation and trial-and-error techniques....
, is an algorithm
Algorithm

In mathematics, computing, linguistics and related subjects, an algorithm is a sequence of finite instructions, often used for calculation and data processing....
 that is able to produce an acceptable solution to a problem in many practical scenarios, 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
Computational complexity theory

Computational complexity theory, as a branch of the theory of computation in computer science, investigates the problems related to the Computational resource required for the execution of algorithms , and the inherent difficulty in providing efficient algorithms for specific computational problems....
 etc.) or at all.

Two fundamental goals in computer science are finding algorithm
Algorithm

In mathematics, computing, linguistics and related subjects, an algorithm is a sequence of finite instructions, often used for calculation and data processing....
s with provably
Mathematical proof

In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive reasoning or empirical arguments....
  good run time
Run time

Run time or runtime may refer to:*Run time, the length of a film or television program in minutes, usually with end credits included*Runtime, in computer science, the duration of a computer program's execution, from beginning to termination...
s and with provably good or optimal
Optimization (computer science)

In computing, optimization is the process of modifying a system to make some aspect of it work more efficiently or use fewer resources. For instance, a computer program may be optimized so that it executes more rapidly, or is capable of operating with less Computer data storage or other resources, or draw less power....
 solution
Solution

In chemistry, a solution is a homogeneous mixture composed of two or more substances. In such a mixture, a solute is dissolved in another substance, known as a solvent....
 quality.






Discussion
Ask a question about 'Heuristic (computer science)'
Start a new discussion about 'Heuristic (computer science)'
Answer questions from other users
Full Discussion Forum



Encyclopedia


In computer science
Computer science

Computer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems....
, a heuristic algorithm, or simply a heuristic
Heuristic

Heuristic is an adjective for methods that help in problem solving, in turn leading to learning and discovery. These methods in most cases employ experimentation and trial-and-error techniques....
, is an algorithm
Algorithm

In mathematics, computing, linguistics and related subjects, an algorithm is a sequence of finite instructions, often used for calculation and data processing....
 that is able to produce an acceptable solution to a problem in many practical scenarios, 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
Computational complexity theory

Computational complexity theory, as a branch of the theory of computation in computer science, investigates the problems related to the Computational resource required for the execution of algorithms , and the inherent difficulty in providing efficient algorithms for specific computational problems....
 etc.) or at all.

Two fundamental goals in computer science are finding algorithm
Algorithm

In mathematics, computing, linguistics and related subjects, an algorithm is a sequence of finite instructions, often used for calculation and data processing....
s with provably
Mathematical proof

In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive reasoning or empirical arguments....
  good run time
Run time

Run time or runtime may refer to:*Run time, the length of a film or television program in minutes, usually with end credits included*Runtime, in computer science, the duration of a computer program's execution, from beginning to termination...
s and with provably good or optimal
Optimization (computer science)

In computing, optimization is the process of modifying a system to make some aspect of it work more efficiently or use fewer resources. For instance, a computer program may be optimized so that it executes more rapidly, or is capable of operating with less Computer data storage or other resources, or draw less power....
 solution
Solution

In chemistry, a solution is a homogeneous mixture composed of two or more substances. In such a mixture, a solute is dissolved in another substance, known as a solvent....
 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
Knapsack problem

The knapsack problem or rucksack problem is a problem in combinatorial optimization. It derives its name from the following maximization problem of the best choice of essentials that can fit into one bag to be carried on a trip....
 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
Antivirus software

Antivirus software is computer software used to identify and remove computer viruses, as well as many other types of harmful computer software, collectively referred to as malware....
 to detect viruses and other malware.

Judea Pearl
Judea Pearl

Judea Pearl is a computer scientist and philosopher, best known for developing the probability approach to artificial intelligence, in particular through Bayesian networks , and for the formalization of causal reasoning ....
 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
Pathological (mathematics)

In mathematics, a pathological phenomenon is one whose properties are considered atypically bad or counterintuitive.Often, when the usefulness of a theorem is challenged by counterexamples, defenders of the theorem argue that the exceptions are 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 metaheuristic
Metaheuristic

A metaheuristic is a heuristic method for solving a very general class of computing problems by combining user-given procedural parameters ? usually heuristics themselves ? in the hope of obtaining a more efficient or more robust procedure....
s, which often use randomized search for example. They can be applied to a wide range of problems, but good performance is never guaranteed.

See also

  • Heuristic function
    Heuristic function

    A heuristic function, or simply a heuristic, is a Function that ranks alternatives in various search algorithms at each branching step based on the available information in order to make a decision about which branch to follow during a search....
  • Artificial Intelligence
    Artificial intelligence

    Artificial intelligence is the intelligence of machines and the branch of computer science which aims to create it. Major AI textbooks define the field as "the study and design of intelligent agents,"...
  • Expert System
    Expert system

    An expert system is software that attempts to reproduce the performance of one or more human experts, most commonly in a specific problem domain, and is a traditional application and/or subfield of artificial intelligence....
  • Logic Programming
    Logic programming

    Logic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy 's [1958] Advice taker proposal, logic is used as a purely Declarative programming language representation language, and a automated theorem proving o...