On 2 Mar 2011, at 23:02, Fred lunnon wrote:
This construction reminds me of the SWASC (Sealing Wax And String Computer) I concocted for an undergraduate course in algorithmics: to find the shortest path on a graph, first join up a bunch of strings cut to lengths representing roads, using wax blobs for the towns; then hold the start blob and finish blob in two hands and pull (but not too hard!).
This device finds any desired shortest path in constant time --- in contrast to (say) Dijkstra's algorithm, which costs time around n log n for n towns. But SWASC will never catch on because of the excessive resources required to configure / build your "computer" in the first place. These might just be worthwhile when the map is fixed and many routes are required --- but in the case of a single maze solution, it's hard to see how they could be justified.
Furthermore, claims for the performance of analogue methods depend on speed of component settling --- the authors give no indication of how fast current devices might be expected to operate. Compare "DNA" computers. [Note that Gene Salamin's suggestion for fabrication has not been copied to Jon Cartwright.]
Fred Lunnon
Is it possible to model the physics of pulling the blobs apart and get a constant-time algorithm? But probably the physical simulation would get equally nonlinear as the original problem, requiring lots of decisions and having no advantage. ??
Steve Gray