## 386Need help with A* search question

Expand Messages
• Sep 6, 2004
Hi i got a question here.. im pretty weak with java coding but i
learnt that the best way to solve this question i have is to use
java.

How do i use vectors to create the tree in the first place for this
question? i was thinking if i needed a vector the information needed
would be

Vector CityA (straight line distance) (distance so far=cost)

how do i use the vector to show teh connection or check for
connection for each city?

If anyone can help me with this pls email me.. either with some help
or if u have a suggested solution using java code. I would be most
grateful.. tnx a million.

Rgds
Feroz

---------------------------------------------------------
My aim is to find a path with the shortest distance between any 2
cities in a graph of interconnecting cities.

Input being : a list of city names, their x-coordinate and y-
coordinate. For example

city washington 138.0 145.0

The name of a city is a string of characters without any intervening
spaces.If two cities are connected by a direct route, it is indicated
in the input file. For example,

conn washington boston

indicates that washington is connected by a direct route to boston.
The start city and goal (destination) city is also indicated in the
input file. For example,

start kansas
goal michigan

indicates that kansas is the start city and michigan the goal
(destination) city.

Given the x- and y-coordinates of the cities, the connections between
the cities, the start city and the goal city, the program is to
perform A* search to find a path with the shortest distance from the
start city to the goal city. The straight-line distance is to be used
as the heuristic function, with the assumption that the cities are
laid out on a 2-dimensional plane.

The program must be general and works correctly on any number of
cities and any interconnection configuration.

-------------------------------------
An example inputfile is:
city washington 138.0 145.0
city california 149.0 145.0
city michigan 142.0 137.0
city boston 145.0 142.0
city kansas 151.0 146.0
conn washington boston
conn washington kansas
conn california boston
conn california kansas
conn michigan boston
start kansas
goal michigan

The corresponding outputfile in this case is:
13.067 kansas california boston michigan 0.01 sec
• Show all 4 messages in this topic