You are currently browsing the tag archive for the ‘Portugal’ tag.
Images – Portugal (1A – top left, original input satellite image below), geodesically stretched by one of my Mathematical Morphology algorithms, in order to represent real travel times from each of the 18 regional districts in Portugal, to the rest of the territory. From the 18, three capital districts are represented here. As departing from Lisbon (1B – top right), from Faro (1C – South of Portugal, bottom left), and from Bragança (1D – North-East region, bottom right). [World Exposition, Lisbon, Territory pavilion, 1998].
Recently one of my colleagues who knows I love maps, pointed me to an old TV show “Câmara Clara“, a cultural TV show by RTP2, at one of the main public Portuguese TV stations. Main reason for my interest was his current theme: Maps. My second reason was their guests: Joaquim Ferreira do Amaral (an ex-Minister with a passion for maps) and Manuel Lima, which wonderful work on information visualization I know for a long time (on one of my past posts I referred to one of his ongoing working sites: visualcomplexity).
For my complete and positive surprise, their interview ended with some new examples, being one of my old works referred (from 57m 12s up to 60m 26s on http://camaraclara.rtp.pt/#/arquivo/131 ). It’s a long story on how I ended doing these kind of maps. Part of it, it’s here. During 1998, the World Exposition was in Portugal, and I got invited to present a set of 18 different maps from the Portuguese territory. So I decided to geodesically stretch the travel distances from any of the 18 different capital districts, to the rest of the territory, in order to represent travel Time not Distance, or Distance as time. For that, I have coded new algorithms based on Mathematical Morphology (MM), taking in account every road (from main roads to regional, check some images below), from which I applied different MM operators.
Unfortunately, many of those maps are now lost. I did tried hard to find them from my old digital archives, but only found those above, which represent the departure from Lisbon (the Capital), Faro and Bragança. So, if by any reason you happen to have some photos from the 1998’s World Exposition in Lisbon, inside the Territory pavilion, I would love to receive them.
Video (LINK) – “Câmara Clara” TV show by journalist Paula Moura Pinheiro dedicated to maps (nº 131), at one of the main public Portuguese TV stations (RTP2), broadcasted on May 3 2009, in Portuguese.
A sketchy summary of this TV program went on something like this (the poor translation is mine): At the year Google promises to launch his first and exhaustive world-wide open-access digital cartography of the African continent, Joaquim Ferreira do Amaral, passioned by the Portuguese World Discover History and collector of historical maps, joins as guest with Manuel Lima, the Portuguese information designer that recently Creativity magazine has considered one of the top bright minds along with Google and Amazon founders, debating the importance of “navigating” reality with a map. From the Portuguese cartographic history, know to be the best in the XV and XVI centuries, up to the actual state-of-the-art in this area, from which Manuel Lima is considered to be one of the top researchers at global scale.
Fig.1 – (click to enlarge) The optimal shortest path among N=1265 points depicting a Portuguese Navalheira crab as a result of one of our latest Swarm-Intelligence based algorithms. The problem of finding the shortest path among N different points in space is NP-hard, known as the Travelling Salesmen Problem (TSP), being one of the major and hardest benchmarks in Combinatorial Optimization (link) and Artificial Intelligence. (V. Ramos, D. Rodrigues, 2012)
This summer my kids just grab a tiny Portuguese Navalheira crab on the shore. After a small photo-session and some baby-sitting with a lettuce leaf, it was time to release it again into the ocean. He not only survived my kids, as he is now entitled into a new World Wide Web on-line life. After the Shortest path Sardine (link) with 1084 points, here is the Crab with 1265 points. The algorithm just run as little as 110 iterations.
Fig. 2 – (click to enlarge) Our 1265 initial points depicting a TSP Portuguese Navalheira crab. Could you already envision a minimal tour between all these points?
As usual in Travelling Salesmen problems (TSP) we start it with a set of points, in our case 1084 points or cities (fig. 2). Given a list of cities and their pairwise distances, the task is now to find the shortest possible tour that visits each city exactly once. The problem was first formulated as a mathematical problem in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods.
Fig. 3 – (click to enlarge) Again the shortest path Navalheira crab, where the optimal contour path (in black: first fig. above) with 1265 points (or cities) was filled in dark orange.
TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources or time windows make the problem considerably harder.
What follows (fig. 4) is the original crab photo after image segmentation and just before adding Gaussian noise in order to retrieve several data points for the initial TSP problem. The algorithm was then embedded with the extracted x,y coordinates of these data points (fig. 2) in order for him to discover the minimal path, in just 110 iterations. For extra details, pay a visit onto the Shortest path Sardine (link) done earlier.
Fig. 4 – (click to enlarge) The original crab photo after some image processing as well as segmentation and just before adding Gaussian noise in order to retrieve several data points for the initial TSP problem.
Fig.1 – (click to enlarge) The optimal shortest path among N=1084 points depicting a Portuguese sardine as a result of one of our latest Swarm-Intelligence based algorithms. The problem of finding the shortest path among N different points in space is NP-hard, known as the Travelling Salesmen Problem (TSP), being one of the major and hardest benchmarks in Combinatorial Optimization (link) and Artificial Intelligence. (D. Rodrigues, V. Ramos, 2011)
Almost summer time in Portugal, great weather as usual, and the perfect moment to eat sardines along with friends in open air esplanades; in fact, a lot of grilled sardines. We usually eat grilled sardines with a tomato-onion salad along with barbecued cherry peppers in salt and olive oil. That’s tasty, believe me. But not tasty enough however for me and one of my colleagues, David Rodrigues (blog link/twitter link). We decided to take this experience a little further on, creating the first shortest path sardine.
Fig. 2 – (click to enlarge) Our 1084 initial points depicting a TSP Portuguese sardine. Could you already envision a minimal tour between all these points?
As usual in Travelling Salesmen problems (TSP) we start it with a set of points, in our case 1084 points or cities (fig. 2). Given a list of cities and their pairwise distances, the task is now to find the shortest possible tour that visits each city exactly once. The problem was first formulated as a mathematical problem in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. In many applications, additional constraints such as limited resources or time windows make the problem considerably harder. (link)
Fig. 3 – (click to enlarge) A well done and quite grilled shortest path sardine, where the optimal contour path (in blue: first fig. above) with 1084 points was filled in black colour. Nice T-shirt!
Even for toy-problems like the present 1084 TSP sardine, the amount of possible paths are incredible huge. And only one of those possible paths is the optimal (minimal) one. Consider for example a TSP with N=4 cities, A, B, C, and D. Starting in city A, the number of possible paths is 6: that is 1) A to B, B to C, C to D, and D to A, 2) A-B, B-D, D-C, C-A, 3) A-C, C-B, B-D and D-A, 4) A-C, C-D, D-B, and B-A, 5) A-D, D-C, C-B, and B-A, and finally 6) A-D, D-B, B-C, and C-A. I.e. there are (N–1)! [i.e., N–1 factorial] possible paths. For N=3 cities, 2×1=2 possible paths, for N=4 cities, 3x2x1=6 possible paths, for N=5 cities, 4x3x2x1=24 possible paths, … for N=20 cities, 121.645.100.408.832.000 possible paths, and so on.
The most direct solution would be to try all permutations (ordered combinations) and see which one is cheapest (using computational brute force search). The running time for this approach however, lies within a polynomial factor of O(n!), the factorial of the number of cities, so this solution becomes impractical even for only 20 cities. One of the earliest and oldest applications of dynamic programming is the Held–Karp algorithm which only solves the problem in time O(n22n).
In our present case (N=1084) we have had to deal with 1083 factorial possible paths, leading to the astronomical number of 1.19×102818 possible solutions. That’s roughly 1 followed by 2818 zeroes! – better now to check this Wikipedia entry on very large numbers. Our new Swarm-Intelligent based algorithm, running on a normal PC was however, able to formulate a minimal solution (fig.1) within just several minutes. We will soon post more about our novel self-organized stigmergic-based algorithmic approach, but meanwhile, if you enjoyed these drawings, do not hesitate in asking us for a grilled cherry pepper as well. We will be pleased to deliver you one by email.
p.s. – This is a joint twin post with David Rodrigues.
Fig. 4 – (click to enlarge) Zoom at the end sardine tail optimal contour path (in blue: first fig. above) filled in black, from a total set of 1084 initial points.
Chemoton § Vitorino Ramos' research notebook 
Recent Comments