代写AI的经典最小路径的问题，算法用A*即可快速求出最小路径。
Requirement
This assignment deals with an offline navigation problem. In the general case,
search would be on a directed, labelled graph. Here we make a number of
simplifying assumptions. An agent is given an n × n grid, with co-ordinates in
the range 0,…,n - 1. For the most part, each position (i, j) is connected to
its immediate neighbours; i.e. to (i, j + 1), (i, j − 1), (i + 1, j), and (i −
1, j), provided no index goes outside the grid’s boundary. However, some
connections are blocked, and a path will have to go around them. Your program
is to take a pair of points, say (s(x), s(y)) and (g(x) , g(y)), and find a
shortest path from the first point to the second.
There are two parts to the assignment. For both parts, assume that you are
give the scenario as in the figure: The grid is 18 × 18, with co-ordinates
running from (0, 0) to (17, 17). There are two obstacles, and the following
co-ordinate points are inaccessible:
(7, 5), (7, 6), (7, 7), (7, 8), (7, 9) and
(10, 13), (11, 13), (12, 13), (13, 13), (14, 13), (15, 13), (15, 12).
So, for example, a path cannot go through (7, 5). You do not need to handle
arbitrary board configurations, so it’s ok to hard code the example in your
program.
Part 1
For this part, ignore the letters “a”-“d” in the figure. Write a program that
determines the shortest path between any two points. While you can chose your
language for the assignment, it must be one of the ones commonly used in the
School – i.e. C/C++, Python, or Java. Justify your choice of search strategy.
Make sure that you test you program with start point (0, 0) and goal (17, 17);
carry out any other testing that you feel is necessary to illustrate that your
program does what it’s supposed to do.
Your program should output:
- The length of the shortest path.
- The shortest path.
- The total number of nodes placed on the fringe (frontier).
- Anything else you think may be helpful.
Part 2
In this part you want to find a path that is not necessarily optimal, but uses
a search that is expected to be more efficient. (So here we’re going to trade
off optimality for speed.)
A common scheme to improve search in such a setting is to choose a number of
“landmarks”, and precompute the paths between adjacent landmarks. The landmark
graph then becomes another, higher-level representation for the search. Then
the general search algorithm could be something like:
- Find the shortest path from the start position to the nearest landmark
- Find the shortest path from the goal position to the nearest landmark
- Add in the precomputed path between the two landmarks.
However, you need to be careful, since it may be more efficient to go directly
between the start and goal states, rather than going through any landmarks.
In the figure, landmarks are at the points labelled “a”, “b”, “c”, and “d”, at
(5, 12), (12, 12), (5, 5), and (12, 5). Since there are only 4 landmarks, the
shortest path between all landmarks (there are 6 of them) can be precomputed.
You can do this by hand, or you can use your program in Part 1 to find them.
Again in your testing you should find a path from (0, 0) to (17, 17), and you
should output: - The length of the shortest path.
- The shortest path (although you do not need to output the path between landmarks).
- The number of nodes on the fringe.
- Anything else you think may be helpful.
Please fully comment and document your programs, and discuss the heuristics
used along with any other interesting features of your programs. As well,
include a README file that describes how to run your programs.
