代写程序解决类似华容道的问题，用A*算法实现，很有意思的一个作业。
Background
Safari Rush Hour is a variation on the popular Rush Hour game from Binary
Arts. The object is to move your car through a tangle of obstacles to reach
the exit. Your job is to write a program to find the best way out of the
traffic.
Rules
Safari Rush Hour is played on a 7 x 7 game grid with up to 19 playing pieces
(safari rover and animals). The object is to slide the safari rover through
the exit gate in the playing grid frame. Each puzzle gives a configuration of
animals and the safari rover. To play, you shift the animals and safari rover
up, down, left, and right until the path is clear to make your escape. Note:
lions, lionesses, impalas, zebras, rhinos, and elephants move only forward and
reverse. The large square safari rover and the wild dogs (termite mound) may
move up, down, right, and left. No lifting of playing pieces off of the
gameboard grid surface once play has begun.
Example
The predecessor game of Safari Rush Hour is Rush Hour. It is played on a
smaller board, with a different number and different shaped pieces. Try
playing the applet here. You can practice on this applet to get an idea of how
to solve Safari Rush Hour puzzles.
Input
A sample problem input looks as follows:
P J1
…….
.rrrf..
hh..fq.!
o.xx.q.!
o.xx.q.
ob..ee.
.bppp..
The first line indicates a problem (“P”) and the name of the problem (“J1”).
The problems are all numbered, and the first letter indicates the difficulty
of the problem: “J” is junior, “B” is beginner, “I” is intermediate, “A” is
advanced, and “E” is expert. In the puzzle specification, the letters stand
for the playing pieces: 2x2 pieces: termite mounds (u,v) and safari rover (x);
3x1 pieces: elephant (o, q, s) and rhino (p, r); 2x1 pieces: lion (a, f),
lioness (d, g, j), impala (b, h, i, k) and zebra (c, e). The actual names do
not matter; all that is important is the shape of each of the pieces and the
way that they move. The “!” indicates the exit (the exit position is fixed and
does not change from puzzle to puzzle).
Solution
Using A* or IDA*, your assignment is to solve a given puzzle in the minimum
number of moves with the smallest search tree possible. The latter implies
enhancing A*/IDA* to eliminate as much of the search tree as possible using
some of the standard techniques in the literature (or possibly some of your
own application-dependent enhancements). Files a2-orig.data, a2-deep.data,
a2-vast.data, a2-fiendish.data contain test sets of problems for evaluating
your solutions.
Report solution using the following format:
solution [id] [t] [n] [move_1] … [move_n]
where [id] is the problem id, [t] is the wallclock time in seconds your
program required to find the solution (or “timeout” if your program timed out
- see -t options below) [n] is the number of moves and [move_i] is a move
encoded by specifying the name of the piece, its move direction (“l”eft,
“r”ight, “u”p, or “d”own) followed by the number of squares that the piece
moves. For example, a solution line for the puzzle above is:
solution J1 0.15 5 el1 qd2 fu1 xu1 xr5
The length of a solution is the number of move strings. Note that the rover
must be moved off the board completely. Test your program on the
junior/beginner problems. Then work your way up to the more difficult ones.
Your program should output the following. For each input problem, I want to
see statistics on the number of nodes searched, execution time, average
h-value for all nodes where an evaluation occurred in the tree, and
min/average/max depth of nodes where a cutoff occurred. When the program
successfully terminates, print out the solution.
Specifications
Your program should take input from stdin and output to stdout. The input is
in the format given above possibly containing multiple positions which need to
be solved by your program in turn.
You program must be single-threaded and use no more than 200 MB of RAM. You
must implement command-line option -t n, where n is an integer. This option
sets the program to stop searching a position after n seconds of real time. If
a timeout occurs your program must report “timeout” as time and proceed with
the next problem.
Submission
A tar file that contains your source code, a makefile, and a report in pdf
format. Your executable must be named safari. Late assignments will not be
accepted!
In the report, give me a description of your program. Skip the basics (such as
A*/IDA*). I want to know any search enhancements that you tried. Describe your
heuristic function. Tell me what you did that was interesting. What problems
did you encounter? How can your solution be improved? This document must be no
longer than five pages. Include a table of experimental results that shows the
(positive?) impact of your enhancements.
