This is partly the result of an unfortunate exchange on Worldbuilding Meta:

@HDE226868 hahahaha. No math allowed. – James yesterday

I shall find a way! – HDE 226868 yesterday

I think I have.

This is sort of based off of the travelling salesman problem, where the object is to find the shortest distance between a given number of points. This is, as mathematicians quickly found out, much harder than it seems.

The scenario:

In a Middle-Earth-esque world, a wizard is responsible for patrolling a network of small villages to keep the people in the area from harm. The villagers don't know about his abilities, simply that he's an eccentric old man who wanders around. They also don't want to interact with him, because they fear him - as a whole, they're pretty xenophobic.

One day, though, the wizard suffers an attack of amnesia. He remembers much of who he is, but he forgets how to get between villages the fastest way possible. He quickly realizes that there are multiple paths from one village to another, but only one is the shortest.

How can he figure out what route to travel through? He's using an approximation: Travel to the closest village he hasn't already been to.

Some restrictions:

  • He has to travel by foot.
  • He has forgotten how to use his powers, except for one: The ability to hover ten feet in the air for approximately seven seconds.

Note: I did not intend for magic to be allowed. That said, I originally didn't specify that, so I'll consider Cort Ammon's answer as perfectly fine, especially as it's quite clever. Future answers: Please don't use magic! Thank you.

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Monica Cellio Jun 19 '15 at 23:27

Any wizard who is aware they have powers should probably be very friendly to everyone he meets. You never know who you might have insulted in the past, so it's wise to make amends until you remember more.

After being friendly to everyone you meet (at least the few that will approach you), and generally trying to earn good karma, you may find a nature wizard approaches you. He politely asks why you keep jumping 10 feet in the air, because it's disturbing the chipmunks. If they don't prepare for winter, they'll starve.

You explain your desire for a path between all of the villages to the nature wizard. He starts scribbling a map and some numbers but you shake your head. You explain that you don't know why, but you're pretty certain you aren't allowed to use math. He raises an eyebrow and asks, "all math?" You shrug, and mention that you think it's probably a difficult enough task to allow one mathematical approach. You figure it'd be okay if we cheated a little, and used the compass and straightedge you have conveniently handy to square the circle if it'd help as part of the solution, but that's all the cheating you can allow. Alas, you've forgotten how to square the circle, so it may not be all that helpful of a cheat.

The nature wizard claps his hands and smiles! "Nature does all sorts of amazing things without math!" he exclaims. He conjures some magic and ants pour forth from several ant hills. He explains the problem to the ants, and gives them a quest to find the shortest path for you!

You thank the wizard for his efforts, and he tells you to wait a few hours for the ants to explore the land and find the best path. He meanders off as you ponder just how many seven second intervals it is going to take to keep your feet off of this ant infested ground for a few hours.

Ants are astonishingly good at path finding in Euclidean spaces. In fact, they are so good, that we often emulate their pheromone based approach in our optimization algorithms; they work just that well!

| improve this answer | |
  • $\begingroup$ Isn't this kind of cheating? $\endgroup$ – HDE 226868 Jun 18 '15 at 16:40
  • $\begingroup$ @HDE226868 I don't see how it's cheating. He's answering the question you asked using a perfectly viable solution: magic. You never specified the wizard in question couldn't use resources, after all. $\endgroup$ – Frostfyre Jun 18 '15 at 16:43
  • $\begingroup$ Fine, I'll let it go. I thought the implication was clear that magic was not allowed, but I was wrong. I'll make a note of that. +1 for ingenuity. $\endgroup$ – HDE 226868 Jun 18 '15 at 16:45
  • 2
    $\begingroup$ This approach works just fine with no magic. Build a scale model and drop the ants on the model. I've seen a similar solution using water with dies in a scale model (though I don't recall how to keep the dies from mixing). $\endgroup$ – Jim2B Jun 18 '15 at 18:32
  • $\begingroup$ @Jim2B The ants are still charmed with the magic... Unless you collect the ants by hand, and somehow coax them to achieve your model's objectives in a linear order... (Is there sugar in the dyes? How do they know where to go next, or where 'home' is for that matter?) $\endgroup$ – Ayelis Jun 18 '15 at 20:17

I've just had a play around with some string and come up with this. I have no idea how well it works in all cases. It seems to work ok for the example case I had. If some one knows where I can find more information about this type of thing I would love to hear in the comments.

With that out of the way on with the show:

Using a map (he walks into the local map shop, the villager runs away, he takes the map) he finds all the villages he needs to visit.

Place a safety pin, loop or hook on each village. (I used safety pins as I had some on hand)

Run a length of string along the roads or paths between each village. Tie each end to the safety pin / loop / hook.

Add a label to each pin with the name of the village on it. The reason for this will become clear.

Your map should have some thing like this over it: Villages with string

Now pick-up the longest path. Hold it up so that the two safety pins on each end are level.

Shake out the mesh then take the lowest hanging loop and pick it up and hold it up so the pins on both ends are level with the pins from the first loop.

Repeat this operation until you have the minimum number of strings left.

Unhook the strings you are holding above the line from the mesh. This was a bit tricky keeping them all untangled.

You should now be left with a single line of safety pins linking each town. Completed path

The downsides to this method:
It takes quite a while to set up.
You need to steal a map.
It is very easy to end up with the mesh in a complete knot.
I am not convinced it will always give you the correct answer. (But it seems close)

| improve this answer | |
  • $\begingroup$ I'm not sure if it'll work, but +1 for actually building something to try it out. $\endgroup$ – Samuel Jun 18 '15 at 20:56
  • $\begingroup$ This is a great idea! Now to turn it into pseudocode.. $\endgroup$ – Josiah Jun 19 '15 at 15:00

He should use a variation of a Genetic Algorithm. This is a technique that mimics natural evolutionary paths to solve problems that are otherwise extremely difficult.

Let's say there are four villages, each with three paths of varying length between them.

The first time the wizard will pick at random: AB1 -> BC2 -> CD3 -> DA1

The next time he picks different routes: AB2 -> BD3 -> DC1 -> CA2

And the third time: AC3 -> CD2 -> DB3 -> BA1

Now he takes out all his notes, and how long it took him to take each path, and he starts combining and mixing the best routes. He discards ones that took way too long, and only keeps and mixes the patterns that were relatively quicker. Then he starts over from step 1, but with his new mixed patterns, and does this all over again several times.

Eventually he'll have a set of very good paths - they won't necessarily be optimal, but they'll be close.

| improve this answer | |
  • 4
    $\begingroup$ A point I almost wrote an entire answer for: The wizard does not actually want the optimal path even if one exists. Always checking points at the same order and roughly the same rate is bad idea when doing patrol over a long period. It makes you less alert, allows intelligent enemies predict you, and may cause weird interactions with other things with regular period. So having several good paths and varying between them or their combinations is actually better than the optimal path. Always walking the same path will also make you look pretty weird to the villagers. $\endgroup$ – Ville Niemi Jun 18 '15 at 16:01

A simple algorithm that I use for relatively small number of stops is this:

  1. Find the distance from each town to every other town.
  2. Take the town whose shortest distance to another is the largest in the group - designate this as town 1.
  3. Select its shortest route to the next town -designate this town 2.
  4. From town 2 select the route to the closest unvisited town.
  5. Repeat step 4 as necessary

This doesn't give the optimal answer but it does give a good one. If the number of towns is smaller (say <10), then it is sometimes obvious how to shorten the route.

It turns out that my self-developed approach is a variant of the minimum spanning tree approach.

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.