Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have realized that its possible to create algorithms that operate physically to solve problems much more efficiently than in a computer itself. Consider the following:

Finding the shortest path between 2 points in a connected graph. If one were to physically create the graph with the edge weights correspond to length of physical connectors and the nodes something corresponding ex: wooden balls and yarn both labeled, then it is possible to generate the graph from data in O(N) time and then determining the shortest path between 2 nodes would simply involve grabbing both those nodes and pulling them so a straight line forms between them (or multiple straight lines!) and the rest hanging. That straight line(s) would be the shortest path for obvious reasons.

How exactly does one take this physical method of solving the problem and implement it in a computer?

share|improve this question
    
No. The solution to the shortest-path problem you gave is only an approximation when the distance between the destination and origin is very large compared to the distance between the nodes, and the distribution of the nodes is more-or-less uniform. In fact it is probably a very common approximation, implemented by Google Maps & Co. It is easy to contrive geometric shapes that will fail your yarn-and-string algorithm and produce pathological solutions. –  user54609 Apr 10 '13 at 1:43
    
How so? If there is a solution, then there is a shortest path, (I assume the weights are on the edges and not the nodes) in which case every edge with a weight W can be transformed into a thread connected nodes with length W units (Ex: W inches) now the goal is simply to pull on the 2 target nodes, putting tension on the system, with the shortest path being the one that straightens out the quickest, the rest of the nodes hanging –  frogeyedpeas Apr 10 '13 at 1:45
    
Hmm. If you think about it, naively applying your algorithm will result in the path that goes closest to the straight line. This isn't necessarily the shortest (consider a box with a very loopy path directly through it, versus going around the box) –  user54609 Apr 10 '13 at 1:49
    
If you mean stringing huge amounts of strings and testing which straightens out the quickest, then you need all those strings, which isn't O(n) but something huge. If you test paths one by one using the string and recording the length, you still have a huge time complexity. –  user54609 Apr 10 '13 at 1:50
1  
For small examples it may seem to be an advantage, but what do you do for a graph with e.g. 100 million nodes, where all distances are close to each other? –  Cristina Apr 10 '13 at 7:29

6 Answers 6

In "physical" algorithm you use massive parallelism of the nature.

Without going to molecular level every node and connector movement is "calculated" in parallel. To get the same speed you would need a computer with too big number of CPU cores and extremely fast communication between them.

So I would say: no, usually direct mapping of physical algorithm to computer does not provide a fast algorithm.

share|improve this answer

What you're describing is an analog computer. These used to be actually built for certain purposes and old CS books had chapters devoted to them. These chapters got shorter over time and eventually disappeared, as did the machines. The problem is that analog computers

  • don't scale well
  • are very limited in the precision of results they can give
  • are very inflexible (they have to be built for a specific, relatively narrow purpose)

As for "Transforming A Physical Algorithm into a Computerized One" - that's not possible, because the core of the analog computer is not an algorithm at all - it's just using the laws of physics operating continuously on a mechanism, while an algorithm consists of discrete steps.

There's a reason that physical simulations are some of the most demanding applications for supercomputers, for which you can essentially never have enough computing power.

share|improve this answer
    
Would it be possible to build a computer then that is able to operate continuously? If our laws of physics can operate continuously there might be some way to do the same on a computer I would hope. –  frogeyedpeas Apr 10 '13 at 14:00
1  
Your big bunch of knotted yarn is that computer. It has the drawbacks I've listed above. –  Michael Borgwardt Apr 10 '13 at 14:10

Lets analyse the physical solution in more detail.

First construction of the graph is going to be O(E+V) as you have to tie each edge to each connected node (E is number of edges, V number of vertices on a well connected graph this will be O(E)). In terms of complexity this will be the same as constructing a graph is software, but we can already imagine that the constant factors will be much larger for string tying.

Second pulling the start and end nodes does not give you the answer instantaneously, the force must propagate along the shortest path, so we can select the answer in O(L) where L is the length of the shortest path, this still looks quite good though, and that is because the force propagates in parallel. However we still have other problems here, if there are two paths that are very similar length then it will be hard to choose between them as the finite width of your strings and knots will mean they are both under tension.

Lastly lets look at scale. All your strings have a physical mass, and maximum tensile strength. Assuming we have steel wire we have a breaking length of 25.9 km. In the worst case your shortest path is 3 nodes with all other edges/nodes hanging off the middle node so this will mean (in steel) the maximum length of all the wire in your graph will be about 25.9 km. given the high constant factor in construction this may mean there are very few or even no graphs for which it is both possible and quicker to solve the shortest path problem physically.

