Heuristic Map A* Search Algorithm Assignment C++
CS 332 – Assignment 2
Assignment description
Here is the map of Glastonbury, Connecticut for Halloween celebration. Kids will gather at Glastonbury High School (starting point, noted as GHS in the map) and find a
way to go to William Pond Halloween Party (goal). The arcs are labeled with the real cost of traversing them from one point to another (distance in kilometers). The
goal is to find a path from GHS to William Pond Halloween Party.
Table 1 (below) provides the straight line estimate for all the nodes to the final destination (h). Use these costs in A* search to list the most cost-effective path
from GHS to William Pond Halloween Party
Street
Straight Line Distance (in km)
GHS
1.79
Nepsic Hunted House
0.95
Lancaster cemetery
1.54
Halloween Creepy Carnival
1.52
Zombie
1.6
Skeleton House
1.53
William Pond Halloween Party
0
Table 1: Heuristic information for this search problem.
You are asked to develop a software agent that use A* search algorithm to find out the path from GHS to William Pond Halloween party. You will have two input files.
The first file is map.txt and the second file is heuristic.txt. map.txt describes the information about the nodes and distances between nodes in the map while
heuristic.txt describes information from table 1.Your program would return the output of places and the total costs from the GHS to the William Pond using A* search
algorithm. For example:
Path: GHS -> Nepsic Hunted House -> William Pond Halloween Party
Cost: 1.84
File #1
File #2
File #3
