Difficult to understand the solution provided in the video (travelling salesman problem)

[WMDhamnekar]

It is difficult to understand the solution provided in the video to the travelling salesman problem having Hamiltonian circuits with added length constraint.
The travelling salesman problem has been solved in the below given video, but I didn't understand lower bound computed for the following paths.

I also didn't understand the why Path 8,9 10 and 11 have been called 'first tour', 'better tour', 'inferior tour' and 'optimal tour' respectively.

What are the meanings of l=24 for Path 8, l=19 for Path 9, l= 24 for Path 10 and l=16 for Path 11?

Path 4: a,e lb=19,

Path 5:a,b,c lb=16,

Path 6:a,b,d lb=16,

Path 7: a,b,e lb=19,

Path 8:a,b,c,d (e,a) l=24 first tour ,

Path 9: a,b,c,e(d,a) l= 19 (better tour),

Path 10: a,b,d,c (e,a) l=24 (inferior tour),

Path 11: a,b,d,e(c,a) l=16 optimal tour.

Watch the vide here →

Would any member explain me the travelling salesman problem solved in this video?

Can we solve this problem by another method where conditions of the travelling salesman problem is not satisfied?

The condition is the salesman has to visit each city in the tour only once and return to the start city.

 

[FactChecker]

It is difficult to understand the solution provided in the video to the travelling salesman problem having Hamiltonian circuits with added length constraint.
The travelling salesman problem has been solved in the below given video, but I didn't understand lower bound computed for the following paths.

All of them or any in particular or all of the ones below? I'll do a few.

I also didn't understand the why Path 8,9 10 and 11 have been called 'first tour', 'better tour', 'inferior tour' and 'optimal tour' respectively.

Traversing that branch of the tree from left to right and calculating the total lengths: The first path is 8. The second path is 9, which is better than path 8. The third path is 10, which is longer than path 9. The final path on that branch is 11, which is optimal for that branch.

What are the meanings of l=24 for Path 8, l=19 for Path 9, l= 24 for Path 10 and l=16 for Path 11?

Those are the actual lengths if you add up those path steps.

Lower bounds:
Before any path steps are assumed, the initial lower bound (ILB) is where we get to use the two lowest for every node, a,b,c,d,e. That is ILB=((ac+ab)+(ba+bc)+(ca+ce)+(de+dc)+(ec+ed))/2 = ((1+3)+(3+6)+(1+2)+(3+4)+(2+3))/2 = 14,
ADDED NOTE: This is a rough estimate guaranteed not to be higher than the true lower bound. It assumes that each node can be entered and left on its two shortest paths. The sum is divided by two because the paths are counted twice (for instance, from a to b and also from b to a).

Path 4: a,e lb=19,

The path (ae) is given, so the ILB values of nodes a and e must be changed. Where possible, replace the larger ILB entries for nodes a and b with ae=8. That gives:
lb=((1+8)+(3+6)+(1+2)+(3+4)+(2+8))/2=19

Path 5:a,b,c lb=16,

Now, ab and bc are given. ab was already in the ILB of nodes a and b, so that changes nothing. bc was already in the ILB for node b but not for node c. Change the larger entry of node c to bc=6.
((1+3)+(3+6)+(1+6)+(3+4)+(2+3))/2 = 16

Continue in that way and see if it makes sense for the others.

Can we solve this problem by another method where conditions of the travelling salesman problem is not satisfied?

Yes. This is an example of the general subject of integer programming. There has been a large amount of work done on this subject. Entire books have been written on how to solve them.

 

[WMDhamnekar]

Is it possible to compute the answer using the node 2 (a,c),node 5(a,c,b) node 6(a,c d), node 7 (a,c,e), node 8(a,c,b,d), node 9 (a,c,d,e), node 10(a,c,d,b),node 11(a,c,d e)? Is that answer viable? Note that in this case, we are violating the condition that 'c' should not be before 'b'

 

[FactChecker]

Sure, you can calculate that but it would be wasting time. The best solution that way would only follow the same path as the "b before c" solution in the opposite direction. By insisting that b precede c, the number of possibilities examined is immediately cut in half. That is a great improvement in efficiency.

EDIT: I should have said it would go around in the opposite direction of one of the optimal "b before c" solutions. There might be ties for the optimal solution. Because the costs (path length) are the same in both directions, the "b before c" solutions are the only ones you need to compute. If the cost depended on direction, the "c before b" paths would also need to be included.

EDIT2: Notice that no branch of the tree is trimmed by comparing two lbs. An lb is an optimistic lower bound. Two of them can not be reliably compared. It is only after an actual length. l. to a terminal "leaf" of the tree is determined that a branch can be trimmed by comparing its optimistic lb to an actual length, l. That is why it is important to go down to some terminal leaves early.

I am including this diagram just to preserve what we are discussing: