Category: Computer Science

Watching whales well – the travelling salesman problem

An aerial photograph of São Miguel lighthouse in the Azores showing the surrounding tree-covered cliff and winding road.

by Paul Curzon, Queen Mary University of London

Photograph of a whale's tail emerging from the deep blue sea with a tree-covered cliff behind it.
Whale tail photograph by Kevin O’Leary from Pixabay

Sasha owns a new tour company and her first tours are to the Azores, a group of volcanic islands in the Atlantic Ocean, off the coast of Portugal. They are one of the best places in the world to see whales and dolphins, so lots of people are signing up to go.

Sasha’s tour as advertised is to visit all nine islands in the Azores: São Miguel, Terceira, Faial, Pico, São Jorge, Santa Maria, Graciosa, Flores and Corvo. The holidaymakers go whale watching as well as visiting the attractions on each island, like swimming in the lava pools. Sasha’s first problem, though, is to sort out the itinerary. She has to work out the best order to visit the islands so her customers spend as little time as possible travelling, leaving more for watching whales and visiting volcanos. She also doesn’t want the tour to go back to the same island twice – and she needs it to end up back at the starting island, São Miguel, for the return flight back home.

Trouble in paradise

It sounds like it should be easy, but it’s actually an example of a computer science problem that dates back at least to the 1800s. It’s known as ‘The Travelling Salesman Problem’ because it is the same problem a salesman has who wants to visit a series of cities and get back to base at the end of the trip. It is surprisingly difficult.

It’s not that hard to come up with any old answer (just join the dots!), but it’s much tougher to come up with the best answer. Of course a computer scientist doesn’t want to just solve one-off problems like Sasha’s but to come up with a way of solving any variant of the problem. Sasha, of course, agrees – once she’s sorted out the Azores itinerary, she then needs to solve similar problems, like the day trip round São Miguel. Her customers will visit the lakes, the tea factory, the hot spring-fed swimming pool in the botanic gardens and so on. Not only that, once Sasha’s done with the Azores, she then needs to plan a wildlife tour of Florida. Knowing a quick way to do it would help her a lot.

The long way round

An aerial photograph of São Miguel lighthouse in the Azores showing the surrounding tree-covered cliff and winding road.
Photo of São Miguel lighthouse Image by Vianney Dugrain from Pixabay

No one has yet come up with a good way to solve the Travelling Salesman problem though and it is generally believed to be impossible. You can find the best solution in theory of course: just try all the alternatives. Sasha could first work out how long it is if you go São Miguel, Terceira, Faial, Pico, São Jorge, Santa Maria, Graciosa, Flores, Corvo and back to São Miguel, then work out the time for a different order, swapping Corvo and Flores, say. Then she could try a different route, and keep on till she knew the length of every variation. She would then just pick the best. Trouble is, that takes forever.

Even this small problem with only 9 islands has over 20 000 solutions to check. Go up to a tour of 15 destinations and you have 43 billion calculations to do. Add a few more and it would take centuries for a fast computer running flat out to solve it. Bigger still and you find the computer would have to run for longer than the time left before the end of the universe. Hmmm. It’s a problem then.

Be greedy

The solution is not to be such a perfectionist and accept that a good solution will have to be good enough even though it may not be the absolute best. One way to get a good solution is called using a ‘greedy’ algorithm. You start at São Miguel and just go from there to the nearest island, from there to the nearest island not yet visited, and so on till you have done them all. That would probably work well for the Azores as they are in groups, so visiting the close ones in each group together makes sense. It doesn’t guarantee the best answer in all cases though.

Or just go climb a hill

Another way is to use a version of ‘hill climbing’. Here you take any old route and then try and optimise it, by just making small changes – swapping pairs of legs over, say: instead of going Faial to Pico and later Corvo to Flores try substituting Pico to Flores and Faial to Corvo, with the rest the same but in the opposite order. If the change is an improvement keep it and make later changes to that. Otherwise stick with the original. Either way keep trying changes on the best solution you’ve found so far, until you run out of time.

So Sasha may want to run a great tour company but there may not be enough time in the universe for her tours to be guaranteed perfect…unless of course she keeps them very small. After all, just visiting São Miguel and Terceira makes a great holiday anyway.

