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!
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
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.
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.
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.
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.
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.
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.
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
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!
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!
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.
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)?
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}.
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!
Nice Video Bro...... This Very Helpful to me......Thank A Lot Bro.....................
great video~
thank-you tushar sir it helped a lot ;_;)/
thanks hello france, please thank sabeeka for me ^_^
Let the salesman just open a website and not travel ! Just kidding, awesome tutorial btw !
"Travelling deliveryman's Problem" will become the name.
I watched this one hour before my exam. Thanks a lot for helping me nail a 12 marker. :)
Much appreciated! Subscribed.
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 :-]
Is it possible for the code to be written in C and not Java. If so, could u pls demonstrate?
I rarely comment on these kind of videos but the way you performed the algorithm was really intuitive, thank you
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
wow it is so amazing that you implemented this... knowing algorithm and implementing is so so soooooooo much different thankyou!
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
*wortex*
vhat?
you deserve a medal sirji .....salute from MNNIT, allahabad
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.
Sunglasses 👓 🤣
Dislikers, did you follow the problem every second along with Tushar and dislike or did you dislike coz you never concentrated?
how did the n^2 term come in time complexity...can u plz explain
East or West Tushar u r the best :) made clear and easy.
"Whatever it takes.." u know the end game plot years ahead :)
Thank you!! plzz make a video on TSP by Branch and bound
This is a great video! But I am wondering if you know how to solve traveling salesman using branch and bound ? Thanks a lot!
thhooo :D
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
Thank You.. It's really helpful before a day of exam.. :-)
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.
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
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?)
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.
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?
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.
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
Only salesman that explained the concept + time complexity + code!!
Other videos only explain the concept.
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)
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.
Its like watching a video on fast forward.......cud u please slow down a bit??
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
good... but your speed is very high in teaching...pls...speak slowly
Gazab ka explanation dete hai aap tothanks for it
East or West, Tushar is the best :) .
Very nicely illustrated. Instead of java, I was looking for implementing it in C. Any luck?
read about islam man❤
Too fast unable to follow bt nice slang and gd video about concept pls slow down little bit
For a future video, can you explain how to do a max flow/min cut for a graph?
does greedy approach work for tsp? if yes, when does it fail?
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!
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!
Appreciate the video, always helps. But this time you are running really fast. Please slow down.
Brilliant explanation..
don't scream please talk slower
how last zero of completing cycle cam from 1 plz explain
thanks . everything was clear 😘😘. i worked out on the same time on another problem watching this video
please speak a bit slow, unless you are late to catch a train
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.
it is really good, better than my professor explained it.
Sir u are king👑👑👑
Too hard for me...😢
How to design or think about such solution?
An excellent video that clearly explains the problem and the solution
Thanks Tushar! Had been looking for the code implementation. :)
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}.
I really appreciate your work and effort you put to explain the solution. thank you
how you are generating the possible subsets?
Nicely explained! Tushar
very clear explanation... thanks a lot!!!
beautifully explained. thanks and appreciate your effort
This playlist is a gem. Thanks Tushar! Please do continue making more videos.
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..
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
Thank u very much for such a brilliant explanation.
Thank you so much. Helped me a lot before my exams
thanks
good explanation for the Held-Karp algorithm
can you tell me where can i get this code in cpp
what about undirected graph in TSP
Thankyou so much for the video :)
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
i learn a lot from your videos. Thanks a lot :)
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 😩😩😩😩
too fast unable to understand
Very helpful, thank you very much!
Dude, you just saved my assignment, thank you!
yo man....me too...where you from thou!
It's awesome 👍... Thanks🙏
thanks a lot for this video sir
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
The best :) thank u :)
thanks for helping!!!
tq sir
Amazing, Thank you :)
really good one!
awesome:)
bhaiiii jada aagraje ho gayee ap
You're amazing man.
Awesome tutorial..
awesome video
dark spots kam karo sir
😍
great video &explanation. Loved it
if u r speaking in English then no need to give subtitle its unable to view the board and mostly your speaking style rare complicated
Could someone provide me with the pseudocode representation of this algorithm?