.. _citytourlongsolutionrst: ============================ Longer city tours (solution) ============================ .. only:: html **Links:** :download:`notebook `, :downloadlink:`html `, :download:`PDF `, :download:`python `, :downloadlink:`slides `, :githublink:`GitHub|_doc/notebooks/challenges/city_tour/city_tour_long_solution.ipynb|*` Solutions to the bigger examples for the challenge: find the shortest path through a set of streets. .. code:: ipython3 %matplotlib inline import matplotlib.pyplot as plt plt.style.use("ggplot") .. code:: ipython3 from jyquickhelper import add_notebook_menu add_notebook_menu() .. contents:: :local: Level 1 ------- .. code:: ipython3 from ensae_projects.datainc.data_geo_streets import get_seattle_streets, shapely_records from ensae_projects.datainc.data_geo_streets import seattle_streets_set_small, folium_html_street_map name = get_seattle_streets() shapes, records, fields = shapely_records(name) edges_index, edges, vertices, distances = seattle_streets_set_small(shapes, records) folium_html_street_map(edges_index, shapes, html_width="50%", zoom_start=15) .. raw:: html

.. code:: ipython3 from ensae_projects.datainc.data_geo_streets import plot_streets_network plot_streets_network(edges_index, edges, vertices, shapes, figsize=(10,10)); .. image:: city_tour_long_solution_5_0.png .. code:: ipython3 from ensae_projects.challenge.city_tour import best_euler_path couples, solution, distance = best_euler_path(edges_index=edges_index, edges=edges, distances=distances, vertices=vertices, fLOG=print) "distance", distance .. parsed-literal:: [best_euler_path] distance_vertices #edges=24 [best_euler_path] bellman_distances [bellman_distances] iteration=1 modif=74 #dist=122 sum_values=0.26812913941842903 avg=0.0021977798312985985 [bellman_distances] iteration=2 modif=102 #dist=214 sum_values=0.6638654574495177 avg=0.0031021750348108304 [bellman_distances] iteration=3 modif=130 #dist=298 sum_values=1.3475652021993083 avg=0.004522030879863451 [bellman_distances] iteration=4 modif=100 #dist=306 sum_values=1.3653257205807 avg=0.004461848760067647 [bellman_distances] iteration=5 modif=64 #dist=306 sum_values=1.2780455413890799 avg=0.0041766194163041824 [bellman_distances] iteration=6 modif=42 #dist=306 sum_values=1.2282394949878546 avg=0.0040138545587838385 [bellman_distances] iteration=7 modif=24 #dist=306 sum_values=1.207369883828586 avg=0.003945653215126098 [bellman_distances] iteration=8 modif=12 #dist=306 sum_values=1.1964121229039824 avg=0.003909843538901903 [bellman_distances] iteration=9 modif=10 #dist=306 sum_values=1.1840886861931539 avg=0.0038695708699122678 [bellman_distances] iteration=10 modif=6 #dist=306 sum_values=1.1840669671109263 avg=0.0038694998925193668 [bellman_distances] iteration=11 modif=2 #dist=306 sum_values=1.1840669671109263 avg=0.0038694998925193668 [bellman_distances] iteration=12 modif=2 #dist=306 sum_values=1.1840644116345598 avg=0.003869491541289411 [bellman_distances] iteration=13 modif=0 #dist=306 sum_values=1.1840644116345598 avg=0.003869491541289411 [best_euler_path] degrees and distances between odd vertices [best_euler_path] matching #odd=6, #odd_dist=30 [best_euler_path] build solution [best_euler_path] order edges to get the path #edges=31 [best_euler_path] done. .. parsed-literal:: ('distance', 0.04360778144581235) .. code:: ipython3 from ensae_projects.challenge.city_tour import euler_path plot_streets_network(edges_index, edges, vertices, shapes, order=solution, figsize=(10,10)); .. image:: city_tour_long_solution_7_0.png Level 2 ------- .. code:: ipython3 from ensae_projects.datainc.data_geo_streets import seattle_streets_set_level2 edges_index, edges, vertices, distances = seattle_streets_set_level2(shapes, records) folium_html_street_map(edges_index, shapes, html_width="80%", zoom_start=14) .. raw:: html

