Loading ...
Sorry, an error occurred while loading the content.

Re: [aima-talk] Re: Need help with A* search question

Expand Messages
  • Nizam A Haja
    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 11:19 PM
    • 0 Attachment
      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
    • j1mmy_n3u7120n
      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 2 of 4 , Sep 16 4:40 AM
      • 0 Attachment
        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.