4.7 Traveling Salesperson Problem - Dynamic Programming

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.co...
Courses on Udemy
================
Java Programming
www.udemy.com/...
Data Structures using C and C++
www.udemy.com/...
C++ Programming
www.udemy.com/...

[@abhishekvarma3673]

Tomorrow DAA exam very Thanks 😊

[@CellerCity]

Lol 😂. It's my turn now

[@sudhanshusharma6700]

Today DAA exam in 1 hr😌

[@XINgalaxy]

@@CellerCity haha now it's my turn👻

[@justjukebox]

@@XINgalaxy Army💜🤣 Mine too 🤝

[@AKASHRAJ-xs5ed]

And mine is today after 1 hour 🙃🙂

[@kennethi.e]

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]

👍

[@xit]

Yeah!, I was thinking the same thing.

[@xit]

@@abdul_bari No problem. Your students can easily overcome minor mistakes. At the end of the day " we are your student ".

[@arjunguleria2318]

thanks bhai i was confused with this one

[@dayakarp631]

Yes i also noticed

[@saisurya1723]

Me, who Today having DAA exam😂

[@shambhavirani87]

Same dude 😂

[@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]

Yes bro , he had written wrong I was also confused All are saying well explained sir but one is observing the mistakes

[@prasathmsd0760]

All the best for tomorrow's exam 😂 👍

[@aditnigam8281]

thank you sir finally I understand how to solve this types of problem ....😊

[@wentworthmiller1890]

Simply outstanding! Doesn't get better than this.

[@mdrukonuzzaman8347]

Sir, you are a great teacher . Your explanation is excellent . wish you all the best and you live long with sound health . Thanks.

[@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

[@jayasuryak9551]

Sir g(2,{3})= is 6 right how come 15

[@Jean-yk9eo]

11:23 forward has some mistakes, but thanks for the video. I kinda understand

[@135jyotirmoygoswami5]

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)

[@rjayashree8780]

Yes there was a mistake , what you have written is correct

[@Vendettaaaa666]

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]

thank you

[@kevintyrrell7409]

@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]

@@kevintyrrell7409 it is NP-Hard afterall

[@sbtopzzzlg7098]

@@kevintyrrell7409 at least we're eliminating the computational redundancy while reaching each possibility

[@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.

[@biprodeepdas3593]

Sir padhai khtm krne ka shortest path nikalne k liye koi algorithm hai kya sir 😢😢

[@soloeditz7581]

g(2,{3})=15

[@isaaca3849]

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]

You are crt bro

[@breakyourthoughts7364]

correct bro

[@nanduugee]

@@vijaykumarRC1215 🥕

[@federickelvis247]

You saved me !!

[@bilalchandio1]

MashaAllah beautifully explained sir. Thanks for uploading such a great lecture. #Balochistan

[@baal1297]

praise to mulla allah

[@bilalchandio1]

@@baal1297 I didn't get.

[@gani_yt]

Tomorrow Ada exam Thanks 👍

[@onlinesocialworld7504]

He is teaching for the sake of TEACHING..and unlike others not asking for Like, Share And Subscribe 🙏🙏🙏🙏

[@mysticlunala8020]

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]

I think you mean love. Sake usually implies he's doing it because he has to not because he wants to.

[@shauryaverma292]

also incorrectly

[@lukemortin8680]

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 , i have exam tomorrow please make a new video in this topic with correction.

[@darthashpie]

Watching this a night before ADA exam . Wish me luck

[@easycodingconcepts6642]

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.

[@AmitKumar-tw1sj]

It is finding the shortest route for one node in step one, for 2 node in the second step and so on..

[@pkhris]

Recursion is brute force, DP means eliminating a path as you calculate the minimal cost at each step.

[@newsanalysis4831]

kzbin.info/www/bejne/gWTVin2Pnpeam6c

[@newsanalysis4831]

​@@pkhris kzbin.info/www/bejne/gWTVin2Pnpeam6c

[@newsanalysis4831]

​@@AmitKumar-tw1sj kzbin.info/www/bejne/gWTVin2Pnpeam6c

[@mohammedabdulrafay8763]

Sir you have done a mistake. The correct answer is g(2,{4})=18

