Heuristic (computer Science) Article Index for
Heuristic 		Shopping
Heuristic 		 

Information About

Heuristic (computer Science)
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...




HEURISTIC ALGORITHMS

Two fundamental goals in computer science are finding and with provably good or Optimal Solution quality. A heuristic is an algorithm that gives up 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.

Often, one can find specially crafted problem instances where the heuristic will in fact produce very bad results or run very slowly; however, these instances might never occur in practice because of their special structure. Therefore, the use of heuristics is very common in real world implementations.


HEURISTICS IN SHORTEST-PATH PROBLEMS


  • to choose the best node to explore. Greedy best-first search will choose the node that has the lowest value for the heuristic function. A--- search will expand nodes that have the lowest value for g(n)+h(n) , where g(n) is the (exact) cost of the path from the initial state to the current node. If h(n) is ''admissible''—that is, if h(n) never overestimates the costs of reaching the goal—, then A--- will always find an Optimal solution.


The classical problem involving heuristics is the N-puzzle . Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan Distance s between each block and its position in the goal configuration. Note that both are admissible.


Effect of heuristics on computational performance


In any searching problem where there are b choices at each node and a depth of d at the goal node, a naive searching algorithm would have to potentially search around b^d nodes before finding a solution. Heuristics improve the efficiency of search algorithms by reducing the Branching Factor from b to a lower constant b', using a cutoff mechanism. The branching factor can be used for defining a Partial Order on the heuristics, such that h_1(n) < h_2(n) if h_1(n) has a lower branch factor than h_2(n) for a given node n of the search tree. Heuristics giving lower branching factors at every node in the search tree are preferred for the resolution of a particular problem, as they are more computationally efficient.


Finding heuristics


The problem of finding an admissible heuristic with a low branching factor for common search tasks has been extensively researched in the Artificial Intelligence community.
Several common techniques are used:

  • Solution costs of sub-problems often serve as useful estimates of the overall solution cost. These are always admissible. For example, a heuristic for a 10-puzzle might be the cost of moving tiles 1-5 into their correct places. A common idea is to use a Pattern Database that stores the exact solution cost of every subproblem instance.


  • The solution of a relaxed problem often serves as a useful admissible estimate of the original. For example, manhattan distance is a relaxed version of the n-puzzle problem, because we assume we can move each tile to its position independently of moving the other tiles.


  • Given a set of admissible heuristic functions h_1(n), h_2(n), ..., h_i(n), the function h(n) = \max\{h_1(n), h_2(n), ..., h_i(n)\} is an admissible heuristic that dominates all of them.


Using these techniques a program called ABSOLVER was written (1993) by A.E. Prieditis for automatically generating heuristics for a given problem. ABSOLVER generated a new heuristic for the 8-puzzle better than any pre-existing heuristic and found the first useful heuristic for solving the Rubik's Cube .


SEE ALSO