This past week we worked on framing problems for search. Now you will implement some basic search algorithms in Python. Attached below is a text file that describes a set of cities and the roads between them. A visual for the map is shown below.Your task is to write a Python module that:
- Loads the cities file into memory to define a search space.
- Applies breadth-first search, uniform-cost search, and A* search to find paths between cities.
Your code should be called as follows:
python SearchCities.py
As your code runs it should print the cities that it is expanding and, when complete it should print out the final result in a clear readable format. A formula for a straight-line lat/long heuristic function is shown at the top of the cities file.
%=============================== Heuristic Function =================================== % sqrt((69.5 * (Lat1 - Lat2)) ** 2 + (69.5 * cos((Lat1 + Lat2)/360 * pi) * (Long1 - Long2)) ** 2) %========================== Cities (name, latitude, longitude) ======================== albanyNY, 42.66, 73.78 atlanta, 33.76, 84.40 austin, 30.30, 97.75 boston, 42.32, 71.09 buffalo, 42.90, 78.85 calgary, 51.00, 114.00 charlotte, 35.21, 80.83 chicago, 41.84, 87.68 cleveland, 41.48, 81.67 dallas, 32.80, 96.79 dayton, 39.76, 84.20 denver, 39.73, 104.97 desMoines, 41.59, 93.62 elPaso, 31.79, 106.42 europe, 48.87, -2.33 ftWorth, 32.74, 97.33 houston, 29.76, 95.38 indianapolis, 39.79, 86.15 jacksonville, 30.32, 81.66 japan, 35.68, 220.23 kansasCity, 39.08, 94.56 keyWest, 24.56, 81.78 lakeCity, 30.19, 82.64 lasVegas, 36.19, 115.22 losAngeles, 34.03, 118.17 medford, 42.33, 122.86 memphis, 35.12, 89.97 mexico, 19.40, 99.12 miami, 25.79, 80.22 minneapolis, 44.96, 93.27 modesto, 37.3, 120.9 montreal, 45.50, 73.67 newHaven, 41.31, 72.92 newOrleans, 29.97, 90.06 newYork, 40.70, 73.92 omaha, 41.26, 96.01 orlando, 28.53, 81.38 philadelphia, 40.72, 76.12 phoenix, 33.53, 112.08 pointReyes, 38.07, 122.81 portland, 45.52, 122.64 provo, 40.24, 111.66 raleigh, 35.82, 78.64 reno, 39.53, 119.82 sacramento, 38.56, 121.47 saltLakeCity, 40.75, 111.89 sanAntonio, 29.45, 98.51 sanDiego, 32.78, 117.15 sanFrancisco, 37.76, 122.44 sanJose, 37.30, 121.87 sanLuisObispo, 35.27, 120.66 santaFe, 35.67, 105.96 saultSteMarie, 46.49, 84.35 seattle, 47.63, 122.33 tallahassee, 30.45, 84.27 tampa, 27.97, 82.46 toledo, 41.67, 83.58 toronto, 43.65, 79.38 tucson, 32.21, 110.92 tulsa, 36.13, 95.94 uk, 51.30, 0.00 vancouver, 49.25, 123.10 washington, 38.91, 77.01 wichita, 37.69, 97.34 winnipeg, 49.90, 97.13 %====================================== Roads ======================================== albanyNY, montreal, 226 albanyNY, boston, 166 albanyNY, buffalo, 212 atlanta, memphis, 456 atlanta, tallahassee, 308 austin, houston, 186 austin, sanAntonio, 79 boston, newHaven, 161 buffalo, toronto, 105 buffalo, cleveland, 191 calgary, vancouver, 605 calgary, winnipeg, 829 charlotte, jacksonville, 432 charlotte, raleigh, 165 chicago, minneapolis, 511 chicago, toledo, 361 cleveland, philadelphia, 476 cleveland, dayton, 214 dallas, denver, 792 dallas, houston, 248 dayton, indianapolis, 165 denver, wichita, 523 denver, provo, 466 denver, santaFe, 386 desMoines, omaha, 135 desMoines, minneapolis, 246 elPaso, sanAntonio, 580 elPaso, tucson, 320 elPaso, santaFe, 328 europe, philadelphia, 3939 ftWorth, tulsa, 314 houston, newOrleans, 321 indianapolis, kansasCity, 502 jacksonville, orlando, 146 jacksonville, lakeCity, 113 japan, pointReyes, 5131 japan, sanLuisObispo, 5451 kansasCity, tulsa, 249 kansasCity, wichita, 190 keyWest, tampa, 446 lakeCity, tampa, 169 lakeCity, tallahassee, 104 lasVegas, losAngeles, 275 lasVegas, saltLakeCity, 486 losAngeles, sanDiego, 124 losAngeles, sanLuisObispo, 182 losAngeles, modesto, 328 medford, portland, 275 medford, pointReyes, 365 memphis, tulsa, 413 miami, orlando, 235 minneapolis, winnipeg, 463 modesto, sacramento, 80 montreal, toronto, 401 newOrleans, tallahassee, 388 newYork, philadelphia, 101 orlando, tampa, 84 philadelphia, uk, 3548 philadelphia, washington, 147 phoenix, tucson, 117 phoenix, sanDiego, 518 pointReyes, sacramento, 115 portland, seattle, 174 portland, saltLakeCity, 777 raleigh, washington, 371 reno, saltLakeCity, 520 reno, sacramento, 133 sacramento, sanFrancisco, 95 sanAntonio, mexico, 895 sanFrancisco, sanJose, 50 sanJose, sanLuisObispo, 168 saultSteMarie, winnipeg, 882 saultSteMarie, toronto, 436 seattle, vancouver, 115 wichita, omaha, 335