You will be given a map and a heuristic. Your job is to use A* to find the shortest path from a start city to a destination city. We will specify how A* works.  Along the way, we'll investigate how other searching algorithms evolve into A*.

First, here is the pseudo-code for a General-Search algorithm:

function General-Search (Queuing-FN) returns a solution or failure {

    nodes = Make-Queue (Make-Node (Initial-State of problem));

    loop do

            if nodes is empty then return failure;

            print(nodes); //for grading purposes only

            node = Remove-Front (nodes);

            if Goal-Test(State(node)) succeeds then return node

            nodes = Queuing-FN (nodes, Expand (node));

    end

}

The idea is just like the tree search that we did in class:

• At every stage there is a list of nodes to investigate.
• A node has all the information in it required to solve the problem. More about that later.
• We want to investigate nodes in the queue one at a time to see if we have a solution.
• If not, we open the node via the function Expand() and add the generated list to the nodes queue.
• Expand() takes a node, finds the city it is currently at and must find all the neighbors of that node. How to find those neighbors will be done by you in the first part of the assignment.

How do we queue the new nodes into nodes? That's up to Queuing-FN, which you must supply.

• If your Queuing-FN is Enqueue-At-End then your algorithm will be Breadth-First. You explore each level completely before moving down a level.
• If your Queuing-FN is Enqueue-At-Beginning then your algorithm will be Depth-First. You explore each node completely before moving across to its sibling. Most depth-first algorithms are implemented using recursion.

The above algorithms are called uninformed because we just search for the shortest solution path.  However, with maps we have real distances to compute. We don't care how many steps the path is, but rather how much distance it covers.

So, we add to the Queuing-FN a function that orders nodes by an Eval-FN function.
Eval-FN obviously depends on the application.  In chess, Eval-FN looks at a node, which is holding a board-position. What could the Eval-FN function be in the map problem?

• If the Eval-FN function is the distance from the start city to the city in the node, let's call it f(n), then the algorithm is called Best-First-Search. This is really a misnomer. It should have been called the Best-So-Far algorithm. Notice that this algorithm only looks back to compute its eval function.
• If Eval-FN is an estimate of how close the node is to the destination city, let's call it h(n), then that algorithm is called a Greedy algorithm. For maps h(n) could be the straight-line distance from the node's city to the target. h(n) is called a heuristic because it's not the real distance, but it's an estimate that's easy to compute—easy to compute is very important for heuristics.  So, now our Eval-FN with h(n) would order the nodes by which city was closest to the target city. Notice that Greedy algorithm only looks forward, that's why it's called Greedy.

Can we combine the two? Yes, easily. Let the Eval-FN be f(n)+h(n). Now, the node list will be ordered by the city whose hypothesized solution distance is shortest. Notice that the hypothesized solution distance is always smaller that the real distance, because the heuristic is always an optimistic estimate. Right? Straight-line distance is always less than or equal to the real distance (remember the triangle inequality).

Your program is to find a path of minimum distance from city A to city B.

Here's the map (each entry is an edge with its distance, i.e. A and Z are connected by an edge which is 75 miles long):

75 A Z

118 A T

140 A S

85 B U

90 B G

211 B F

101 B P

138 C P

120 C D

146 C R

75 D M

70 M L

111 T L

151 O S

71 O Z

99 S F

80 S R

98 U H

86 H E

142 U V

92 I V

87 N I

97 R P

Here's the heuristic (each entry tells you the straight-line distance from the city to B, e.g.., the straight-line distance from A to B is 366). Notice that if the problem asked you to take any two cities and compute the best path using A*, then the heuristic would an n by n matrix, where n was the number of cities in the map.

A 366

B -

C 160

D 242

E 161

F 178

G 77

H 151

I 226

L 244

M 241

N 234

O 380

P 98

R 193

S 253

T 329

U 80

V 199

Z 374

In your solution you should print out the order of the nodes you open so we know if you are doing the algorithm right. What's in a node?

• The value of f(n) so that you can compute its full evaluation.
• Enough information to know the path of how you got there. You design it.

Here is a good output. Each line is a list representing the current queue of open nodes at each step. It came from print(nodes) in the algorithm. Each node is a triple (estimated weight from start to finish, total weight from start to current vertex, and the path to current vertex).

      {(366 0[A])}

      {(393 140[A S])(447 118[A T])(449 75[A Z])}

      {(413 220[A S R])(417 239[A S F])(447 118[A T])(449 75[A Z])(671 291[A S O])}

      {(415 317[A S R P])(417 239[A S F])(447 118[A T])(449 75[A Z])(526 366[A S R C])
                        (671 291[A S O])}

      {(417 239[A S F])(418 418[A S R P B])(447 118[A T])(449 75[A Z])(526 366[A S R C])

                        (615 455[A S R P C])(671 291[A S O])}

      {(418 418[A S R P B])(447 118[A T])(449 75[A Z])(450 450[A S F B])(526 366[A S R C])

                        (615 455[A S R P C])(671 291[A S O])}

      Final Solution: [A S R P B]

      Statistic : Max Depth[5] Total Node Expanded[11]

Here’s the assignment:      

1. Read the map file and process it.

·        Write code that reads in the map file and produces a hashmap<String, List<Edge>> where String is a source city, and Edge is pair of (destination city, distance from source).
For example: the entry for hashmap.get(“A”) will return  ((Z 75)(T 118)(S 140)), in other words all the cities connected to A. This list is important because you need it in your Expand function. Right?

·        After you have created the hashmap, print out all the keys and values.

·        Make sure you write a readme.txt in detailing how to run your code.

2. Write A*

·        Create an abstract base class to house the General-Search algorithm. It will certainly have as abstract signatures: Queuing-FN, the printing function, maybe others.

·        Create a subclass to house the A* implementation.

·        Use the hashmap you created in step one in your Expand function.

·        Make sure you write a readme.txt in detailing how to run your code, tells what you think works and what doesn't.

3. Extra-Credit: Create a subclass to hold the Breadth-First implementation. In Breadth-First, there is no heuristic or evaluation function. Just queue at the end what you expand, and stop when you find ANY solution. A node should hold (current-distance path).
4. More Extra-Credit: Create a subclass to hold the Depth-First implementation. In Depth -First, there is no heuristic or evaluation function.

That's it. Good luck.

Submittal Instructions for part 1:      

 >submit -tag hashmap -user csci271 file1, file2, ...

or you can zip up your files as hashmap.zip, then:

>submit -tag hashmap -user csci271 hashmap.zip

Submittal Instructions for part 2.      

>submit -tag astar -user csci271 file1, file2, ..
 or you can zip up your files as astar.zip, then:

>submit -tag astar -user csci271 astar.zip