Rug Burn Junky on 27/3/2008 at 17:16
Quote Posted by Starrfall
Well actually what it sounds like is more interesting than checking periods in citations to see whether or not they were italicized which I spent at least 20 minutes doing today. :(
Learn how to use Replace in Word. It's about 60% of being an effective drafting lawyer. ;)
45% is knowing how to C&P and the other 22% is being good at math.
Chade on 27/3/2008 at 22:34
Quote Posted by Thief13x
Basically, after implementing a minimum spanning tree, he will simply be able to input the stations he wants to deliver to that day along with the distances between them, and the program will tell him the order which he should visit the stations to travel the minimum overall distance. It sounds like something you could do manually, and on a small scale you could, but when you're talking about dozens of stations connected by hundreds of roads, you want a computer program that could calculate it quickly, and a minimum spanning tree is designed to do just that. It doesn't only optimize the delivery process, it will always give you the shortest route
But a minimum spanning tree only gives you the shortest length of "path" which connects all the nodes ... it doesn't give you the shortest length of path for any subset of nodes, and it also doesn't give you the shortest route when you are traveling from node to node ...
Let's talk about something concrete. Check the (
http://en.wikipedia.org/wiki/Minimum_spanning_tree) wikipedia page. It's easy to see that traveling along the tree (going down each branch and then doubling back) is not the quickest way of visiting all nodes.
Please correct me if I'm wrong, but unless there is some modification to the basic MST that I know about, I really don't see how it's applicable to a traveling salesman problem.
Lhet on 4/4/2008 at 04:29
So, the instructions are still confusing me a bit. The problem is a traveling salesman problem, right?
Will brute force work?
Mingan on 4/4/2008 at 16:33
yes. In O(n!) time. SLOOOOOOOOOOW.
Lhet on 5/4/2008 at 02:41
well, if there are few enough destinations, it might be ok anyways.
Or you could try a genetic algorithm, but I really dunno that the time you'd spend programming it and letting it get set up would be worth it.
