辅导CS452/552、讲解Articial Intelligence

- 首页 >> Java编程


Homework 1 — Using A* Search

UWL CS452/552 Arti€cial Intelligence

Fall 2019

For your €rst homework, please write a Java[1] class which implements A* search to €nd the

best travel path betwee two cities, given cost information between a subset of pairs of those cities.

In the resources for this homework linked from Canvas, you will €nd two Java source €les.

One of these classes, FoundPath, just bundles up the details of an A* search. The other class,

Pathfinder, is an abstract class which you will extend. The core of your work is the method

getPathInfo[2]:

public abstract FoundPath getPathInfo(String startCity, String endCity);

Your class AStar should extend Pathfinder, implementing an A* search to €nd the shortest path

between the named start- and endpoints. Its result bundles up certain information which your

search should gather:

• The sequence of cities in the best path between cities, or an empty list if no such path is

possible. The €rst element of this list should be startCity, and the last element of this list

should be endCity.

• The total cost of following the above path, or the empty instance if there no such path is

possible[3]

.

• The number of nodes which A* generated in the search (i.e. nodes ever placed into the

frontier).

• The number of nodes le† in the frontier at the end of the search (i.e. nodes in the frontier

but never expanded).

The FoundPath interface describes methods for these values, and your implementation of getPathInfo

should return an object implementing this interface.

Your class AStar should provide (among any other constructors which you might use for your

own development and testing purposes) a one-argument constructor, where the argument is a

String naming a €le containing information about the cities known to your algorithm. Such a €le

will have the format shown in Figure 1. That is, the €le describes a set of N cities, with €xed

(latitude, longitude) locations, de€ned on the €rst N + 1 lines of the €le. 1 The next set of lines

describes distances between pairs of named cities (lines starting with ‘#’ are comments). Each pair

of cities appears at most once in this list. If some pair of cities is in the list, then the distance

between them is the same in both directions. If some pair of cities is not in the list, then there

is no direct connection between those two cities, and any path between those cities must pass

# name latitude longitude

<CITY NAME 1> <LAT 1> <LON 1>

...

<CITY NAME N> <LAT N><LON N>

# distances

<CITY NAME X1>, <CITY NAME Y1>: <MILES BETWEEN CITY X1 AND CITY Y1>

...

<CITY NAME XM>, <CITY NAME YM>: <MILES BETWEEN CITY XM AND CITY YM>

Figure 1: The cities speci€cation €le.

# name latitude longitude

La Crosse 43.8 -91.24

La Crescent 43.83 -91.3

Winona 44.06 -91.67

Minneapolis 44.98 -93.27

# distances

La Crosse, La Crescent: 5.0

La Crosse, Winona: 31.6

La Crescent, Winona: 27.5

La Crescent, Minneapolis: 142.0

Winona, Minneapolis: 116.0

Figure 2: A small example of a cities speci€cation.

through some other city €rst (if any such path exists). Figure 2 shows a small example with four

local cities. This small €le will be included in the examples to be made available on Canvas.

For your A* heuristic, you should use the length of the shortest possible arc on the surface of

the Earth between a city C and the goal G.

[4] If calculated correctly, this arc length is guaranteed

to be an admissible and consistent heuristic for the data sets given.

Your code should be ecient enough that it can handle the larger example €le which you will

receive, which contains data for several hundred cities. However, small examples are typically

easier for debugging. You are of course encouraged to make additional examples for your own

purposes.

You should assume that the getPathInfo will be called more than once per instance. It should

return consistent results for the same information from call to call.

We will see in class that the most basic speci€cation of A* allows a single city to appear multiple

times during a search path. The algorithm will not output these non-optimal paths as solutions,

but it will still explore them as it tries to €nd the optimal path. For domains with non-decreasing

path costs (like this one), generating these paths is inecient, and we will want to avoid it. There

will be two submission points for your code:

• Your €rst implementation should leave this ineciency in, so repeated nodes are allowed

during search.

• Your second submission should remove this ineciency, so that repeated nodes are ignored

along a single path.

Your code should be well-formatted, and documented with both Javadoc and inline comments.

The inline comments should focus on the explanation of the AI ideas implemented.

There are a number of other abstract methods de€ned in Pathfinder.java, and a number of

additional requirements mentioned in the Javadoc comments of that €le, which I expect you to

implement.

The two implementations for this assignment are due on Thursday, September 26, at the

usual deadline time of 11:59pm (La Crosse local time). Do not resubmit the FoundPath.java

and Pathfinder.java €les, which you must not alter. Details of the exact form and mechanics of

the submission are to follow.

Notes

1. I prefer that you code the solution in Java, but I am open to discussing other languages.

Come speak with me before you start, so we can discuss feasibility and agree on a protocol.

Two points related to choosing an alternative language:

• Do not wait to discuss this: because we may need time to think about the format of

your work, and because I can manage only so many other languages.

• I have not yet written all of the homeworks for this class, and I cannot guarantee that

every homework will support alternative languages.

2. The full €le also contains Javadoc comments, additional declarations, and helper/administrative

methods — see the full source for details.

3. The java.util.Optional class represents a value which could be present, or which might

not exist at all. See its Javadoc API documentation for more information, and for the static

methods used to create an Optional instance.

4. Details of how to calculate this distance using the Haversine formula can be found at

http://andrew.hedges.name/experiments/haversine . Note that for this formula to work:

• The inputs to any of the trigonometry functions must be in the form of radians, not

degrees. Since the data given in the input €le has latitude and longitude in degrees, you

will need to convert.

• Since distances in the input are given in miles, you should also use miles for the radius

of the Earth.

Do not worry about possible errors in the heuristic arising from the fact that our Earth is

not a perfect sphere.



站长地图