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

Re: Need help with A* search question

Expand Messages
  • j1mmy_n3u7120n
    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 6:11 PM
    • 0 Attachment
      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
    • 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 2 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 3 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.