CECS 451 Assignment 1

CECS 451
Assignment 1
Total: 40 Points
General Instruction
• Submit uncompressed file(s) in the Dropbox folder via BeachBoard (Not email).
• Use Python 3, any other programming language is not acceptable.
• You can import modules in the Python Standard Library (please check the full list
here). If you want to use any other library, please consult with the instructor or TA.
• Your submission may be evaluated automatically using a script file, so if you would
not follow the output format, you may receive zero point even though your program
outputs correct answers.
1. (40 points) Implement an optimal route finder program using A* algorithm.
i. Find coordinates.txt and map.txt. Figure 1 is attached for your information.
ii. coordinates.txt stores the latitude and longitude of each city.
City:(Latitude,Longitude)
iii. map.txt stores actual distances between connected cities in California. We assume
each city is connected with limited number of nearby cities.
City-NearbyCity1(Distance),NearbyCity2(Distance),...
iv. You can compute the straight line distance between two cities using the Haversine
formula.
• You need to convert latitude and longitude to radian. (radian =
π
180 degree)
• Let ϕ1, ϕ2 be the latitude of point 1 and latitude of point 2
and λ1, λ2 be the longitude of point 1 and longitude of point 2.
• The straight line distance d is defined by
d = 2 · r · arcsin r
sin2
ϕ2 − ϕ1
2


+ cos ϕ1 · cos ϕ2 · sin2
λ2 − λ1
2



, where r is the radius of the earth. Use r = 3, 958.8 mile.
v. The program should be able to
• parse coordinates.txt and map.txt
• take a departing city and an arriving city as input arguments (an interactive
style is not acceptable).
• output an optimal route from the departing city to the arriving cit
CECS 451 Assignment 1 - Page 2 of 2
vi. Please follow the output format below.
> python a-star.py SanFrancisco LongBeach
From city: SanFrancisco
To city: LongBeach
Best Route: SanFrancisco - SanJose - Fresno - LosAngeles - LongBeach
Total distance: 442 mi
vii. Submit a-star.py file.
Figure 1: A map of cities in California