Babu lives in a certain village A, and in a sudden fit of materialism, he decides to earn extra income selling dubious medicine, like the ones above, in other villages within the vicinity.
To avoid trouble, he will not visit the same village twice, and to minimize cost, he has to keep his travelling distance the shortest possible - that being the major cost component, the medicine practically costing nothing (since it is dubious after all). He will need the shortest possible path that visits every other city once before returning to the safety of his own village, A. And he needs the travelling cost before he starts selling the medicine, to be able to factor in that cost into his selling price. But he (somehow) knows that its going to be O(N!) , just doing the calculation, and he doesn't have that much time.
So, not wanting to spend too much time going through a brute-force evaluation of all possible paths, he decides to keep track of the lower bound for the cost. This is a cost value below which the actual cost can never go below. He wanders for a while on what or how this lower bound is to be calculated, and after much jostling about, hanging about, staring into space, spamming scribbles into pieces of papers, he chances upon an idea. Suppose in the shortest path, for every village, one considers the 2 shortest road into or out from the village. Of course, it may or may not be possible to actually form a path using the 2 shortest roads for each of the villages. But still it may be possible, and he's considering that best-scenario possibility. The lower bound for the total cost is then a sum of the length of the 2 shortest roads for every village. There is certainly no way for the cost of the actual shortest path to go lower than this.
So he draws up the following table.. for each village, he's going to record the two shortest roads.
Here's what he have in the table,:
Now he sum up the total of the shortest 2 distances for each village:
And then calculate the sum of all the sums:
And he get 70, or 70km to be precise. That is a pretty long trip, but is 70km really the lower bound, he wondered. He pondered again over his map.
He came to realize that if 2 villages share the same shortest edge, than that edge is going to be counted twice. In fact, it's the same for all the other consecutive villages on the shortest path. So 70 is likely an overestimate. If the shortest path indeed comprises of all the 2 shortest roads for each village, then he would have counted each road twice, as shown above. His forehead wrinkled pondering over this, he realized that he has to divide the 70 by 2. Whatever the value obtained by summing up the 2 shortest roads for each village, he has to divide it by two. In terse form, it looks as shown below:
The e with 0 as the superscript and v as the subscript denotes the shortest edge of village v, where v can be anything from A to G. The e with superscript 1 is the second shortest edge.
Applying the formula as it is above, Babu obtains the value of 35. The shortest path for him to travel cannot be any shorter than 35. But now comes the actual problem: what is the actual path? In all likelihood the actual path he'll be taking will be much longer than the theoretical shortest path, the one with the length of 35. It doesn't make good business sense to consider the theoretical lower bound to be the actual shortest travelling distance.
He thinks of possible options he has when actually carving out the routes. From A, he can go to any of the following 3: B, G, F.
Had he chosen B, he could proceed on to G or C. And had he gone to G, he could from there, gone on to B or C or D or E or F. And as can be seen below, from F, he could continue as shown below, to proceed on to either G and E:
Now, that's lots of work.. Babu keeps thinking. He imagines a complete path A-B-G-C-D-E-F.
Summing up the length of the roads along the path (including the road from F back to A), he gets
But that's just a single path.... Should he also explore further the path A-B-G-D? Should he? Babu ponders, his forehead now wrinkled so much that's it ages beyond his age... He has the lower cost (35). But that lower cost makes no assumption about what roads to be fixed, what roads selected. But if he knows the lower cost, after fixing A-B-C-D, then he needs explore further only if the lower cost is lesser than the 36 he found for A-B-G-C-D-E-F. If that lower cost is more than 36, then he cannot expect anything better than 36 extending the A-B-C-D path.
So the question now for Babu is the following... Having the overall lower cost bound, how should he calculate the new lower cost after fixing a number of edges (or roads)?
Like suppose, from A, he decides to go to B, as shown below. What should be the new lower cost bound then? Logically, one needs to remove certain part from the lower bound - the cost for shortest or second shortest edges for A and B. And you need to add in the overall actual cost so far, that is the distance from A to B.
The new lower bound should then be something like as follows:
Babu gazes lovingly at his new found formula. Just a part missing - what should be subtracted from the original lower bound? It must be the length of edges connected to A and B. He thinks about it, and decides that it should be the average of the shortest edges from A and from B. He adjusts his formula to look as follows:
It seems perfectly logical now. Take away the cost of the smallest road in A and in B from the original lower bound, then add to the adjusted lower bound cost the total distances of the roads selected up to this point.
Now, what happen if he proceed further, from B to C?
He thinks about how the lower bound will now be adjusted.
Surely, he will need to subtract another term from the original lower bound. It must be the average of the shortest roads in B and that in C. But since the shortest road from B has already been subtracted out, for B, he will have to settle for the second shortest road. Hence, the revised lower bound is as follows:
Babu is about done now thinking about how he's going to search for the shortest path. With luck, if he can cut out many branches in his search for the shortest path, his Branch-and-Bound method will take him much less than O(N!) to find the shortest path. There is no guarantee, of course. And the amount of time he needs may still be a lot. But he has the whole weekend to do it. His trip will start on the Monday to come.
No comments:
Post a Comment