Mathematica 9 is now available

Wolfram Library Archive

All Collections Articles Books Conference Proceedings
Courseware Demos MathSource Technical Notes
Title Downloads

Heuristic Search Techniques

Raza Ahmed
Organization: University of California at Berkeley
Brian L. Evans
Organization: University of Texas
Department: Department of Electrical and Computer Engineering
Old MathSource #

Revision date


This package defines breadth-first, depth-first, hill climbing, and simulated annealing search techniques in the Mathematica programming language. These search techniques apply a list of transformation rules to minimize the cost of an expression. The user gives the list of rearrangement rules, the expression to be optimized, and the function to compute cost. When LeafCount is used as the cost function, for example, the search techniques will simplify the expression.

Breadth-first and depth-first searches will always find the optimal answer but requires memory that is exponential in the number of transformation rules in the worst case. Hill climbing and simulated annealing only require a constant amount of memory, but they are not guaranteed to find the optimal answer. Simulated annealing can be modified to find the optimal answer in exponential time with constant memory.

We provide a notebook that gives examples of using these search techniques to minimize the cost of evaluating polynomials. Hill climbing outperforms breadth-first and depth-first searching in execution time and memory usage to find the same optimal answer. Hill climbing runs faster than simulated annealing because the optimization steps fit a steepest decent approach.

*Applied Mathematics > Computer Science

hill climbing search, simulated annealing search, breadth-first search, depth-first search, simplification, rearrangement, optimizing implementation cost, artificial intelligence, search algorithms
Downloads Download Wolfram CDF Player

README (10.3 KB) - Installation instructions
GeneralSearch.m (5.9 KB) - Supporting routines
InformedSearch.m (6.5 KB) - Hill Climbing and Simulated Annealing
Master.m (661 B) - Stubs for the Heuristic Search package
PolySearchFunctions.m (5.5 KB) - Optimizing polynomial calculations
UninformedSearch.m (4.4 KB) - Breadth- and Depth-First Searches
finalpolybook.nb (26.6 KB) - Notebook showing how to use the package

Files specific to Mathematica 2.2 version:
Download (20 KB) - Notebook showing how to use the package