Write a program which implements the A* algorithm on an arbitrary map described through connections file and locations file. The algorithm should allow the exclusion of 1 or more cities in the locations file. Two possible A* algorithm heuristics are required: the Straight Line Distance and the Fewest Links". Note: The fewest linksis the path in which the fewest number of connections are needed to get from start city to end city.

INPUT

The user input at runtime consists of the following:

The connections file and the locations file

-Allow the user to specify the full path of each file, for example:

c:\myDocs\myTestFiles\locations.txt

The start city

The end city

The city name(s) that should not be included in the solution path; let the user select 1 or mo re cities that are to be excluded.

The heuristic to use

- Straight line distance, or

- Fewest links

Whether to show just the optimal path foundor a step-by-steppath to the solution. The step-by-step path to the solution would allow the user to control each step by pressing the enter key

OUTPUT

For example if the start city is A1 and the end city is C3 and the user selects to sh ow only the optimal path found , the output might look like

---

OptimalPath:

A1->B1->B2->C3

However if the user selects the step-by-

step path to the solution,and the heuristic is the straight line distance,the output might look like

--

Current Path: A1

Distance traveled: 0

Best move is to: B1

Current Path: A1-> B1

Distance traveled: 10

Best move is to: A2

Current Path: A1-> A2

Distance traveled: 9

Best move is to: D1

Current Path: A1->B1->D1

Distance traveled: 18

Best move is to: B2...

Optimal Path:

A1->B1->B2->C3

Distance traveled: 38

SPECIFICATIONS

City names are given as string labels that can be from 1 to 80 characters long.

There will be no more than 200 cities.

There will be no more than 10 direct roads from one city to the next city.

There can be one-way roads. For example the connections file can show that A1 is connected to B2 but the connection from B2 does not include A1.

All city locations are given in (x, y), where x and y are positive integers in the range from 0 to 800.

(0, 0) is the top left of the coordinate space. X is the horizontal position. Y is the vertical position

Program in C++*****