Sorry, an error occurred while loading the content.

## Re: Need help with A* search question

Expand Messages
• 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
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 2 of 4 , Sep 11, 2004
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
Message 3 of 4 , Sep 16, 2004
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.