|
|
|
|
|
|
 |
 |
|
Heuristic Search Techniques
|
|
|
|
|
|
| Organization: | University of California at Berkeley |
| Organization: | University of Texas |
| Department: | Department of Electrical and Computer Engineering |
|
|
|
|
|
|
0208-044
|
|
|
|
|
|
1996-06-24
|
|
|
|
|
|
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.
|
|
|
|
|
|
|
|
|
|
|
|
hill climbing search, simulated annealing search, breadth-first search, depth-first search, simplification, rearrangement, optimizing implementation cost, artificial intelligence, search algorithms
|
|
|
 |
|
|
| 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:
| | finalpolybook.ma (20 KB) - Notebook showing how to use the package |
|
|
|
|
|
|
|
| | | | | |
|
For the newest resources, visit Wolfram Repositories and Archives »