This article was originally published on the CS4FN website and a copy can also be found on pages 14-15 of issue 10 of the CS4FN magazine, which you can downloads as a PDF below. All of our free material can be downloaded here.

Related Magazine …

This blog is funded through EPSRC grant EP/W033615/1.

Cyber Security at the Movies: Guardians of the Galaxy (Fail Secure security)

by Paul Curzon, Queen Mary University of London

[Spoiler Alert]

Guardians of the Galaxy Poster

If you are so power hungry you can’t stand the idea of any opposition; if you want to make a grab for total power, so decide to crush everyone in your way, then you might want to think about the security of your power supply first. Luckily, all would-be dictators who crush everyone who gets in their way as they march towards total domination of the galaxy, tend to be very naive about cyber-security.

Take Ronan the Accuser in the original Guardian of the Galaxy film. He’s a villain with a religious streak, whose belief that strength is virtue and weakness is sin leads to his totally corrupted morality. To cut to the guts of the story he manages to get the “Infinity Stone” that gives unimaginable power to its owner. With it he can destroy anyone who gets in his way so sets out to do so.

Luckily for the Galaxy, good-guy Peter Quill, or Star-Lord as he wants to be known, and his fellow Guardians have a plan. More to the point they have Gamora. She is an assassin originally sent to kill Quill, but who changes sides early on. She is an insider who knows how Ronan’s security system works, and it has a flaw: its big, heavy security doors into his control room.

Security Lesson 1. It should still be secure even when the other side know everything about how it works. If your security relies on no one knowing, its almost certainly bad security!

Once inside his ship, to get to Ronan the Guardians will need to get through those big heavy security doors. Now once upon a time big, heavy doors were locked and barred with big, heavy bolts. Even in Roman times you needed a battering ram to get in to a besieged city if they had shut the doors before you got there. Nowadays, how ever big and heavy the door, you may just need some cyber skills to get in if the person designing it didn’t think it through.

Electromagnetic locks are used all over the place and they give some big advantages, such as the fact that they mean you can program who is and isn’t allowed entry. Want to keep someone out – you can just cancel their keycard in the system. They are held locked by electromagnets: magnets that are switched on and off using an electric current. That means computers can control them. As the designer of an electromagnetic lock you have a choice, though. You can make them either “fail safe” or “fail secure”. With a fail safe lock, when the power goes, the doors automatically unlock. With fail secure, instead they lock. Its just a matter of whether the magnet is holding the door open or closed. Which you choose when designing the lock depends on your priorities.

Fail safe is a good idea, for example, if you want people to be able to escape in an emergency. If a fire cuts the electricity you want everyone to still be able to get out, not be locked in with no chance of escape. Fail secure on the other hand is good if you don’t want thieves to be able to get in just by cutting the power. The magnets hold the bolts open, so when the power goes, the spring shut.

Security Lesson 2. If you want the important things to stay secure, you need a fail secure system.

This is Ronan’s problem. Zamora knows that if you cut the power supply then the doors preventing attackers getting to him just open! He needed a fail secure door, but instead had a fail safe one installed. On such small things are galaxies won and lost! All Zamora has to do is cut the power and they can get to him. This of course leads to the next flaw in his security system. It wouldn’t have mattered if the power supply was on the secure side of that door, but it wasn’t. Ronan locks himself in and Zamora can cut the power from the outside … Dhurr!

There is one last thing that could have saved Ronan. It needed an uninterruptible power supply.

Security Lesson 3. If your system is reliant on the power supply, whether a door, your data, your control system or your life-support system, then it should keep going even if the power is switched off.

After all, what if the space ships cleaners (you never see them but they must be there somewhere!) unplug the door lock by mistake just because they need somewhere to plug in the hoover.

The solution is simple: use an “uninterruptible power supply”. They are just very fast electricity storage systems that immediately and automatically take over if the main power cuts out. The biggest on Earth keeps the power going for a whole city in Alaska (you do not want to lose the power running your heating mid-winter if you live in Alaska!). Had Ronan’s doors had a similar system, the doors wouldn’t have just opened as the power would not have been cut off.It’s always the small details that matter in cyber security (and in successfully destroying your enemies and so ruling the universe). As with all computational thinking, you have to think about everything in advance. If you don’t look after your power supply, then you may well lose all your power over the galaxy too (and your life)!

More on …