.. code:: ipython3 from ensae_projects.challenge.city_tour import best_euler_path couples, solution, distance = best_euler_path(edges_index=edges_index, edges=edges, distances=distances, vertices=vertices, fLOG=print) "distance", distance .. parsed-literal:: [best_euler_path] distance_vertices #edges=129 [best_euler_path] bellman_distances [bellman_distances] iteration=1 modif=472 #dist=730 sum_values=1.3426775505752198 avg=0.0018392843158564654 [bellman_distances] iteration=2 modif=896 #dist=1560 sum_values=4.509671272151574 avg=0.002890814918045881 [bellman_distances] iteration=3 modif=2714 #dist=3814 sum_values=21.436393955580577 avg=0.005620449385312159 [bellman_distances] iteration=4 modif=5352 #dist=7136 sum_values=67.61389258158759 avg=0.009475041000783014 [bellman_distances] iteration=5 modif=4934 #dist=7140 sum_values=63.907784995637684 avg=0.008950670167456258 [bellman_distances] iteration=6 modif=4524 #dist=7140 sum_values=61.71585793972974 avg=0.008643677582595202 [bellman_distances] iteration=7 modif=4032 #dist=7140 sum_values=60.16494600016438 avg=0.008426463025233106 [bellman_distances] iteration=8 modif=3538 #dist=7140 sum_values=58.65108198958743 avg=0.008214437253443618 [bellman_distances] iteration=9 modif=3064 #dist=7140 sum_values=57.23220051767171 avg=0.008015714358217326 [bellman_distances] iteration=10 modif=2676 #dist=7140 sum_values=55.93916546577031 avg=0.007834617012012648 [bellman_distances] iteration=11 modif=2220 #dist=7140 sum_values=54.8619203668688 avg=0.007683742348300953 [bellman_distances] iteration=12 modif=1850 #dist=7140 sum_values=53.88565811083889 avg=0.007547010939893402 [bellman_distances] iteration=13 modif=1518 #dist=7140 sum_values=53.10678224301025 avg=0.007437924683894993 [bellman_distances] iteration=14 modif=1172 #dist=7140 sum_values=52.44868349843554 avg=0.007345753991377527 [bellman_distances] iteration=15 modif=880 #dist=7140 sum_values=51.93813330975093 avg=0.007274248362710215 [bellman_distances] iteration=16 modif=652 #dist=7140 sum_values=51.60396788188214 avg=0.007227446482056322 [bellman_distances] iteration=17 modif=494 #dist=7140 sum_values=51.42044975004631 avg=0.007201743662471472 [bellman_distances] iteration=18 modif=360 #dist=7140 sum_values=51.229579334128026 avg=0.007175011111222413 [bellman_distances] iteration=19 modif=272 #dist=7140 sum_values=51.12190399874062 avg=0.007159930532036502 [bellman_distances] iteration=20 modif=168 #dist=7140 sum_values=51.05549678560144 avg=0.007150629801904964 [bellman_distances] iteration=21 modif=130 #dist=7140 sum_values=51.00300138561965 avg=0.007143277504988746 [bellman_distances] iteration=22 modif=84 #dist=7140 sum_values=50.980044318294766 avg=0.0071400622294530485 [bellman_distances] iteration=23 modif=44 #dist=7140 sum_values=50.96567438582126 avg=0.007138049633868524 [bellman_distances] iteration=24 modif=20 #dist=7140 sum_values=50.95015411488475 avg=0.007135875926454446 [bellman_distances] iteration=25 modif=18 #dist=7140 sum_values=50.940511485236094 avg=0.007134525418100293 [bellman_distances] iteration=26 modif=12 #dist=7140 sum_values=50.93584369169428 avg=0.007133871665503401 [bellman_distances] iteration=27 modif=12 #dist=7140 sum_values=50.93584369169428 avg=0.007133871665503401 [bellman_distances] iteration=28 modif=14 #dist=7140 sum_values=50.93584369169428 avg=0.007133871665503401 [bellman_distances] iteration=29 modif=6 #dist=7140 sum_values=50.93584369169428 avg=0.007133871665503401 [bellman_distances] iteration=30 modif=0 #dist=7140 sum_values=50.93584369169428 avg=0.007133871665503401 [best_euler_path] degrees and distances between odd vertices [best_euler_path] matching #odd=34, #odd_dist=1122 [best_euler_path] build solution [best_euler_path] order edges to get the path #edges=161 [best_euler_path] done. .. parsed-literal:: ('distance', 0.17361084069482008) .. code:: ipython3 from ensae_projects.challenge.city_tour import euler_path plot_streets_network(edges_index, edges, vertices, shapes, order=solution, figsize=(20,20)); .. image:: city_tour_long_solution_11_0.png Level 3 ------- .. code:: ipython3 from ensae_projects.datainc.data_geo_streets import seattle_streets_set_level3 edges_index, edges, vertices, distances = seattle_streets_set_level3(shapes, records) # We skip display as it takes some time # folium_html_street_map(edges_index, shapes, html_width="80%", zoom_start=14) .. code:: ipython3 from ensae_projects.challenge.city_tour import best_euler_path if False: # Be prepared, it is quite long, the bellman implementation has to be improved. couples, solution, distance = best_euler_path(edges_index=edges_index, edges=edges, distances=distances, vertices=vertices, fLOG=print) "distance", distance