4.7 [New] Traveling Salesman Problem - Dynamic Programming using Formula
Вставка
- Опубліковано 2 жов 2024
- Traveling Salesman Problem - Dynamic Programming - Explained using Formula
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/...
You are going to single-handedly get me through my algorithms course. It's so clear, almost obvious, when you explain these things, where seemed so murky when I first heard them. Very much appreciated.
The best algorithm explaining teacher I have ever seen. Thanks Abdul Bari sir.
Abdul Bari sir I randomly landed in your page , after that I cant stop myself from binge watching all your Algo videos , your videos are amazing n Iam loving it
Algo ki sb videos dekh kr ke bol skte ke yr mera kafi had tk algorithm clear ho gya
Mtlb fir me ja kr k codeforces wagera ki c type problems solve kr pao ga
11:36 apke sath ek chota sa prank hua, camera ke saamne dekh ke smile karde
U r out of mind
@@sudhagbhat8226 He was just joking, don't take it seriously.
😂🔥
Dear sir,
This semester is very short, 3 months approximately
So our professor can't complete the whole syllabus
But our college professor is referring your channel for learning
You are awesome sir❤
Cannot see overlapping sub problem
Exactly what I was wondering
Thank you.
I found deriving the formula, than implementing one more effective. But it was nice to see the other way as well.
Good, is this part of some of your Udemy course. Please advise.
For my own reference:
final path : {1,2,4,3,1}
Awesome explanation Sir... 👍👌
Thanks alot... 💕
this video is much clear than previous one
give a medal to this man
If in the source matrix, position [3,1] value we change it as value '0'. Then what should be the Path?
Thank you very much. You are a genius. 👍👍🔝🔝🙏🙏👌👌
00:01 Explaining the traveling salesman problem using dynamic programming formula.
02:15 The formula explains how to find the minimum cost for visiting the remaining vertices.
04:12 Finding the minimum value by using dynamic programming formula
06:06 Dynamic programming for solving traveling salesman problem
08:27 Discussing the recursive tree execution for solving the traveling salesman problem using dynamic programming.
10:27 Dynamic programming is done with tabular values.
12:43 Finding smallest values first using dynamic programming
14:47 The shortest route for the Traveling Salesman Problem using Dynamic Programming is 35.
Professor, I asked you this in a different video but I have noticed the following:
If I click on your course for data structure, it sends me to Udemy with a price of $10 which is correct but it clearly says that this offer is for “new students only”. Since I already have an account, as soon as I log in the price goes up. I could create a new account with a different email but I am hoping you can look into this.
I have also noticed that at random times on different days, the offer is different. Sometimes is $170, other times is $90, or $19 etc. I don’t believe the offer will be $10 during thanksgiving promotion as you stated. But even if it is, please let me know if the only option for me is to create a new account so that I can pay the $10.
I am a college student and while I could pay $20 (which is what it goes up to when I log in if the offer is $10) I am suffering from greedy syndrome. You see, since you have already advertised it as $10 then I only want to pay $10 :). That’s how greedy algorithm works professor! I can’t go on paying $20 when there clearly is a lower weight Lol
Please let me know!
Sir please provide the code also for some of the algorithms of which code has not been provided .
be grateful
kya yaaro chale jaate aisich class se sikhaana chodhke
unsubscribe dislike
what's the time complexity of this algorithm?
what's the use of making table.....I mean what optimization we are achieving by using dp
It would have been nice if he showed the table at the end. But basically, you start from the bottom and fill the values in the table, then you don’t need to do recursion or anything else, just fill the table and check if the values are already defined (they will if we do it this way)
you the GOAT at this.
a goldmine in youtube
Hello Sir,
Which reference or standard book is preferred for referring algorithms ?
Introduction to algorithm by comren
Sir, I'm a great fan of your videos, You make things really easy for us no matter how complex the problem statement is.
Since the time complexity of this algorithm is not polynomial, AFAIK we can just find the MST (Minimum Spanning Tree) and can add the Cost from last vertex to the source to the final result. This way we can have only O(E log V) complexity? Please correct me if i'm wrong?
You cannot revisit a city in the standard travelling salesman problem.
Amazing content! Thank you !
Incredible Explanation!!
Where i can find the first formul that you used. Can you name your source please?
At -5:41 jo pachak hua , sir kehte ye method to lamba hai ye nahi karna 😭 yaar ek din pehle padhrai aur ye dekhne ko mile , LOL ho gaya 😂
thank you so much for this video.. i was a little confused with the formula..
now i feel dumb for not understanding it before.. 😅
very good explanation sir.....guys watch him if u want to learn
we are already :)
Can somebody give me the previous video on traveling salesman problem he is referring to please?
I got more benefits by learning from this video,it is very nice video👌.
Really satisfying 👌
If there are more vertices present, say 6, then this algorithm becomes almost too huge to handle and cumbersome!!!
it is appearing so but see from computer's perspective ..when we gonna program then its just A matter of a loop for controlling value of k.
Sir can we do exactly in exam like drawing tree and writing remaining vertices???
Depends what type of pattern your university follows .....
@Abdul Bari What will be the time complexity of TSP when done this way?
I am guessing Tabulation will reduce some amount of time but ultimately we are having to consider all possible routes from all possible vertices. Thus O(n!) correct?
In an iterative approach, you can simply solve it as you show in the tree diagram.
As usual AWESOME explanation by Abdul Bari sir. Kudos to you for explaining complex topics in easy and simple terms.
You are a divine god for me ,tomorrow i have exam learning today from ur channel😊✨🔥
Thanks a lot SIR! very helpful :)
Very nice explanation sir super super
But u didn't say the shortest route
What is the vedio no. For previous vedio on this topic as said by sir?
Very good explanation, watched lot of videos :) Thanks a lot for such awesome content.
Plot twist at 11:41
how are we gonna use tabulation method for this one?
Sir can you please solve for s1=abbacdcba and s2=bcdbbcaac
so how and what are we supposed to write it in college university end exam? I mean, where do we start? Do we draw the tree with sample calculations or do we directly do calculations by formula?
Do everything 😂😂
Sir can you explain cutting plane algorithm
What about the return path - imagine u have the case where the return path for a vertex is shorter if we use an indirect route. Would you just run the algorithm backwards?
Superb explanation Sir hatsoff🙏🙌🙌
algo bhi bata dete toh thek rahta..................hehehe
Where is previous video sir? Tmw is my exam can you give the link ?
Saviour ❤️
The Man The Myth🫶🔥
How to find the path?
thank you sir thank you so much 🙏🙏🙏
Sir, why C[2][1] and C[1][2] have different values and similarly for others.
1st city se 2nd city jane pe Ola mili bro
Aur 2nd se 1st jane pe uber
Ab bhai jo mehnga h wo mehnga hai🙅♂🤷♂😛
Just kidding
Actually they are predefined weights of path available for the salesperson.
Suppose it like a two different root from going 1 location to another location.
Assume each vertex as a city/country in the world and there are multiple paths for every city from another city. The available data is just the indication of the salesmen didn't choose the same path.
Agra->Delhi
Delhi->Agra
There are multiple roads available for this
Assume A(agra)(delhi) = 12
and A(delhi)(agra) = 13
Then the path for reaching delhi and returning back from there might be different.
It's just given.
Hope you got it.
Thanks for the tutorial. I would like to just add one note. Maybe it is better to go through tree as Depth-first search not Breadth-first search, because I think recursive algorithm use Depth-first Search.
thank you sir for your easy explanation. the topics which i felt hard in class, you explained it so understandable.
how do you do the table without writing the recursion tree first? we have to write the recursion tree in order to know the later values
Watch few of his prev. videos on DP u will get it. In a table u don't find 'later' ones but 'previous' ones or from where the subprob came. Actually if u find the value of the smallest subproblem then u would be able to find the answer to thelarger subprob and so on.. Inshort u start from small and then form large.
Long but easy question with awesome explanation!💫
Finally got it thanx
legendary thanks a lot!!
Thank you so much sir 👍👍👍🙏🙏🙏
Sir you are awesome.. Thank you
thank you very helpful
Paatal Lok,s Jaideep Ahlawat.👍
Your algorithm lectures is really awesome....!!
Is it a bottom up approach?
Awesome 👍🏻👏🏻
Please, I want an algorithm for this problem. I want to transfer it to program c # :( if you allow
Please help 🥺🥺
U will get it on gfg
We love you sir!!!!
Sir, why don’t you swap this video into the playlist instead of the old one.
Abdul Bari Sir my question is Can we use that old video method for Salesman Problem using dynamic prog?
It will be found in hindi
Thank you so much Sir. You make it really easy to grasp and apply these concepts. I am even doing your course on Udemy. Hope to see more of your content and your channel grow even vast. Best Wishes.
11:37
Thank you very much , May Allah bless you
Thank you for your hard work.
Sir how do we do the table without writing the recursion tree first? we have to write the recursion tree in order to know the later values
simple find 2 to null three to null four to null then get the values similarly 2 to 3 2 to 4 then 3 to 2 and 3 to 4 etc . Or use the formula which he's given in the beggining of this video (g[i,s] one ).
@@manishrai6845 i think if using formula we have to do like a top down memoization dp, i can't think of a effective way for bottom-up dp yet, like how do we know the remaining set if starting from the bottom (from 2-> null etc.)?
Thankyou sir
You are awesome sir , it's very nice and clear explanation. 👏👏👏
Can we apply a dijikistra algo to find the path ...
No, because you've to traverse back to the source vertex.
thank you sir
thanks
Nice
One Doubt! The formula you explained is for minimum spanning tree. I think you should explain the last condition when a set is empty we have to return distance from the last node to the starting node.
Anyways, Its been great to watch your videos. Kudos to you!
He did explain that
excellent explanation sir..... please explain the implementation of algorithm too...!
Thank you sir
🙏🙏🙏
11:07
sir LCS problems I think u forget??
great explanation.
n 2^n?
.
Best teacher for Algorithms
best playlist in algorithm cheers
Bhaiyaa ye series complete kr ne se algorithm ka kaafi part cover ho jye ga
Thanks.
Thank you
Great content and easy to understand.
awesome explanation!!!
superb :-)
Thanks a lot sir :-)