Honestly the best video I have found on held karp! And you've uploaded it with just enough time to fully understand it before my exam! Thank you so much!! :)
+Tushar Roy One quick question though! If say you added on one extra node, would you look through the combinations in this order? A B C D E AB AC AD AE
ABC
ABD
ABE
ACB
ACD
ACE
ADB
ADC
ADE
AEB
AEC
AED
ABCD
ABCE
ABDC
ABDE
ABEC
ABED
ACBD
ACBE
ACED
ACEB
ADBC
ADBE
ADCB
ADCE
ADEB
ADEC
AEBC
AEBD
AECD
AECB
AEDB
AEDC Apologies for the long comment, but am I looking at too many combinations? Cheers!
Ok cheers! The thing that has confused me though is that these combinations will look past 2^n and will check over 40! Is the 2^n almost a rough estimate or have I done something wrong?! haha! Cheers! :)
It's not right! ABE and AEB is the same set: order doesn't matter in a set. Try 4 elements, you should get 2^4=16 subsets (nil, A, B, C, D, AB, AC, AD, BC, BD, CD, ABC, ABD, ACD, BCD, ABCD). In your generating the subsets either take the current one or not, but stick to that decision when doing the next step. An easy to understand algo is [for n
+Róbert Papp (TWiStErRob) Thanks! I thought something was up with it! However what confuses me is that if order doesn't matter then how is the problem solved? Because what if AEB leads to a shorter path in the end but it's been completely disregarded? I am confused haha!
+Ben Davies hmm, I didn't think that far, your count of subsets were off, so that had to be fixed. Your generated subsets will most likely be in lexicographical order, or equivalent (you can redefine the alphabet with a bijection). The dynamic programming part of this algorithm only depends on lengths one less than the current subset's length, so as long as the subsets are in increasing order of length you're fine. Notice that AEB has recursive steps of A+EB/E+AB/B+AE; and BEA would have B+EA/E+BA/A+BE; which are the same if they're sets. Within the same length it can be any order because the minimum always selects the smallest one... notice that the pairings are the same.
I watched this tutorial a week ago and I couldn't understand a thing because I **ONLY** WATCHED Today I did so again but this time I followed along the calculations by writing and when he was calculating [1,{2,3}], I had already calculated [2,{1,3}] Knowing it is awesome(to be honest) Summary: 0➡️1➡️3➡️2➡️0
this is really great one of videos about the topic..Thank you for your effort to create this understandable video for viewers.. I'm 100% sure about that they like it as much as me.Thank you.
I appreciate it ... it's a good video... But there are a lot of words that use , for instance "That vertex" , "This vertex"... it would be clear to follow if u'd instead say "Vertex A" or "Vertex B". I mean being precise and clear would benefit more. Good job though!
Awesome!! Great Work Tushar!! just one feedback, please use something like 0->1->2->3 instead of saying if a vertex from subset precedes this vertex, that will be much better!
If you mean to say at 7:05 , then he is doing the right thing. He is doing the TSP iterations for {vertex, {remainingSet}} in the ascending order of remainingSet. Like first through Phi, then through {1}, and then {2} and then {3} and then {1,2}, {2,3}, {1,3}, and lastly {1,2,3}.
does space complexity and time complexity is same O(n^2 *2^n) nut I read in book as space complexity is O(n*2^n) please explain clearly about time complexity and space. complexity Thank u
NO NEED TO COMPUTE SET {0,{1,2,3}} DESTINATION CAN CONTAIN ALL THE VERTICES EXCEPT THE SOURCE.WITH EACH HOP OPTIMAL SUBSTRUCTURE CONTAINS AT LEAST ONE OR MORE THAN ONE VERTICES IN ITS FINAL POSITION SO WITH HOP COUNT = N ALL THE VERTICES WILL BE IN THEIR FINAL POSITION AND ROUTE FROM LAST VERTEX HERE WITH HOP COUNT = N TO SOURCE VERTEX IS THE SHORTEST PATH COVERING ALL THE VERTICES.IF SET {0,{1,2,3}}(CONTAINING N+1 VERTICES) BEING COMPUTED IT INDICATES THAT SET WITH N VERTICES IS NOT SUFFICIENT TO COMPUTE SHORTEST PATH AND MAY BE DISRUPTED BY SET WITH THE SIZE(N+1) THIS WILL LEAD TO AMBIGUITY WHERE NO VERTEX BEING FINALIZED IN THE EVOLUTION OF HOPS.
is this the best current attempt at this algorithm, I see there has been clustering, 2-opt, and simulated annealing, etc ? or is this just an example algorithm to solve it. Great video , I watch many of your videos , they are plainly explained, making the example most easy to understand. Thank you!
The code is excellent. Comparators, collections, static inner class, hashcode override, you sure know how to code java . Question: Line 153, Collections.sort(allSets, new SetSizeComparator()); Could your comparator just be implemented as a final static member variable of the class TravelingSalesmanHeldKarp ? This would avoid the a ton of object creations.
For the last subset {1,2,3} you checked for 3 permutations: (1,2,3), (2,1,3) and (3,1,2). Why didn't you check for the three remaining permutations: (1,3,2), (2,3,1) and (3,2,1)?
sir can you create a video for 5 cities explaining it step by step there are is some confusion like in 5 cities there will be 3 possibilities for each city when dealing with 3 cities at a time like 3 variables a312 a314 a324 where a312 is a variable name in which we are going to city 3 in which the parent city can be 1 or 2, now coming back to the 3 variables a312 a314 and a 324 what will we do with these 3 will we compare them also to have the smallest path, like how will we operate.
How the number of subset is exponential -- which is 2 ^ n As per my understanding, it should be n ^2 ~~ approx (n-1)(n-2) +2. Please correct me if I am going wrong
Hi @Tushar Roy Please provide some video for this problrm "Partition a set into two subsets such that the difference of subset sums is minimum" There is two variation ......>1 both subset can be of any size > 2 both subset of equal size or max size difference is 1 in case given array is odd by length.
You have left many questions unanswered and skipped many logics like why are we making these sets? or why you made those tables and noted costs and parent? and many more.
you deserve a medal sirji .....salute from MNNIT, allahabad
I rarely comment on these kind of videos but the way you performed the algorithm was really intuitive, thank you
I watched this one hour before my exam. Thanks a lot for helping me nail a 12 marker. :)
Much appreciated! Subscribed.
Only salesman that explained the concept + time complexity + code!!
Other videos only explain the concept.
Honestly the best video I have found on held karp! And you've uploaded it with just enough time to fully understand it before my exam! Thank you so much!! :)
+Tushar Roy One quick question though! If say you added on one extra node, would you look through the combinations in this order?
A
B
C
D
E
AB
AC
AD
AE
ABC
ABD
ABE
ACB
ACD
ACE
ADB
ADC
ADE
AEB
AEC
AED
ABCD
ABCE
ABDC
ABDE
ABEC
ABED
ACBD
ACBE
ACED
ACEB
ADBC
ADBE
ADCB
ADCE
ADEB
ADEC
AEBC
AEBD
AECD
AECB
AEDB
AEDC
Apologies for the long comment, but am I looking at too many combinations?
Cheers!
Ok cheers! The thing that has confused me though is that these combinations will look past 2^n and will check over 40! Is the 2^n almost a rough estimate or have I done something wrong?! haha! Cheers! :)
It's not right! ABE and AEB is the same set: order doesn't matter in a set. Try 4 elements, you should get 2^4=16 subsets (nil, A, B, C, D, AB, AC, AD, BC, BD, CD, ABC, ABD, ACD, BCD, ABCD). In your generating the subsets either take the current one or not, but stick to that decision when doing the next step.
An easy to understand algo is [for n
+Róbert Papp (TWiStErRob) Thanks! I thought something was up with it! However what confuses me is that if order doesn't matter then how is the problem solved? Because what if AEB leads to a shorter path in the end but it's been completely disregarded? I am confused haha!
+Ben Davies hmm, I didn't think that far, your count of subsets were off, so that had to be fixed. Your generated subsets will most likely be in lexicographical order, or equivalent (you can redefine the alphabet with a bijection). The dynamic programming part of this algorithm only depends on lengths one less than the current subset's length, so as long as the subsets are in increasing order of length you're fine. Notice that AEB has recursive steps of A+EB/E+AB/B+AE; and BEA would have B+EA/E+BA/A+BE; which are the same if they're sets. Within the same length it can be any order because the minimum always selects the smallest one... notice that the pairings are the same.
This playlist is a gem. Thanks Tushar! Please do continue making more videos.
wow it is so amazing that you implemented this... knowing algorithm and implementing is so so soooooooo much different thankyou!
Let the salesman just open a website and not travel ! Just kidding, awesome tutorial btw !
"Travelling deliveryman's Problem" will become the name.
East or West Tushar u r the best :) made clear and easy.
I watched this tutorial a week ago and I couldn't understand a thing because I **ONLY** WATCHED
Today I did so again but this time I followed along the calculations by writing and when he was calculating [1,{2,3}], I had already calculated [2,{1,3}]
Knowing it is awesome(to be honest)
Summary:
0➡️1➡️3➡️2➡️0
Dude, you just saved my assignment, thank you!
yo man....me too...where you from thou!
this is really great one of videos about the topic..Thank you for your effort to create this understandable video for viewers.. I'm 100% sure about that they like it as much as me.Thank you.
I appreciate it ... it's a good video... But there are a lot of words that use , for instance "That vertex" , "This vertex"... it would be clear to follow if u'd instead say "Vertex A" or "Vertex B". I mean being precise and clear would benefit more. Good job though!
Thank you so much. Helped me a lot before my exams
I really appreciate your work and effort you put to explain the solution. thank you
Thank You.. It's really helpful before a day of exam.. :-)
Thanks Tushar! Had been looking for the code implementation. :)
An excellent video that clearly explains the problem and the solution
this is an excellent presentation! Thank you.
"Whatever it takes.." u know the end game plot years ahead :)
it is really good, better than my professor explained it.
Is it possible for the code to be written in C and not Java. If so, could u pls demonstrate?
Nicely explained! Tushar
thanks . everything was clear 😘😘. i worked out on the same time on another problem watching this video
Gazab ka explanation dete hai aap tothanks for it
East or West, Tushar is the best :) .
The greedy algorithm would be wrong to solve this but ironically the example you choose greedy algo would've given the same answer LOL
could you please direct me to any books for better understanding of DSA :-]
Awesome!! Great Work Tushar!! just one feedback, please use something like 0->1->2->3 instead of saying if a vertex from subset precedes this vertex, that will be much better!
the video is really helpful though i noted when performing union of 2 sets, you went ahead and did {1,3} before attempting {2,3}
If you mean to say at 7:05 , then he is doing the right thing. He is doing the TSP iterations for
{vertex, {remainingSet}}
in the ascending order of remainingSet. Like first through Phi, then through {1}, and then {2} and then {3} and then {1,2}, {2,3}, {1,3}, and lastly {1,2,3}.
@@chinmayjoshi5554 it's been 10 month I have to rewatch again 😩😩😩😩
does space complexity and time complexity is same O(n^2 *2^n)
nut I read in book as space complexity is O(n*2^n)
please explain clearly about time complexity and space. complexity
Thank u
how did the n^2 term come in time complexity...can u plz explain
i learn a lot from your videos. Thanks a lot :)
Great video. I do have a questions about the code. Why do you have to remove the preVertex and then add it back in the getCost method?
NO NEED TO COMPUTE SET {0,{1,2,3}} DESTINATION CAN CONTAIN ALL THE VERTICES EXCEPT THE SOURCE.WITH EACH HOP OPTIMAL SUBSTRUCTURE CONTAINS AT LEAST ONE OR MORE THAN ONE
VERTICES IN ITS FINAL POSITION SO WITH HOP COUNT = N ALL THE VERTICES WILL BE IN THEIR FINAL POSITION AND ROUTE FROM LAST VERTEX HERE WITH HOP COUNT = N TO SOURCE VERTEX IS THE
SHORTEST PATH COVERING ALL THE VERTICES.IF SET {0,{1,2,3}}(CONTAINING N+1 VERTICES) BEING COMPUTED IT INDICATES THAT SET WITH N VERTICES IS NOT SUFFICIENT TO COMPUTE SHORTEST
PATH AND MAY BE DISRUPTED BY SET WITH THE SIZE(N+1) THIS WILL LEAD TO AMBIGUITY WHERE NO VERTEX BEING FINALIZED IN THE EVOLUTION OF HOPS.
For a future video, can you explain how to do a max flow/min cut for a graph?
can u pls tell, how did u construct d cost matrix??
did you find out?
my guess is that the matrix has not the same values as the graph is shown at the beginning.
yaa
you can just apply floyd-warshall to construct the cost matrix
beautifully explained. thanks and appreciate your effort
So is this the value of the lower bound? And do you have to repeat the algorithm with each possible starting-nod?
Thx for your help
This is a great video! But I am wondering if you know how to solve traveling salesman using branch and bound ? Thanks a lot!
is this the best current attempt at this algorithm, I see there has been clustering, 2-opt, and simulated annealing, etc ? or is this just an example algorithm to solve it. Great video , I watch many of your videos , they are plainly explained, making the example most easy to understand. Thank you!
Sir u are king👑👑👑
Awesome, Tushar!
Your sample applies to only 1 vehicle, without capacity constraint.
Is there any similar video with "Capacity vehicle routing"?
like multiple travelling salesman, reading research maybe the solution is genetic algorithm ... ? can you share if you have ... Thanks lot my friend
Thank u very much for such a brilliant explanation.
The code is excellent. Comparators, collections, static inner class, hashcode override, you sure know how to code java .
Question:
Line 153,
Collections.sort(allSets, new SetSizeComparator());
Could your comparator just be implemented as a final static member variable of the class TravelingSalesmanHeldKarp ? This would avoid the a ton of object creations.
+Tushar Roy yah your right.
Do you have an account in Codeforces or Topcoder?)
Please could you help me TSP with Source and Destination are different? (Directed grapth, a node or edge can be visited any number of times)
For the last subset {1,2,3} you checked for 3 permutations: (1,2,3), (2,1,3) and (3,1,2). Why didn't you check for the three remaining permutations: (1,3,2), (2,3,1) and (3,2,1)?
he already considered these cases in previous step by choosing minimum path.
e.g. for (1,2,3), min of {2,3} or {3,2}.
Very nicely illustrated. Instead of java, I was looking for implementing it in C. Any luck?
sir can you create a video for 5 cities explaining it step by step there are is some confusion like in 5 cities there will be 3 possibilities for each city when dealing with 3 cities at a time like 3 variables a312 a314 a324
where a312 is a variable name in which we are going to city 3 in which the parent city can be 1 or 2, now coming back to the 3 variables a312 a314 and a 324 what will we do with these 3 will we compare them also to have the smallest path, like how will we operate.
Nice Video Bro...... This Very Helpful to me......Thank A Lot Bro.....................
thanks
good explanation for the Held-Karp algorithm
Thank you!! plzz make a video on TSP by Branch and bound
How the number of subset is exponential -- which is 2 ^ n
As per my understanding, it should be n ^2 ~~ approx (n-1)(n-2) +2.
Please correct me if I am going wrong
how you are generating the possible subsets?
does greedy approach work for tsp? if yes, when does it fail?
Hey u use graph in starting and distance matrix .this matrix is from that graph or both are different???
+Tushar Roy ok :) i also think so
can you give example of some more traveling salesmen city more then 4 or 5 city
Vishal Nakum stop asking stupid questions. also learn grammar
Dislikers, did you follow the problem every second along with Tushar and dislike or did you dislike coz you never concentrated?
Will you please provide a main function in your Github link for this post
it doesn't have a main function and i don't understand how to add that
thanks
what about undirected graph in TSP
very clear explanation... thanks a lot!!!
How to design or think about such solution?
Hi @Tushar Roy
Please provide some video for this problrm "Partition a set into two subsets such that the difference of subset sums is minimum"
There is two variation ......>1 both subset can be of any size
> 2 both subset of equal size or max size difference is 1 in case given array is odd by length.
great video &explanation. Loved it
Brilliant explanation..
It's awesome 👍... Thanks🙏
can you tell me where can i get this code in cpp
Very helpful, thank you very much!
Appreciate the video, always helps. But this time you are running really fast. Please slow down.
Hey Mr Tushar Roy really thanks for the videos uh explain veery well but can uh b lil slow while speaking its tough to understand uh speak really fast
You can change the speed..
how last zero of completing cycle cam from 1 plz explain
You're amazing man.
Thankyou so much for the video :)
Too fast unable to follow bt nice slang and gd video about concept pls slow down little bit
*wortex*
vhat?
Could someone provide me with the pseudocode representation of this algorithm?
You have left many questions unanswered and skipped many logics like why are we making these sets? or why you made those tables and noted costs and parent? and many more.
Amazing, Thank you :)
Its like watching a video on fast forward.......cud u please slow down a bit??
Why can't we just generate a Minimum Spanning Tree for the Graph and just add the smallest edge from the ending vertex to the starting vertex....?
How do you ensure that would give us a simple cycle? In most cases, it would not.
Awesome tutorial..
really good one!
Sunglasses 👓 🤣
thanks a lot for this video sir
good... but your speed is very high in teaching...pls...speak slowly
awesome video
thanks for helping!!!
great video~
Thx my teacher
The best :) thank u :)
too fast unable to understand
dark spots kam karo sir
thank-you tushar sir it helped a lot ;_;)/
awesome:)
Too hard for me...😢
bhaiiii jada aagraje ho gayee ap
thhooo :D
tq sir
please speak a bit slow, unless you are late to catch a train
thanks hello france, please thank sabeeka for me ^_^
😍