- 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 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

distances already calculated).

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 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

--- j1mmy_n3u7120n <padmatv@...> wrote:

> 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

> distances already calculated).

>

> 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 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