For those wondering what makes this a DP solution: Basically instead of finding all permutations. and then doing the arithmetic, IE, instead of doing min(1->2->3->4, 1->2->4->3, ...) of all possible routes, we can see that there are repetitive calculations in 1->2->3->4 and 1->2->4->3 for instance. The route 1->2 is common(overlap) to routes 1->2->3->4 and 1->2->4->3, if you looked at the tree closely. By definition of DP, we are trying all possibilities and we also see overlapping subproblems!
@vendettaaaa666 So essentially all this is, is caching distances into a giant lookup table? That still seems very complexity-demanding to solve this problem.
I think we are overlapping because we don't know from which direction path cost is minimum. If both sided path would be same then that approach will not be more good.
Our college teachers became teachers because they didn't get placement 😀 . and this person became teacher because of his interest. The difference can be seen 😁 clearly
Sir one thing I've to tell you ! Watched all of your videos for 3 times or atleast 2 times perfectly and It's just because of you , today I was confidently able to write the DAA Exam under JNTU-H Thank You so much Sir ! Really lovely explantions ! and I hope you create some more videos on other Computer Subjects Sir , you were known to whole of our College and you were the one who have helped almost 450 students in our college Once again Hats Off to you Sir !
Profesor Bari, you surprise me all the time, are you Magic? i have just come from another video and i could not understand what he was saying but within the first two minutes and 30 seconds here i already understand the problem... thank you
Awesome sir.....I'm in DAA semester exam's previous day, I'm blank about DAA, but after seen your all videos I'm very much cleared and having hope i will pass in exam👏👏👏👏👏 Hat's of sirG
Sir u r teaching very useful for me tq so much and this TSP it has 1 small mistake g(2,{3} )=15 but g(2,{4})=18, g(3,{2})=18and so on... But u just consider only 1vetex only that is mistake
Sir as you took g(2, {3}) =15 then all the remaining will be also like same..... But you wrote g(2, {4}) =8 it will be 18 na, and g(3, {2}) =5 but 18....g(3, {4}) =20, g(4, {2}) =13, g(4, {3}) =15.....na?
Sir, promise me you'll never delete these videos! These are great for references even when I'm 30 Edit: We have exam tomorrow with students of about 20sec*60 = 1200 students watch your videos this entire day like me :-)
Sir, Thank you for a great explanation! I have a question. For g(2, {3}) we have 15, but then should not g(2, {4}) = 18, g(3, {2}) = 18, g(3, {4}) = 20, g(4, {2}) = 13, g(4, {3}) = 15? Thank you
No one is perfect , but that mistake screwed up my solution.... Well i found a helpful guy who gave the correct values... Guys like me will get into depression if our answers don't match, so thanks to that guy....
sir u messed up near the intermediate part where there is 1 remaining vertex as in ... g(2,{3}) ..... to ..... g(4,{3}) .... but it is a good explanation ... thank you
Great explanation, thank you sir i got clarity on this problem, but there is a little problem: 10:30, I think he wrote number "1" not number "4" since he said "start from vertex 2 to nowhere -> return vertex 1" -> so his answer is g(2,{1}) =5. I have misled as well, but I listen to him carefully so maybe we are misled at this point. 11:28, g(2,{4}) = 18 not 8 (Cause g(4,1) = 8 + g(2, 4) = 10 -> 18), and the continuous answer is similar to Mr. @kennethi.e answer.
Sir, I believe Dynamic Programming is an improvement over Brute Force, although approach is similar. But in this particular example, I can't find any improvement, it looks exactly Brute Force. My question is what is the difference between Brute Force and Dynamic P, if we solve this problem using both?
This is already a little smaller than the brute force. Brute force is O(n!) which means the table would have 24 entries. He doesn't work the last 3 entries for his table, but there are 15 total. This improvement gets more dramatic as the problem increases in size.
Hello sir ! play your video just before 13:01....you have completed a section in which g(2,{3})=15 g(2{4})= 8 in above eqn you have misplaced I think... the 1st one should 6 or the 2nd one should 18. in both the cases you have used different methods.
So this is pretty much the same as the multistage graph problem? The algorithm starts finding out minimum costs from the end towards the starting point. The only difference is instead of having a table saving the shortest path to the next node, we have have all the combinations as some sort of list
Sir, its my request to you to please stand at the side for 2-3s before you erase the board. This makes it easier to make notes by directly taking screenshots.
Nice explanation sir Can you please make some videos on in depth explanation on making these general dp formulas and determining if we can apply dp in a particular problem?
Great explanation sir, but I have a question about it. You got the minimum value to travel to all vertices to be 35, but how do you know its going 1-2-4-3 without using the tree?
You can find this from the tables. To find the first leg, select the node with the lowest cost for N nodes starting with the origin. From there, select the node with lowest cost for N-1 nodes starting with the node you selected. Continue until you have a full tour.
This algorithm is different from the way I originally learned to solve TSP (I would refer to this as back-to-front; I originally learned front-to-back). I implemented it for practice and noticed something wonderful about it. Rather than having to infer the best tour from the cost table you can build up a path table as you go. e.g. when you are calculating `g(2, {3,4})` you compare the values of `c[2][3] + g(3, {4})` and `c[2][4] + g(4, {3})`. You end up choosing `c[2][4] + g(4, {3})`, with a value of 25. If you also record that you picked `4` as the next node instead of `3`, then you can build the optimal tour back up directly from the table without needing to reference the adjacency matrix again.
There was a mistake from g(2, {4}) to g(4, {4})..The solutions are g(2, {4}) = 18, g(3, {2}) = 18, g(3, {4}) = 20, g(4, {2}) = 13, g(4, {3}) = 15 (Copied from another comment to ensure double check)
![4.7 [New] Traveling Salesman Problem - Dynamic Programming using Formula](http://i.ytimg.com/vi/Q4zHb-Swzro/mqdefault.jpg)
Tomorrow DAA exam very Thanks 😊
Lol 😂. It's my turn now
Today DAA exam in 1 hr😌
@@CellerCity haha now it's my turn👻
@@XINgalaxy Army💜🤣
Mine too 🤝
And mine is today after 1 hour 🙃🙂
There was a mistake from g(2, {4}) to g(4, {4})..The solutions are g(2, {4}) = 18, g(3, {2}) = 18, g(3, {4}) = 20, g(4, {2}) = 13, g(4, {3}) = 15
👍
Yeah!, I was thinking the same thing.
@@abdul_bari No problem. Your students can easily overcome minor mistakes. At the end of the day " we are your student ".
thanks bhai i was confused with this one
Yes i also noticed
Sir, you are a great teacher . Your explanation is excellent . wish you all the best and you live long with sound health . Thanks.
For those wondering what makes this a DP solution:
Basically instead of finding all permutations. and then doing the arithmetic, IE, instead of doing min(1->2->3->4, 1->2->4->3, ...) of all possible routes, we can see that there are repetitive calculations in 1->2->3->4 and 1->2->4->3 for instance. The route 1->2 is common(overlap) to routes 1->2->3->4 and 1->2->4->3, if you looked at the tree closely.
By definition of DP, we are trying all possibilities and we also see overlapping subproblems!
thank you
@vendettaaaa666 So essentially all this is, is caching distances into a giant lookup table? That still seems very complexity-demanding to solve this problem.
@@kevintyrrell7409 it is NP-Hard afterall
@@kevintyrrell7409 at least we're eliminating the computational redundancy while reaching each possibility
I think we are overlapping because we don't know from which direction path cost is minimum. If both sided path would be same then that approach will not be more good.
The way of teaching is like bottom up approach - first solve , then derive algorithm !
Great videos - all of them : )
Our college teachers became teachers because they didn't get placement 😀 . and this person became teacher because of his interest. The difference can be seen 😁 clearly
Simply outstanding! Doesn't get better than this.
Sir
one thing I've to tell you !
Watched all of your videos for 3 times or atleast 2 times perfectly
and It's just because of you , today I was confidently able to write the DAA Exam under JNTU-H
Thank You so much Sir !
Really lovely explantions !
and I hope you create some more videos on other Computer Subjects
Sir , you were known to whole of our College and you were the one who have helped almost 450 students in our college
Once again Hats Off to you Sir !
NOT ONLY YOUR COLLEGE!
HE IS HELPFULL FOR EVERY COLLEGE STUDENT PURSUING BTECH IN CSE.
pass hua?
You the best in explaining these tough algorithms in an layman language. Thank you sir!!
ua-cam.com/video/K3rYJYi2geE/v-deo.html
He is teaching for the sake of TEACHING..and unlike others not asking for Like, Share And Subscribe 🙏🙏🙏🙏
If someone asks for like, share and Subscribe, there's nothing wrong. They need to fill their stomach to actually teach. Really D*m* take by you.
I think you mean love. Sake usually implies he's doing it because he has to not because he wants to.
also incorrectly
thank you sir finally I understand how to solve this types of problem ....😊
11:23 forward has some mistakes, but thanks for the video. I kinda understand
Me, who Today having DAA exam😂
Same dude 😂
All the best for tomorrow's exam 😂 👍
Profesor Bari, you surprise me all the time, are you Magic? i have just come from another video and i could not understand what he was saying but within the first two minutes and 30 seconds here i already understand the problem... thank you
Watching this a night before ADA exam . Wish me luck
Teacher is at another level 🤩👏🏼 now I can do it on my own..thank you sir
This Channel deserves more subscribers and views
You know you will top when sir abdul bari is there. Thx sir
Sir your videos are too good and easy to understand... I studied from your algorithm Playlist only... You're a saviour... Thanks a ton!!!
Awesome sir.....I'm in DAA semester exam's previous day, I'm blank about DAA, but after seen your all videos I'm very much cleared and having hope i will pass in exam👏👏👏👏👏 Hat's of sirG
did you pass? I have DAA tomorrow, asking for a friend
@@nanduugee I have daa exam tomorrow what should do. To pass
@@nanduugee there is no waY TO pass by watching his video, i got failed , i had watched his video 100 times but still not cleared
Thank you sir understood this very clearly. Except for that small mistake of g(2,{4}) everything is explained well and fine. ⚡
Sir u r teaching very useful for me tq so much and this TSP it has 1 small mistake g(2,{3} )=15 but g(2,{4})=18, g(3,{2})=18and so on... But u just consider only 1vetex only that is mistake
Your lectures helped me to pass in my examinations 🙏
nee thooti potti machu
Sir as you took g(2, {3}) =15 then all the remaining will be also like same..... But you wrote g(2, {4}) =8 it will be 18 na, and g(3, {2}) =5 but 18....g(3, {4}) =20, g(4, {2}) =13, g(4, {3}) =15.....na?
Yes bro , he had written wrong
I was also confused
All are saying well explained sir but one is observing the mistakes
Our teachers are watches your videos sir before teaching a lecture
Daa exam is tommorow ... i am here 😂
You are
doing a great help to students like us sir... huge repect
MashaAllah beautifully explained sir. Thanks for uploading such a great lecture.
#Balochistan
praise to mulla allah
@@baal1297 I didn't get.
Ye toh abdul baari hai.. Ye to accha baccha hai.. Ye duaae sithkaa hai.. Acchi baate bataata hai.
To aao, chalo sikhe abdul baari ke sanng..
Tomorrow DAA exam....my DAA mam is a waste...thought me nothing but how to pluck the hair........thankyou for explaining sir
I think there is mistake in this problem sir, but the way you teaching students can easily find that error😍
Sir, promise me you'll never delete these videos! These are great for references even when I'm 30
Edit: We have exam tomorrow with students of about 20sec*60 = 1200 students watch your videos this entire day like me :-)
gitam,visakhapatnam sir..
@@pranavigogireddy9859 here you go!! Told you there will many people watching it.. 2 out of 1200
I should have watched this in regular of my examination 😩
Now I can pass my exam 😃
Even my subject faculty is watching your videos to take classes for us sir😂😂
The best teacher in the world
Best explanation i've seen.
Sir,
Thank you for a great explanation! I have a question. For g(2, {3}) we have 15, but then should not g(2, {4}) = 18, g(3, {2}) = 18, g(3, {4}) = 20, g(4, {2}) = 13, g(4, {3}) = 15?
Thank you
You are crt bro
correct bro
@@vijaykumarRC1215 🥕
I appreciate the fact that you used salesperson instead of salesman. It is 2021 we don't assume genders.
Tomorrow is college exam very thank you.
Akgec....
Super thalaiva❤🎉
🎉
You make the subject very easy sir.
Thank you so much.
Sir you are great sir, this help me lot in #DAA exam 🙏🙏🔥
No one is perfect , but that mistake screwed up my solution.... Well i found a helpful guy who gave the correct values...
Guys like me will get into depression if our answers don't match, so thanks to that guy....
time duration 11:14, I am little bit confused Sir at this point And the rest of it is very much helpful.
This is morning 5 am and today is daa exam but I'm ok daa easy and his lectures are very useful ❤😊
Bahut acche se samaj me aaya sir... Thank you...
great explanation but it could have been awsome if algorithm would have explained with any code (C/C++)
He maintained gender equality.
Not salesman but sales person😁
Ky ky hua ky aakhir😆😆😆
Tomorrow is daa exam tq sir ❤
thank yoou so much sir you make feel like a superman
7:55 DYNAMIC PROGRAMMING approach
I have DAA EXAM TOMORROW THANK YOU
Simple and easy explanation nice 😊we are easily understanding u r simply way ☺️
Thank u ji.. For helping before exam day..❤❤nice teaching skills saab
Thank you sir i gave exam today for algorithm and my exam was good thnx to you
started from the bottom, now we're here...
Tomorrow Ada exam
Thanks 👍
sir u messed up near the intermediate part where there is 1 remaining vertex as in ... g(2,{3}) ..... to ..... g(4,{3}) ....
but it is a good explanation ... thank you
Tomorrow DAA exam , very thanks😊
Sir wonderful explaination.hats off sir😍😍
Great explanation, thank you sir i got clarity on this problem, but there is a little problem:
10:30, I think he wrote number "1" not number "4" since he said "start from vertex 2 to nowhere -> return vertex 1" -> so his answer is g(2,{1}) =5.
I have misled as well, but I listen to him carefully so maybe we are misled at this point.
11:28, g(2,{4}) = 18 not 8 (Cause g(4,1) = 8 + g(2, 4) = 10 -> 18), and the continuous answer is similar to Mr. @kennethi.e answer.
I'm pass this exam tq soo much sir 👏😍
U teach very well sir no doubt ...bt best thing what i found is tha u take examples from text book ...it makes very easy to understand us the concept
Abdul Sir you are the best! 🙏🏽
Sir, I believe Dynamic Programming is an improvement over Brute Force, although approach is similar. But in this particular example, I can't find any improvement, it looks exactly Brute Force. My question is what is the difference between Brute Force and Dynamic P, if we solve this problem using both?
Good question. I also don't see any improvement of using dynamic programming in this case.
This is already a little smaller than the brute force. Brute force is O(n!) which means the table would have 24 entries. He doesn't work the last 3 entries for his table, but there are 15 total. This improvement gets more dramatic as the problem increases in size.
memory..i guess
Hello sir !
play your video just before 13:01....you have completed a section in which
g(2,{3})=15
g(2{4})= 8
in above eqn you have misplaced I think...
the 1st one should 6 or the 2nd one should 18.
in both the cases you have used different methods.
You should explain time complexity with the help of algorithm. Overall it's was very good.
Ris Ab Agreed
its on the order of n!
Super explain sir thanks for wonderful information for tsp
Today Daa exam thanks
To me it looks like Recursion problem instead of Dynamic Programming. Can someone explain, how DP is used here, there is no optimal substructure here.
It is finding the shortest route for one node in step one, for 2 node in the second step and so on..
Recursion is brute force, DP means eliminating a path as you calculate the minimal cost at each step.
ua-cam.com/video/K3rYJYi2geE/v-deo.html
@@pkhris ua-cam.com/video/K3rYJYi2geE/v-deo.html
@@AmitKumar-tw1sj ua-cam.com/video/K3rYJYi2geE/v-deo.html
Masha Allah your teaching very nice sir...,
bari mama mass. I fan u. Khuda Haafiz
So this is pretty much the same as the multistage graph problem? The algorithm starts finding out minimum costs from the end towards the starting point. The only difference is instead of having a table saving the shortest path to the next node, we have have all the combinations as some sort of list
One big alumni network in the comments😂. Great explanation, thanks sir!
Sir, its my request to you to please stand at the side for 2-3s before you erase the board. This makes it easier to make notes by directly taking screenshots.
i was searching for this nice explaination
Today DAA Exam.
Thanks ❤
Excellent teaching ❤
This is extremely useful. Thanks a lot!
why dont you publish a book? awesome teaching
Hii sir,
11:12 the cost g(2,{3}) is 6
Thanks slot sir I really feel very happy after seeing u r videos it's really awesome I learned alot tqqqqqqqqq so Much
Tomorrow DAA Exam Ajeenkya DY Patil University
Thank you❤
Tomorrow day exam mama ..thanks 👍
It is concept of discrete Mathematics and Graph Theory?
NICE SUPER EXCELLENT MOTIVATED
Sir please make video on longest common subsequence
at 8:51 as well as at 9:49, why 'k' is being subtracted?
Great Videos Sir!! Really helps a lot.
Nice explanation sir
Can you please make some videos on in depth explanation on making these general dp formulas and determining if we can apply dp in a particular problem?
today is my DAA exam
Who had came for oneday Batting like it 😅
Haslee - free .... U blessed me
Can we expect TSP problem with branch and bound.
please share the link if you have done it before.
ua-cam.com/video/1FEP_sNb62k/v-deo.html
CMR 🔥🔥 oka like eskondii 😂😂
sir i love your teaching method
5:22 "...Now we here"
lmao
😂😂🤣😑 funny
Y??
Great explanation sir, but I have a question about it. You got the minimum value to travel to all vertices to be 35, but how do you know its going 1-2-4-3 without using the tree?
You can find this from the tables. To find the first leg, select the node with the lowest cost for N nodes starting with the origin. From there, select the node with lowest cost for N-1 nodes starting with the node you selected. Continue until you have a full tour.
This algorithm is different from the way I originally learned to solve TSP (I would refer to this as back-to-front; I originally learned front-to-back). I implemented it for practice and noticed something wonderful about it. Rather than having to infer the best tour from the cost table you can build up a path table as you go. e.g. when you are calculating `g(2, {3,4})` you compare the values of `c[2][3] + g(3, {4})` and `c[2][4] + g(4, {3})`. You end up choosing `c[2][4] + g(4, {3})`, with a value of 25. If you also record that you picked `4` as the next node instead of `3`, then you can build the optimal tour back up directly from the table without needing to reference the adjacency matrix again.
There was a mistake from g(2, {4}) to g(4, {4})..The solutions are g(2, {4}) = 18, g(3, {2}) = 18, g(3, {4}) = 20, g(4, {2}) = 13, g(4, {3}) = 15
(Copied from another comment to ensure double check)
Yes there was a mistake , what you have written is correct
11:24 sir is wrong.. but it did not make any change in the final answer...
So don't become panic ..see this comment don't waste time..