4.7 Traveling Salesperson Problem - Dynamic Programming

  Рет қаралды 1,519,995

Abdul Bari

Abdul Bari

6 жыл бұрын

4.7 Traveling Salesman Problem - Dyn Prog -Explained using Formula
• 4.7 [New] Traveling Sa...
CORRECTION: while writing level 3 values, mistakenly I wrote 4 level values
Travelling Salesperson problem is solved using Brute Force approach and Dynamic Programming
PATREON : www.patreon.com/bePatron?u=20...
Courses on Udemy
================
Java Programming
www.udemy.com/course/java-se-...
Data Structures using C and C++
www.udemy.com/course/datastru...
C++ Programming
www.udemy.com/course/cpp-deep...

Пікірлер: 555
@abhishekvarma3673
@abhishekvarma3673 3 жыл бұрын
Tomorrow DAA exam very Thanks 😊
@AMAN-dt9ry
@AMAN-dt9ry 2 жыл бұрын
Lol 😂. It's my turn now
@sudhanshusharma6700
@sudhanshusharma6700 2 жыл бұрын
Today DAA exam in 1 hr😌
@Xingalaxy
@Xingalaxy 2 жыл бұрын
@@AMAN-dt9ry haha now it's my turn👻
@justjukebox
@justjukebox 2 жыл бұрын
@@Xingalaxy Army💜🤣 Mine too 🤝
@AKASHRAJ-xs5ed
@AKASHRAJ-xs5ed 2 жыл бұрын
And mine is today after 1 hour 🙃🙂
@kennethi.e
@kennethi.e 5 жыл бұрын
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
@karthikpallikonda8922
@karthikpallikonda8922 5 жыл бұрын
👍
@xit
@xit 5 жыл бұрын
Yeah!, I was thinking the same thing.
@xit
@xit 5 жыл бұрын
@@abdul_bari No problem. Your students can easily overcome minor mistakes. At the end of the day " we are your student ".
@arjunguleria2318
@arjunguleria2318 5 жыл бұрын
thanks bhai i was confused with this one
@dayakarp631
@dayakarp631 5 жыл бұрын
Yes i also noticed
@wentworthmiller1890
@wentworthmiller1890 5 жыл бұрын
Simply outstanding! Doesn't get better than this.
@mdrukonuzzaman8347
@mdrukonuzzaman8347 6 жыл бұрын
Sir, you are a great teacher . Your explanation is excellent . wish you all the best and you live long with sound health . Thanks.
@Vendettaaaa666
@Vendettaaaa666 4 жыл бұрын
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!
@vibhavrathee6788
@vibhavrathee6788 3 жыл бұрын
thank you
@kevintyrrell7409
@kevintyrrell7409 2 жыл бұрын
@vendettaaaa666 So essentially all this is, is caching distances into a giant lookup table? That still seems very complexity-demanding to solve this problem.
@harsh3948
@harsh3948 2 жыл бұрын
@@kevintyrrell7409 it is NP-Hard afterall
@sbtopzzzlg7098
@sbtopzzzlg7098 Жыл бұрын
@@kevintyrrell7409 at least we're eliminating the computational redundancy while reaching each possibility
@deepak-ly3ob
@deepak-ly3ob Жыл бұрын
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.
@ravipaliwal9726
@ravipaliwal9726 Жыл бұрын
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
@aditnigam8281
@aditnigam8281 5 жыл бұрын
thank you sir finally I understand how to solve this types of problem ....😊
@aayushagarwal5666
@aayushagarwal5666 6 жыл бұрын
The way of teaching is like bottom up approach - first solve , then derive algorithm ! Great videos - all of them : )
@bswethar
@bswethar 3 жыл бұрын
You the best in explaining these tough algorithms in an layman language. Thank you sir!!
@newsanalysis4831
@newsanalysis4831 Жыл бұрын
kzfaq.info/get/bejne/gZmijK2KzpjLlXk.html
@abhiyaanand8689
@abhiyaanand8689 Жыл бұрын
Teacher is at another level 🤩👏🏼 now I can do it on my own..thank you sir
@ayan1751
@ayan1751 Жыл бұрын
You are doing a great help to students like us sir... huge repect
@StarkPlayz
@StarkPlayz 5 жыл бұрын
Thank you sir understood this very clearly. Except for that small mistake of g(2,{4}) everything is explained well and fine. ⚡
@himareddy3240
@himareddy3240 4 жыл бұрын
You make the subject very easy sir. Thank you so much.
@reddyr4420
@reddyr4420 6 жыл бұрын
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 !
@ratanupadhyay9497
@ratanupadhyay9497 5 жыл бұрын
NOT ONLY YOUR COLLEGE! HE IS HELPFULL FOR EVERY COLLEGE STUDENT PURSUING BTECH IN CSE.
@RyanMJohn-xw6bh
@RyanMJohn-xw6bh 8 ай бұрын
pass hua?
@KingKhan-bi7kb
@KingKhan-bi7kb 5 жыл бұрын
You know you will top when sir abdul bari is there. Thx sir
@sanyam188
@sanyam188 5 жыл бұрын
Sir your videos are too good and easy to understand... I studied from your algorithm Playlist only... You're a saviour... Thanks a ton!!!
@wycliffeottawa7998
@wycliffeottawa7998 5 ай бұрын
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
@Jean-yk9eo
@Jean-yk9eo 4 жыл бұрын
11:23 forward has some mistakes, but thanks for the video. I kinda understand
@OneT0One
@OneT0One 3 жыл бұрын
This Channel deserves more subscribers and views
@kalp2586
@kalp2586 6 жыл бұрын
Best explanation i've seen.
@pspkfan9913
@pspkfan9913 6 жыл бұрын
Sir wonderful explaination.hats off sir😍😍
@saisurya1723
@saisurya1723 Ай бұрын
Me, who Today having DAA exam😂
@shambhavirani87
@shambhavirani87 Ай бұрын
Same dude 😂
@rishikakapoor6220
@rishikakapoor6220 5 жыл бұрын
Great explanations!! thank you sir.
@02andrewedwiny14
@02andrewedwiny14 4 жыл бұрын
Thank u ji.. For helping before exam day..❤❤nice teaching skills saab
@sankarkuppu5031
@sankarkuppu5031 4 жыл бұрын
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
@nanduugee
@nanduugee 2 жыл бұрын
did you pass? I have DAA tomorrow, asking for a friend
@akshatkatal7055
@akshatkatal7055 2 жыл бұрын
@@nanduugee I have daa exam tomorrow what should do. To pass
@thecreativemind...1104
@thecreativemind...1104 7 ай бұрын
@@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
@darthashpie3370
@darthashpie3370 5 жыл бұрын
Watching this a night before ADA exam . Wish me luck
@onlinesocialworld7504
@onlinesocialworld7504 3 жыл бұрын
He is teaching for the sake of TEACHING..and unlike others not asking for Like, Share And Subscribe 🙏🙏🙏🙏
@mysticlunala8020
@mysticlunala8020 2 жыл бұрын
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.
@ActuallyAudacity
@ActuallyAudacity Жыл бұрын
I think you mean love. Sake usually implies he's doing it because he has to not because he wants to.
@shauryaverma292
@shauryaverma292 Жыл бұрын
also incorrectly
@Sandhya-wd8jg
@Sandhya-wd8jg Жыл бұрын
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?
@bolimeradinesh2638
@bolimeradinesh2638 3 ай бұрын
Yes bro , he had written wrong I was also confused All are saying well explained sir but one is observing the mistakes
@aeshgupta5662
@aeshgupta5662 5 жыл бұрын
Great Videos Sir!! Really helps a lot.
@thanujasrinivas504
@thanujasrinivas504 3 жыл бұрын
Your lectures helped me to pass in my examinations 🙏
@MILINSHOYRajagiri
@MILINSHOYRajagiri Жыл бұрын
nee thooti potti machu
@yesumashi9433
@yesumashi9433 2 жыл бұрын
Abdul Sir you are the best! 🙏🏽
@mythiliptv3490
@mythiliptv3490 4 жыл бұрын
Thanks slot sir I really feel very happy after seeing u r videos it's really awesome I learned alot tqqqqqqqqq so Much
@chintan_rana
@chintan_rana 5 жыл бұрын
Thank you sir i gave exam today for algorithm and my exam was good thnx to you
@sulemanali4023
@sulemanali4023 2 жыл бұрын
Sir you are great sir, this help me lot in #DAA exam 🙏🙏🔥
@Soniya0715
@Soniya0715 8 ай бұрын
Simple and easy explanation nice 😊we are easily understanding u r simply way ☺️
@gahlyogu4570
@gahlyogu4570 5 жыл бұрын
very good! thorough explanation
@bilalchandio1
@bilalchandio1 5 жыл бұрын
MashaAllah beautifully explained sir. Thanks for uploading such a great lecture. #Balochistan
@baal1297
@baal1297 3 жыл бұрын
praise to mulla allah
@bilalchandio1
@bilalchandio1 3 жыл бұрын
@@baal1297 I didn't get.
@galadesonne5643
@galadesonne5643 5 жыл бұрын
Great explanation! Thx!
@dvddisk
@dvddisk 6 ай бұрын
This is extremely useful. Thanks a lot!
@dogmanvfx
@dogmanvfx Жыл бұрын
I think there is mistake in this problem sir, but the way you teaching students can easily find that error😍
@46-shabnambashir50
@46-shabnambashir50 Жыл бұрын
i was searching for this nice explaination
@ParveenSk-xt5rx
@ParveenSk-xt5rx 3 жыл бұрын
I should have watched this in regular of my examination 😩 Now I can pass my exam 😃
@ankk98
@ankk98 6 жыл бұрын
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?
@bhushankumarkhade2985
@bhushankumarkhade2985 Жыл бұрын
Bahut acche se samaj me aaya sir... Thank you...
@gulaamnabim822
@gulaamnabim822 5 жыл бұрын
Masha Allah your teaching very nice sir...,
@5sempart49
@5sempart49 2 жыл бұрын
sir i love your teaching method
@Manisci3
@Manisci3 Ай бұрын
thank yoou so much sir you make feel like a superman
@babuprasadr4205
@babuprasadr4205 8 ай бұрын
Even my subject faculty is watching your videos to take classes for us sir😂😂
@PankajKumar-pf6sh
@PankajKumar-pf6sh 6 жыл бұрын
Sir please make video on longest common subsequence
@prasenjitsaha5322
@prasenjitsaha5322 5 жыл бұрын
Thanks a lot for these wonderful videos.
@prasenjitsaha5322
@prasenjitsaha5322 5 жыл бұрын
You have very nice voice. It makes listening to you more enjoyable.
@syedmahasibali2324
@syedmahasibali2324 5 жыл бұрын
Well understood by this video Great ......
@niceguy9048
@niceguy9048 3 жыл бұрын
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....
@prateektalukdar4657
@prateektalukdar4657 2 жыл бұрын
Hello, I just saw your video on travelling sales man problem. I had another problem that is similar to this one, however we have the revenue at each location on a certain day and we want to travel through any combination of cities to figure out the maximum revenue possible. Do you have any suggestions on how I could solve this?
@arjunsingharjunsingh1634
@arjunsingharjunsingh1634 6 жыл бұрын
Best algorithms lecture
@jahanvikhedwal1107
@jahanvikhedwal1107 4 жыл бұрын
Really nice explanation sir.
@Libertoso
@Libertoso 3 жыл бұрын
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
@tushar_pawar040
@tushar_pawar040 Жыл бұрын
Our teachers are watches your videos sir before teaching a lecture
@ihebbendebba2978
@ihebbendebba2978 4 жыл бұрын
The best teacher in the world
@IIBCARMTCIAcia
@IIBCARMTCIAcia Жыл бұрын
Very excellent thank you your valuable team
@prasathmsd0760
@prasathmsd0760 2 ай бұрын
All the best for tomorrow's exam 😂 👍
@harininuthalakanti8256
@harininuthalakanti8256 7 ай бұрын
I'm pass this exam tq soo much sir 👏😍
@gurpreettata
@gurpreettata 6 жыл бұрын
great explanation but it could have been awsome if algorithm would have explained with any code (C/C++)
@suhailcool13111985
@suhailcool13111985 5 жыл бұрын
Sir . So clear explanation . One doubt I have is in the formula you have used - {K}. Can you explain that with an example which has to be subtracted.
@itsme-sm9jp
@itsme-sm9jp Ай бұрын
This is morning 5 am and today is daa exam but I'm ok daa easy and his lectures are very useful ❤😊
@diverseaspirants
@diverseaspirants 6 жыл бұрын
Thank You So Much Sir..nice explanation SIr!!!
@akashreddyjammula3684
@akashreddyjammula3684 3 жыл бұрын
Nice work with cool explaination
@golsocial4769
@golsocial4769 3 жыл бұрын
thanks alot. it was so helpful🙏🏻🙏🏻🙏🏻
@anantgupta6642
@anantgupta6642 5 жыл бұрын
Sir I want to ask if there is infinity in the matrix then what cost will be considered in the tree for that
@user-rv8yx3df9g
@user-rv8yx3df9g 9 ай бұрын
Tomorrow DAA exam....my DAA mam is a waste...thought me nothing but how to pluck the hair........thankyou for explaining sir
@isaaca3849
@isaaca3849 5 жыл бұрын
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
@vijaykumarRC1215
@vijaykumarRC1215 3 жыл бұрын
You are crt bro
@breakyourthoughts7364
@breakyourthoughts7364 2 жыл бұрын
correct bro
@nanduugee
@nanduugee 2 жыл бұрын
@@vijaykumarRC1215 🥕
@fahmidaahmed6669
@fahmidaahmed6669 5 жыл бұрын
much helpful....thanks sir.
@vamsicherukuri5963
@vamsicherukuri5963 6 жыл бұрын
Sir plz tell algorithm
@priyankaraikwar9367
@priyankaraikwar9367 6 жыл бұрын
Haslee - free .... U blessed me
@rohankottawar96
@rohankottawar96 6 жыл бұрын
why dont you publish a book? awesome teaching
@jayrajvardhan9906
@jayrajvardhan9906 2 ай бұрын
Thank you sir for wonderful explanation
@danishnabeel2101
@danishnabeel2101 5 жыл бұрын
Can you make a video on inventory transshipment problem for individual retailers in the system ?
@ManurManasa
@ManurManasa 7 ай бұрын
Excellent teaching ❤
@BM-sc1pc
@BM-sc1pc 6 жыл бұрын
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
@manojmuraboina6834
@manojmuraboina6834 6 жыл бұрын
Can we expect TSP problem with branch and bound. please share the link if you have done it before.
@ashishupadhyay5407
@ashishupadhyay5407 5 жыл бұрын
kzfaq.info/get/bejne/Z6x1g8Kks8iaYp8.html
@Sanatanabhishekaa28498
@Sanatanabhishekaa28498 6 жыл бұрын
Please add video on travelling salesman using Branch and Bound method
@yuninrju6213
@yuninrju6213 5 жыл бұрын
awesome way to explain
@fatihcenesiz9587
@fatihcenesiz9587 5 жыл бұрын
you are making it from hard way
@chinnireddy8236
@chinnireddy8236 5 жыл бұрын
Awesome teaching
@shreyashachoudhary480
@shreyashachoudhary480 2 жыл бұрын
Really understandable.
@adarshbalachandar8680
@adarshbalachandar8680 2 ай бұрын
One big alumni network in the comments😂. Great explanation, thanks sir!
@berniethedonut9097
@berniethedonut9097 3 жыл бұрын
great video and easy to understand! however, im wondering if other routes would have lower cost compared to starting from location 1? if yes, how should i find out let's say there are too many locations eg. 10? i tried substituting i = 3, the cost is also $35. the route is 3-1-2-4-3. even though the route is the same, it still shows that there is an alternative starting point so does it mean i can start with either 1 or 3 to my likings? would appreciate if someone can explain, im learning this for a school assignment!
@AdamHoelscher
@AdamHoelscher 2 жыл бұрын
The routes are all cycles. 3-1-2-4-3 had the same cost as 1-2-3-4-1. One you've found an optimal tour you can just rotate the start to a different place.
@federickelvis247
@federickelvis247 Жыл бұрын
You saved me !!
@rishabjain5890
@rishabjain5890 6 жыл бұрын
You should explain time complexity with the help of algorithm. Overall it's was very good.
@chinmoydutta9931
@chinmoydutta9931 6 жыл бұрын
Ris Ab Agreed
@antigy7962
@antigy7962 5 жыл бұрын
its on the order of n!
@milan_shah
@milan_shah 4 жыл бұрын
at 8:51 as well as at 9:49, why 'k' is being subtracted?
@meaparadox5864
@meaparadox5864 6 жыл бұрын
Great video sir
@capitallaterA
@capitallaterA 5 жыл бұрын
time duration 11:14, I am little bit confused Sir at this point And the rest of it is very much helpful.
@ganeshjaggineni4097
@ganeshjaggineni4097 Жыл бұрын
NICE SUPER EXCELLENT MOTIVATED
@talarikrishnamurthy3011
@talarikrishnamurthy3011 2 жыл бұрын
Tq sir I cleared my subject
@zahidfayaz
@zahidfayaz 5 жыл бұрын
Basit Sir I am able to understand why we are subtracting {K} to g(k,{2,3,4})
@bushratabassum1575
@bushratabassum1575 5 жыл бұрын
Sir, do i have to remember the formula as well if i understand the problem???
@yashugaming_yt8089
@yashugaming_yt8089 9 ай бұрын
Tomorrow is daa exam tq sir ❤
@ratankumar1399
@ratankumar1399 4 жыл бұрын
sir ,what is shortesr link strategey for trvelling sales man problem?
@banapurammadhuri9090
@banapurammadhuri9090 5 жыл бұрын
sir plz explain their respective algorithmz plz sir
@PalukuriSuseela
@PalukuriSuseela 7 ай бұрын
Good explanation thank you sir
@soloeditz7581
@soloeditz7581 2 жыл бұрын
g(2,{3})=15
7.3 Traveling Salesman Problem - Branch and Bound
24:42
Abdul Bari
Рет қаралды 1,7 МЛН
3.6 Dijkstra Algorithm - Single Source Shortest Path - Greedy Method
18:35
Cool Items! New Gadgets, Smart Appliances 🌟 By 123 GO! House
00:18
123 GO! HOUSE
Рет қаралды 17 МЛН
Nastya and SeanDoesMagic
00:16
Nastya
Рет қаралды 26 МЛН
Clowns abuse children#Short #Officer Rabbit #angel
00:51
兔子警官
Рет қаралды 76 МЛН
MISS CIRCLE STUDENTS BULLY ME!
00:12
Andreas Eskander
Рет қаралды 15 МЛН
Traveling Salesman Problem using Dynamic Programming | DAA
31:33
Jenny's Lectures CS IT
Рет қаралды 534 М.
Greedy Algorithm - Jump Game - Leetcode 55
0:58
Greg Hogg
Рет қаралды 37 М.
3.5 Prims and Kruskals Algorithms - Greedy Method
20:12
Abdul Bari
Рет қаралды 2,7 МЛН
0/1 knapsack problem | example| dynamic programming
14:42
Education 4u
Рет қаралды 313 М.
4.1 MultiStage Graph - Dynamic Programming
21:07
Abdul Bari
Рет қаралды 966 М.
4.5 0/1 Knapsack - Two Methods - Dynamic Programming
28:24
Abdul Bari
Рет қаралды 2,7 МЛН
Traveling Salesman Problem | Dynamic Programming | Graph Theory
20:28
Cool Items! New Gadgets, Smart Appliances 🌟 By 123 GO! House
00:18
123 GO! HOUSE
Рет қаралды 17 МЛН