Converting to a computer solution, if we network V hardware nodes with E message channels such that the time to propagate a message along a channel is the weight of an edge, I think we can again see that if we can send message in parallel along all edges we can find the shortest path in O(L) time. And this I think demonstrates the key issue, you are using O(E+V) hardware to do this, if we convert this to software on O(1) hardware in the straight forward way then the algorithm becomes O(L+E+V) as we now have to simulate all our hardware in series. We can now see this is worse than the usual algorithms.

share|improve this answer

I think this is what OP's talking about:

http://i.stack.imgur.com/wE2th.png

You can almost instantly find the shortest path in real life, but I'm not sure how well this would work with a computer- You could assign a tension value to every node attached to the endpoints, and then to each of the nodes attached to each of those nodes, and so on, but I'm pretty sure other methods would be faster.

Simulating physics for each node would probably take much longer than just finding the distance of each node to the two endpoints.

share|improve this answer
    
Is there any computer that can basically perform tasks on all its datastructures simaltaneously? Not threaded but like in real life. If you drop 100 rocks off a cliff they all fall at the same time as opposed to one after the other and as far as we know there is no ordering, its continuous. Can this same effect be done a computer? –  frogeyedpeas Apr 10 '13 at 14:02

There is no such thing as a distinction between a "physical" algorithm and a "computerized" one - the truth of the matter is that an algorithm is a completely conceptual idea or formula. Computers are capable of doing the exact same subset of calculations that human brains can do, no more and no less - speed is the only real difference. As such, any formula you have for doing something physically has an equivalent that can be programmed, and visa-versa. This is the "Computers are Not Magic" principle that all computer science students should come to accept.

I would believe that the typical shortest path algorithm you're familiar with IS functionally equivalent to your rope method, and that you are not taking into account the relative complexity of how choosing the various balls and dropping them would equate to the checks that a computer would perform.

share|improve this answer
    
If you're going to make a bold statement like computers are capable of doing the exact same subset of calculations the human brains can do you should back it up with evidence. –  Caleb Apr 10 '13 at 14:59
1  
@Caleb Don't mistake my comment for some sort of wild claim. I am only stating a fundamental principle of computers: that they operate using (only) human-conceivable algorithms, and that is theoretically possible to model any conceived algorithm using a computer. Accepting this is important to "demystify" computers, and understand that they won't do anything conceptually different than a human following step-by-step instructions would. –  Southpaw Hare Apr 10 '13 at 16:03

How exactly does one take this physical method of solving the problem and implement it in a computer?

The sequential nature of digital computers prevents them from perfectly mimicking many physical operations, so there's not always a useful way to implement physical algorithms in software.

Spaghetti sort is a classic example of a physical operation that can't be implemented in software with the same performance. The idea is that you represent a set of numbers by cutting pieces of dry spaghetti to lengths that correspond to each number in the set. You then gather the spaghetti in your hand and lower the bundle against a surface so that the ends are all aligned. It's then a simple matter to remove pieces from the bundle one at a time, starting with the longest. Performance is O(n) because time to cut the spaghetti strands and time to remove all the strands from the bundle are both O(n).

The software version of the spaghetti sort is selection sort, which has O(n2) performance. The reason for this is that a sequential machine like a computer is unable to evaluate all the numbers at once. Instead, it has to run through the list of numbers looking for the largest, which is itself an O(n) operation, and it has to pick the largest number n times. In the real world, we can evaluate all the spaghetti strands at once, so the selection is O(1) instead of O(n).

So, the answer to your question is that it's not always possible to convert a physical method into software and while preserving the advantages of the physical method.

share|improve this answer
    
I believe the Spaghetti sort is a flawed view due to simplification. It is not fair to say that it takes linear time to pick out strands of spaghetti, even if their relative values are in full view right in front of you - you still have to skim the group with your eyes and look at them all which, despite taking only a tiny moment, is still a linear search each time (leading to n^2 overall). It's the same reason why Bubblesort is n^2, even though it is natural to humans. You see all the "cards" in your hand and take for granted that even just looking at them is a linear process each time. –  Southpaw Hare Apr 10 '13 at 16:14
    
@SouthpawHare The linked description of the algorithm avoids your objection. You don't scan the bundle with your eyes, you lower your hand onto the bundle from above and pick the first piece that you hit. It's my description that's flawed, not the process. –  Caleb Apr 10 '13 at 16:33
    
But suppose you had a computational device that can represent this, for example when given data to sort ex: {1, 9, 7, 5, 3} the device creates 1 atom, 9 atom, etc... long strands and plates them to a grid and then scans the strands moving them in order, this should be possible, the problem is that we don't have the technology to implement physical processes so effectively –  frogeyedpeas Apr 11 '13 at 15:05
    
Well, moving n strands takes O(n) times, since you already said that: scans the strands moving them in order. You still get O(n^2) plus a whole bunch of simulation overhead for useless details about the composition of spaghetti etc. –  user54609 Apr 13 '13 at 14:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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