[@babuprasadr4205]

Even my subject faculty is watching your videos to take classes for us sir😂😂

[@mdarshad9877]

Who had came for oneday Batting like it 😅

[@salilchincholikar]

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..

[@nxtstory5363]

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..

[@StarkPlayz]

Thank you sir understood this very clearly. Except for that small mistake of g(2,{4}) everything is explained well and fine. ⚡

[@28-anishanne86]

Today Daa exam thanks

[@reddyr4420]

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]

NOT ONLY YOUR COLLEGE! HE IS HELPFULL FOR EVERY COLLEGE STUDENT PURSUING BTECH IN CSE.

[@RyanMJohn-xw6bh]

pass hua?

[@BhuvaaneshRajeswaran]

Tomorrow DAA exam....my DAA mam is a waste...thought me nothing but how to pluck the hair........thankyou for explaining sir

[@grasshopperweb]

I don't understand how this isn't brute force. Aren't we calculating every subtree in the end anyways?

[@Gashdal]

fun little exercise: scroll through the comments of this video and count all the times someone says sir

[@AkinaGaurdrailerR35]

😅

[@Hetrush]

sir please check your explanation at 11.23 of your video.......some mistake s happening

[@prateekgupta7544]

He maintained gender equality. Not salesman but sales person😁

[@Farahat1234]

Ky ky hua ky aakhir😆😆😆

[@corntheatre1398]

7:55 DYNAMIC PROGRAMMING approach

[@sankarkuppu5031]

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]

did you pass? I have DAA tomorrow, asking for a friend

[@akshatkatal7055]

@@nanduugee I have daa exam tomorrow what should do. To pass

[@thecreativemind...1104]

@@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

[@tushar_pawar040]

Our teachers are watches your videos sir before teaching a lecture

[@abhiyaanand8689]

Teacher is at another level 🤩👏🏼 now I can do it on my own..thank you sir

[@bswethar]

You the best in explaining these tough algorithms in an layman language. Thank you sir!!

[@newsanalysis4831]

kzbin.info/www/bejne/gWTVin2Pnpeam6c

[@kiruthigav6704]

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

[@kalp2586]

Best explanation i've seen.

[@sulemanali4023]

Sir you are great sir, this help me lot in #DAA exam 🙏🙏🔥

[@it_is_Mighty]

Daa exam is tommorow ... i am here 😂

[@Manisci3]

thank yoou so much sir you make feel like a superman

[@ccmrshrdnt]

Thank you so much Sir,

[@adipatell]

Such a time waste

[@Libertoso]

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

[@abhay_Awasthicarguy7777]

Tomorrow is college exam very thank you.

[@ishansharma5922]

Akgec....

[@aneeshaprasad9300]

Biggggg thankyouuuu sir

[@wycliffeottawa7998]

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

[@OneT0One]

This Channel deserves more subscribers and views

[@adithyavelaparthi1820]

what the F the total sol is wrong

[@rohankottawar96]

why dont you publish a book? awesome teaching

[@chinthalasundarramireddy6048]

Sir you made a mistake at 11:24

[@ParQuik]

bari mama mass. I fan u. Khuda Haafiz

[@thanujasrinivas504]

Your lectures helped me to pass in my examinations 🙏

[@MILINSHOYRajagiri]

nee thooti potti machu

[@agamersdiary1622]

started from the bottom, now we're here...

[@stuthiharshitha7431]

Tomorrow daa sem tq sir

[@yashugaming_yt8089]

Tomorrow is daa exam tq sir ❤

[@hubssc5748]

HOW MANY GNDUIANs?

[@technologywalaguru]

Watching during exam😂😂

[@onuryorganci8082]

Distance table must be symmetric. e.g. If 2 to 3 is 9 so how can 3 to 2 be 13? :D They are the same pats ;)

[@onuryorganci8082]

Abdul Bari whatever it is, road, path or any distance, 2 to 3 and 3 to 2 (and other lines) are the same (as shown on your figure). Otherwise the travelling salesman problem becomes another problem

[@shahveziqbal5206]

Thankyou sir

[@aftabnadaf9843]

Sir you are created wrong table for second last nodes: g(2,{4})=18 g(3,{2})=18 Remaining values are also wrong

