{"id":779,"date":"2019-11-26T23:56:07","date_gmt":"2019-11-26T21:56:07","guid":{"rendered":"http:\/\/www.joanillo.org\/?p=779"},"modified":"2020-10-05T23:57:34","modified_gmt":"2020-10-05T21:57:34","slug":"ruta-pels-arbres-singulars-de-barcelona-minimitzant-la-distancia","status":"publish","type":"post","link":"https:\/\/www.joanillo.org\/?p=779","title":{"rendered":"Ruta pels arbres singulars de Barcelona (minimitzant la dist\u00e0ncia)"},"content":{"rendered":"<p><a href=\"http:\/\/www.joanillo.org\/wp-content\/uploads\/2019\/11\/Ruta_colleccio_arbres2.png\"><img loading=\"lazy\" src=\"http:\/\/www.joanillo.org\/wp-content\/uploads\/2019\/11\/Ruta_colleccio_arbres2-300x180.png\" alt=\"\" title=\"Ruta_colleccio_arbres2\" width=\"300\" height=\"180\" class=\"alignright size-medium wp-image-2100\"><\/a>El problema del viatjant de comer\u00e7 (traveling salesman problem) \u00e9s un problema cl\u00e0ssic de l&#8217;algor\u00edsmica: es tracta de passar per una s\u00e8rie de punts, sense repetir-ne cap, i minimitzant la dist\u00e0ncia recorreguda. Fa unes poques setmanes vaig importar els arbres singulars de Barcelona a OpenStreetMaps, i crec que \u00e9s una bona activitat did\u00e0ctica per con\u00e8ixer els arbres de la ciutat fer una ruta per uns quants d&#8217;aquests arbres.<\/p>\n<p>Per fer-ho m\u00e9s interessant, podem plantejar-nos el problema de fer un recorregut que minimitzi la dist\u00e0ncia, passant per tots els arbres, i que retorni al punt de partida. Vaig estar cercant diferents implementacions amb Python que resolguin el problema, fins que en vaig trobar una que satisfeia la meva restricci\u00f3 de tornar al punt de partida.<\/p>\n<p>Sobre aquesta soluci\u00f3 he fet alguna modificaci\u00f3 per tal de generar un fitxer JSON amb la soluci\u00f3. Finalment, hem de pintar sobre un mapa OSM els nostres punts (nodes); tra\u00e7ar una l\u00ednia recta entre els punts; i afegir un label-text informatiu sobre aquests punts. El resultat es pot veure en la imatge.<\/p>\n<p>Evidentment hem fet unes simplificacions: la dist\u00e0ncia m\u00ednima entre dos punts \u00e9s la l\u00ednia recta, per\u00f2 per la ciutat no podem anar en l\u00ednia recta, i a m\u00e9s poden haver-hi pujades i baixades. Per\u00f2 com a exercici did\u00e0ctic crec que \u00e9s interessant.<\/p>\n<p>Aqu\u00ed Catalunya s\u00f3n populars les Curses d&#8217;Orientaci\u00f3. Crec que es podria aprofitar aquestes activitats en el lleure i afegir-hi una capa de coneixement, com ara con\u00e8ixer els arbres, con\u00e8ixer monuments, etc. Crec que per als joves i infants pot ser una activitat engrescadora.<\/p>\n<p>Refer\u00e8ncies:<\/p>\n<ul>\n<li><a href=\"http:\/\/wiki.joanillo.org\/index.php\/Traveling_Salesman_problem_i_arbres_singulars_de_Barcelona\" title=\"Entrada a la wiki\" target=\"_blank\" rel=\"noopener noreferrer\">Entrada a la wiki<\/a><\/li>\n<li><a href=\"https:\/\/github.com\/Forceflow\/Ambiance_TSP\" title=\"Soluci\u00f3 TSP Python\" target=\"_blank\" rel=\"noopener noreferrer\">Soluci\u00f3 TSP Python<\/a><\/li>\n<li><a href=\"https:\/\/openlayers.org\/en\/latest\/apidoc\/module-ol_source_OSM-OSM.html\" title=\"Openlayers\" target=\"_blank\" rel=\"noopener noreferrer\">Openlayers<\/a><\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Travelling_salesman_problem\" title=\"Traveling Salesman Problem\" target=\"_blank\" rel=\"noopener noreferrer\">Traveling Salesman Problem<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>El problema del viatjant de comer\u00e7 (traveling salesman problem) \u00e9s un problema cl\u00e0ssic de l&#8217;algor\u00edsmica: es tracta de passar per una s\u00e8rie de punts, sense repetir-ne cap, i minimitzant la dist\u00e0ncia recorreguda. Fa unes poques setmanes vaig importar els arbres singulars de Barcelona a OpenStreetMaps, i crec que \u00e9s una bona activitat did\u00e0ctica per con\u00e8ixer [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[16,44,36,40],"tags":[],"_links":{"self":[{"href":"https:\/\/www.joanillo.org\/index.php?rest_route=\/wp\/v2\/posts\/779"}],"collection":[{"href":"https:\/\/www.joanillo.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.joanillo.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.joanillo.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.joanillo.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=779"}],"version-history":[{"count":1,"href":"https:\/\/www.joanillo.org\/index.php?rest_route=\/wp\/v2\/posts\/779\/revisions"}],"predecessor-version":[{"id":780,"href":"https:\/\/www.joanillo.org\/index.php?rest_route=\/wp\/v2\/posts\/779\/revisions\/780"}],"wp:attachment":[{"href":"https:\/\/www.joanillo.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=779"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joanillo.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=779"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joanillo.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=779"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}