rpjday@watrose.UUCP (rpjday) (10/17/86)
In article <8194@watrose.UUCP> rpjday@watrose.UUCP (rpjday) writes: > > I am interested in collecting examples of problems in the area of >computation that are generally acknowledged to be reasonably to >obscenely difficult using the digital computer model, but which have >simple elegant solutions if one was allowed to construct some form >of "analog" computer. > As an example, the problem of finding the shortest path between two >points in a graph is easily solved if one is allowed to build a string >model of the graph, then pick it up by the source node, and measure the >distance straight down to the target node. I'm sure everyone is familiar >with this trick, but I'm also sure there were other "analog" models >of computation, some for supposedly intractable problems. > ... >R Day > And then the flames came pouring in ... ACK!! I'm sorry if what I was asking for was completely misunderstood. It seems that the juxtaposition of the two paragraphs made it appear that I considered the 2-node shortest path problem to be "obscenely difficult." No, no, no! I just wanted to give an example of a simple analog model that could be used for solving a simple problem, even if I did screw it up, OK? The statement immmediately following makes it, I thought, quite clear that this idea could be extended to deal with intractable problems. I'm not concerned with the difficulty of building the damned thing, either! It's supposed to be a mental exercise, mathematical recreation, FUN! Jeez, sometimes you people can be so serious ;-). Another problem (somewhat harder than the shortest path problem, I believe) is to find the LONGEST path between two vertices, no duplicate vertices in the path, that is. One technique mentioned is to grab the two nodes and stretch them apart, allowing the taut strings to break until there remains only one path connecting the two points. Sounds good, right? Doesn't always work, though. I'll let you think about why not. Have a good one. ______________________________________________________________________ R Day rpjday@watrose.uucp CS Department rpjday%watrose@waterloo.csnet U. of Waterloo rpjday%watrose%waterloo.csnet@csnet-relay.arpa