Mathematica 9 is now available

Wolfram Library Archive


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

Heuristic Search Techniques
Authors

Raza Ahmed
Organization: University of California at Berkeley
Brian L. Evans
Organization: University of Texas
Department: Department of Electrical and Computer Engineering
URL: http://www.ece.utexas.edu/~bevans/
Old MathSource #

0208-044
Revision date

1996-06-24
Description

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.
Subject

*Applied Mathematics > Computer Science
Keywords

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

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

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