The Maze Problem
Problem Description
Program Descriptions
 maze.m
This program tries to find the shortest path through a maze, by generating a set of choices at junctions. For example, an output may indicate something along the lines of ``At Junction 1, go East, at the next Junction, go South ...''. The set of choices is updated via the CE method.Usage:
Call the program from MATLAB, with the following syntax:
pi = maze( N , rho , alpha , M , start , finish )
Example: pi = maze( 1000 , 0.02 , 0.7 , MAZE , [1,1] , [12,12] )
Where, in this example, M is a 12x12 maze of 0s and 1s, with 1s representing walls, and 0s representing the paths. The start of the maze is at [1,1] and the end is at [12,12]. Note that this method seems to perform quite well on very small mazes, or on mazes with few junctions, but performs less well on larger problems.Inputs: N  Number of samples to generate each iteration rho  Fraction of samples to use to update the choices alpha  Smoothing parameter M  A matrix of 1s and 0s, representing a maze start  Starting position finish  Ending position Outputs: pi  Output choice set  gmaze.m
This program is used internally to generate a set of direction choices.  smaze.m
This program is used internally to evaluate the performance of a given set of direction choices.
Bibliography

D. P. Kroese and R. Y. Rubinstein.
The CrossEntropy Method: A Unified Approach to Combinatorial Optimization, MonteCarlo Simulation and Machine Learning.
Springer, 2004.