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

386Need help with A* search question

Expand Messages
  • wizniz
    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
    • Show all 4 messages in this topic