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

Need help with A* search question

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