The Village Problem With a VPython Solution

Village problem? Is that even the correct name? Who knows? Here is the puzzle:

There are four villages arranged such that they occupy the 4 corners of a perfect square. What arrangement of roads could you create that would allow access to all the villages but have the shortest total road length?

Instead of drawing a picture of the problem, let me just show you this excellent video with the solution.

http://www.youtube.com/watch?v=dAyDi1aa40E Very cool. There is just one problem. I don't have one of those soap bubble things. Is it possible to use VPython instead? I don't know, but I am going to try it out. Instead of using soap, I will use springs. Here is the plan:

• Have four fixed points for the villages.
• Create 2 "node" masses for the intersection points. Yes, I know I already know the answer here, but I need to start somewhere.
• Create springs between the nodes and the villages. I will use springs that have zero natural length (so any length with create a stretch).
• If I don't put in a dampening force, the node-masses will just oscillate all over the place.

Ok, here is my first try.

The displayed number is a calculation of the total length of the roads. Also, notice that I have the two nodes starting at random locations. The final length value for this run was 2.736. This is pretty close to the predicted minimum road length of 1 + sqrt(3) = 2.732. Is it not exact because of rounding error? Is it not exact because I didn't let the simulation run long enough? Or maybe it isn't exact because this method is not legit. One thing that bothers me is that all the springs are stretched the same.

What if the springs don't have a natural length (unstretched length) of zero distance units? What if they are naturally 1/2 the length of the square? Would I get the same result? How about I find out.

Here is the final state with a spring length of s/2 - sorry, no animated gif for this one.

As I increase the starting spring length, the final path length also goes up. This suggests that either "zero" is the best spring length, or this method doesn't quite work. I am going to go with "doesn't quite work". Think about it this way. What happens as I let my springs settle down? The whole system loses energy (since there is a drag term in there). At the end, the nodes are stationary so they have to be at the lowest energy (or at least lower than when they started). This energy is just in the form of spring potential energy.

Energy and Real Springs

If the springs are "Hooke's law springs", then the magnitude of the force and the spring potential energy would be:

Where k is the spring constant and s is the amount the spring is either compressed or stretched. So, if I use "zero-length" springs, at the end of the simulation the spring potential energy will be proportional to the square of the total distance.

Here is a plot of both the spring potential energy and the length of the path over time during the simulation.

Here the blue curve represents the length. It might be difficult to tell, but these two functions aren't just shifted vertically. Here is another view. In this case, I shifted the potential up so that it was near the length curve (and this doesn't show the whole simulation, just part of it).

So, key point: energy and length are not the same. I should not expect that the minimum energy would be the same as the minimum length.

Non-Real Springs

Ok, what if I make the energy proportional to the length? Suppose I make the spring potential energy look like this:

But if I have that for the potential, the force would have to be different. In one dimension, the force should be the negative derivative of the potential with respect to distance. Like this:

So, I would have to replace my "springs" with something that just exerts a constant force. Ok. Let's do it. Here is the final shot of the same simulation but with constant force spring-things.

BOOM. That looks like a much better answer. Much closer to 1 + sqrt(3).

4 Nodes

I am still not happy though. Why? Because I cheated. Cheated. I cheated by knowing that there were two nodes. I shouldn't cheat. Ok, here is my new plan. I will make 4 nodes. I will start with the following setup:

Yes. More nodes, more springs.

Here is my first run with the 4 nodes (the final state):

In case you can't tell, it works. Well, it didn't give the same minimum path length. Why? I have no way for nodes to merge together. They want to stay apart since each node is separated by a constant for spring-thing. This means that they will always be pushing apart. The only way to get zero is to have the other springs pushing them together.

Even from an energy perspective, the spring-thing still has a length so it still has energy. This will not work the way it is right now.

How could I fix it? Here are my thoughts:

• What if I made the spring-thing constant inversely proportional to the distance? As nodes got closer together, they would push less. The problem is that this would no longer have a potential energy that is proportional to the distance.
• Vanishing nodes. What if the nodes vanish if they get close enough to another node. The problem would be dealing with the springs that were connected to that now vanished node.
• I guess I could keep nodes when they get close, but just make the spring-thing constant go to zero. Not sure if this would work.

I think the real solution would be to have a whole bunch of nodes. Make it so that each node continually connects to those nodes near it and disconnects from those that are far away. This seems to be what the soap film is doing.

Maybe I will put this project on my "project shelf" and come back to it later.