Rook Jumping Maze Instructions: Starting at the circled cell in the upper-left corner, find a path to the goal cell marked “G”. From each numbered cell, one may move that exact number of cells horizontally or vertically in a straight line. How many moves does the shortest path have?
Solution (select to reveal): [19 moves: RDLRUDRLRLUDLDRRUDD]
Problem: Using a form of stochastic local search called Hill Descent with Random Restarts, search the space of 5-by-5 Rook Jumping Mazes (RJMs) for a given number of iterations and print the best maze evaluated according to the objective function specified by Rook Jumping Maze Evaluation.
One problem with pure hill descent is that stochastic local search may become trapped in local minima, where every local step is uphill, making things worse. One escape strategy is to restart search periodically. Another way of viewing this is that we iteratively perform pure hill descent, starting each descent at a random state. The end result is the best result from all descents.
Using the definitions of hill descent, we may describe our modified algorithm as follows:
Possible background readings include:
Input Format:
Output Format:
Sample Transcripts (input underlined):
Iterations? 10000 Hill descents? 1 2 1 1 4 3 2 2 3 1 4 3 2 2 3 3 3 3 1 1 3 4 1 3 4 0 Moves from start: 0 2 1 2 6 6 3 2 4 5 1 12 10 2 11 7 4 9 8 5 14 13 3 3 15 -15
Iterations? 1000 Hill descents? 10 3 4 3 4 3 2 2 3 3 2 4 1 1 2 1 3 2 1 2 3 3 3 4 4 0 Moves from start: 0 15 7 1 14 4 4 5 3 13 11 10 9 10 12 1 3 8 2 13 -- 16 6 2 17 -17
Iterations? 100 Hill descents? 100 1 2 2 2 1 1 3 1 2 2 1 2 2 3 4 2 1 3 3 2 1 2 2 4 0 Moves from start: 0 1 5 2 6 1 2 4 5 3 2 2 5 3 6 3 -- 4 6 4 7 3 6 4 7 -7
Questions: