.. _citytour1solutionrst: ============================= Shortest city tour (solution) ============================= .. only:: html **Links:** :download:`notebook `, :downloadlink:`html `, :download:`PDF `, :download:`python `, :downloadlink:`slides `, :githublink:`GitHub|_doc/notebooks/challenges/city_tour/city_tour_1_solution.ipynb|*` Find the shortest path through a set of streets, solution of the first example. .. 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: Problem definition ------------------ .. 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="80%", zoom_start=15) .. raw:: html

We display a simplified map. .. 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_1_solution_6_0.png Eulerian path ------------- A solution is a set of indices of edges. Let’s try ``edges_index`` without one edge as a solution. .. 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_1_solution_9_0.png