[@nextleveltech267]

Thanks sir 🙏🙏

[@dr.vinodkumarchauhan3454]

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?

[@jamesmufugi5316]

Good question. I also don't see any improvement of using dynamic programming in this case.

[@AdamHoelscher]

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.

[@e_51_shubhamdebnath43]

memory..i guess

[@1n1go91]

life changing

[@turtle8428]

3:00

[@v12_jatt]

Aur Cu walo kya haal hai

[@huntermages9037]

DAA is the worst case subject 🤦‍♂️😌

[@aaheng97]

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?

[@AdamHoelscher]

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.

[@AdamHoelscher]

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.

[@librae-5664]

사랑한다 선생님

[@Pleiades_Ayesha]

I should have watched this in regular of my examination 😩 Now I can pass my exam 😃

[@berniethedonut9097]

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]

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.

[@danishnabeel2101]

Can you make a video on inventory transshipment problem for individual retailers in the system ?

[@aayushagarwal5666]

The way of teaching is like bottom up approach - first solve , then derive algorithm ! Great videos - all of them : )

[@joshywherry5924]

it's 2024, I'm having my DAA exam tomorrow.

[@Vishnu-id1ts]

CMR 🔥🔥 oka like eskondii 😂😂

[@ayan1751]

You are doing a great help to students like us sir... huge repect

[@awalktoinfinity665]

One serious doubt , in the video we already took the path in the tree , then you took bottom to up approach .but sir you took the cost of bottom to up but we are going from top to bottom , and both the costs are different . Maybe silly question but still Please clarify sir .

[@awalktoinfinity665]

But sir , if we follow top to bottom procedure then also answer is same then why used bottom to top approach ? Why and when do we use bottom to top approach? And glad you replied .

[@gowtham2775]

@@awalktoinfinity665 I think solving bottom to up is useful while solving without using formula. That way we can ignore few branches, if it's an expensive route while coming from top to bottom we have to find complete cost on all the routes

[@awalktoinfinity665]

@@gowtham2775 see , we have to travel from the topmost root to lowermost root and the tree drawn shows all the possible paths.. If you take the up to down calculation then the answer will be also same . ( I have done it) Here sir also has started from down to up but he has taken the cost from up to down . (Since up to down and down to up both costs are different and we have to go from up to down so we have to take up to down cost ) . But question lies here why we take bottom to up approach

[@pspkfan9913]

Sir wonderful explaination.hats off sir😍😍

[@milan_shah]

at 8:51 as well as at 9:49, why 'k' is being subtracted?

[@shubham_navlakha]

2to3 is right, but after that 2to4, 3to2, 3to4, 4to2 and so on should be 18, 18, 20, 13, 15.

[@dlsmikhael6232]

Watching this video after 5 years Tomorrow is my DAA exm

[@varrjames186]

Subtitles would have been good. I can hardly understand a word that he is saying.

[@dogmanvfx]

I think there is mistake in this problem sir, but the way you teaching students can easily find that error😍

[@ganeshjaggineni4097]

NICE SUPER EXCELLENT MOTIVATED

[@khushipatil1577]

your solution is wrong sir in case 2 please delete the video else it'll misconceptualize us!

[@heymama9815]

Hello jeipratha mam ke bachho whats up

[@manojmuraboina6834]

Can we expect TSP problem with branch and bound. please share the link if you have done it before.

[@ashishupadhyay5407]

kzbin.info/www/bejne/Z3eogZKpg8dpaM0

[@gouravmotwani]

After 45 minutes DAA exam.

[@KingKhan-bi7kb]

You know you will top when sir abdul bari is there. Thx sir

[@adipatell]

Har ek video me kuch na kuch galti karte ho sara mood kharab kar dete ho!

[@top10-r2f]

Thank you sir❤🙏

[@gurpreettata]

great explanation but it could have been awsome if algorithm would have explained with any code (C/C++)

[@tejaswalondre2891]

Sir u have written g of remaining vertex 4 and so on .........

[@Nam_David]

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.

[@adityakrishna11]

9:26 rip

[@AdeshPaul]

??

[@b3aStYyY]

lmao :D :D