Browse Groups

• 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
Message 1 of 4 , Sep 6, 2004
View Source
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
• Vectors will be hardly helpful! I see it nothing more than a collection of elements just like an array. Moreover its pretty slow. For your problem there is a
Message 1 of 4 , Sep 7, 2004
View Source
Vectors will be hardly helpful! I see it nothing more than a
collection of elements just like an array. Moreover its pretty slow.

For your problem there is a much easier implementation,
write a class edge say like,
class Edge
{
/*basic attributes*/
String City1,City2;
float heuristic distance;
/*basic method*/
calcHeuristic()

/*Other methods and attributes may be added as needed*/
}

Then simply create a 2D Matrix
Edge[][];

read from the file and generate the appropriately sized matrix.
u can index the cities as u wish.
for ur example, we can have
0 washington
1 california
2 michigan
3 boston
4 kansas

Notice that all this is done just at the start .. then simply run
your A* algorithm on this matrix(which will have all the heuristic

This implementation is much easier to implement and not to mention
smaller.

--- In aima-talk@yahoogroups.com, "wizniz" <wizniz@r...> wrote:
> 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
• Hi jimmy.. thanks a lot for ur reply.. but i dont quite understand what the class edge is for.. and how i can use the matrix to find out the best solution i
Message 1 of 4 , Sep 11, 2004
View Source
Hi jimmy.. thanks a lot for ur reply..

but i dont quite understand what the class edge is
for.. and how i can use the matrix to find out the
best solution i want..

would u have the code for that part? im confused on
how to use the class and yet show the overrall total
distance travelled so far.. and the A* search works on
a stucture that seems like a tree after the distances
are all worked out right?

Would u be able to write the code to solve this
question? If its not too much trouble.. thnx.

I could take a look and learn from it then..

Rgds
Feroz

> Vectors will be hardly helpful! I see it nothing
> more than a
> collection of elements just like an array. Moreover
> its pretty slow.
>
> For your problem there is a much easier
> implementation,
> write a class edge say like,
> class Edge
> {
> /*basic attributes*/
> String City1,City2;
> float heuristic distance;
> /*basic method*/
> calcHeuristic()
>
> /*Other methods and attributes may be added as
> needed*/
> }
>
> Then simply create a 2D Matrix
> Edge[][];
>
> read from the file and generate the appropriately
> sized matrix.
> u can index the cities as u wish.
> for ur example, we can have
> 0 washington
> 1 california
> 2 michigan
> 3 boston
> 4 kansas
>
> Notice that all this is done just at the start ..
> then simply run
> your A* algorithm on this matrix(which will have all
> the heuristic
>
> This implementation is much easier to implement and
> not to mention
> smaller.
>
> --- In aima-talk@yahoogroups.com, "wizniz"
> <wizniz@r...> wrote:
> > 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
>
>
>

__________________________________
Do you Yahoo!?
Yahoo! Mail - Helps protect you from nasty viruses.
http://promotions.yahoo.com/new_mail
• Note that the class is of no specific use , its more like the structure in C but u can add some important functions like calcHeuristic to this class which
Message 1 of 4 , Sep 16, 2004
View Source
Note that the class is of no specific use , its more like the
structure in C but u can add some important functions like
calcHeuristic to this class which calculates heuristic distances (in
your case the euclidean distance between the cities).

the class matrix Edge[][] is nothing more than a weighted matrix like
the one we use in graphs.(Note that the tree is also a graph without
loops thats all. So u can represent a tree even in a weighted matrix
form .... )

what i did was instead of having just simple weighted matrix ... i
have many information stored along with the weight. For applying the
A* to this matrix .. u will be travelling the matrix from (left to
right) or (top to bottom) whichever way u prefer.

-- AI

P.S -> And no i don't have a working code neither am i planning to
write one in the immediate future.

--- In aima-talk@yahoogroups.com, Nizam A Haja <wizniz@r...> wrote:
> Hi jimmy.. thanks a lot for ur reply..
>
> but i dont quite understand what the class edge is
> for.. and how i can use the matrix to find out the
> best solution i want..
>
> would u have the code for that part? im confused on
> how to use the class and yet show the overrall total
> distance travelled so far.. and the A* search works on
> a stucture that seems like a tree after the distances
> are all worked out right?
>
> Would u be able to write the code to solve this
> question? If its not too much trouble.. thnx.
>
> I could take a look and learn from it then..
>
> Rgds
> Feroz
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.