# CECS 451 Assignment 1

\$30.00

Category:

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
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