7.3 Traveling Salesman Problem - Branch and Bound
Вставка
- Опубліковано 2 жов 2024
- Traveling Salesman Problem - Branch and Bound
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/...
![4.7 [New] Traveling Salesman Problem - Dynamic Programming using Formula](/img/n.gif)
Heyy...
The timing is 2:49 am.
Today is my exam on 10 o'clock.😅
I read some comments that they have their exams on the day they saw this video.
So I just want share this 😁
That I'm also seeing this video on my exam day . ☘️🙃🏝️
Hope that my exam will go well🤞🏻.......
us bro us
updates? how did your exam go?
@@kyusiv9026good. I got 68 out of 100.
Me 15 min before exam 😂😂
It's 5:00 exam at 2:00
I'm helping my daughter do her homework during the Covid-19 lockdown and this is the clearest description of branch and bound that I have seen. I looked at several websites and videos. Thank you for your help!
God bless your soul. Wish every father was like you.
you are an awesome father sir hope she does good in the exams
Hope all fathers are like you
I dont mean to be off topic but does anybody know a trick to get back into an Instagram account??
I somehow lost the account password. I would love any assistance you can offer me
Hope you have done vaccination properly. Stay safe
Sir you are the best...infact my class teacher teaching in the class after watching your video's lecture 😊
Acha bhai fir to aap glt college mein pdte ho..... Aap unki classes chod ke yhi dekh liya kro taki apko pura smjh aaye.....Esse cllg se bdiya to cllg hi na ho bs formalities ho rhi hai or bacho ke paise mein aag lg rhi hai....fees ke liye sbse phle ayenge but in case of quality they are making fools. Atleast yr unko guide to ache se kre but wo bhi nhi hota, cllg bs naam ke liye hai baki Thanks to UA-cam and such teacher's on UA-cam jinke wajah se hme achi directions mil pati hai.....
lol he's a fraud then
@@Libertoso why ??
Because he either doesn't know what he's teaching and is just copying ya boi, or he knows the topic but doesn't know how to teach it
@@Libertoso or maybe he finds abdul baris methods more simpler than the methods he/she learnt , its good the teacher is a learner and still keeps updating methods
Tnk u very much Sir
Your explanation way is very clear & awesome👌
Your channel is bigger than the teacher's channel.
I had my DAA exam today, and I am pretty sure that I am going to top this one. The same question came in my exam today for a whopping 18 marks! Thanks, Abdul Bari Sir for giving us the support the college couldn't give. 😊😊
this is 5 mark question in my university
@@mrAmal45 Mine too lol
@@mrAmal45 lmao same, simple yet lengthy
@@mrAmal45 same
@@mrAmal45 For us it is 10 (the maximum possible among all questions)
sir i couldn't attend any of the daa lectures at my college due to an internship and every lecture you've taken is a treasure!..my orals went amazing thanks to the way you clear fundamentals and I'm feeling more confident for my finals too! Thank you so much sir!
how did you get an internship? can you please guide me too?
Bro how you got internship tell us please
This is so extremely well done. I can’t thank you enough for sharing this in such a well detailed manner. You’re a gifted teacher.
how he has found the cost of node 5 7 8 ?
Sir mere cllg me que. Yhi aaya tha usme diagonal me infinity ki jagah 0 tha to meme infinity put kf diya sahi hoga kyaa
The videos on branch and bound do not seem very useful as you explain the method for solving a problem, but not how to deduce the formula for "pruning" a node. You are teaching us a solution, but not how to come to the solution ourselves by deducing the formula through a logical or mathematical approach.
@@abdul_bari Thank you. That is not to say I do not appreciate all the content you have provided. : ) Keep up the good work! The world needs more people like you.
Hello Sir,
You explained it really well and made an "NP" hard problem just a cake walk.
Abdul Bari, I've been watching a couple of your videos to cram for my final and you're incredibly helpful. I give my most gratuitous thank you.
Sir mere cllg me que. Yhi aaya tha usme diagonal me infinity ki jagah 0 tha to meme infinity put kf diya sahi hoga kyaa
i think the cost from 4 to 3 is wrong it should be 37 correct me if I am wrong
same here thanks man
we have to make 3 to 1 as infinite its correct
I think there is an error for the Node6(2) to Node10(5), it should have a remained cost for 11, the true cost should be C(2,5) + Cost(Node6) + ReducedCost(place(5,1)) = 0 + 28 + 11 = 39
Yes you are right .
No here we also make( 5,1) as infinity bcuz we have to return from 5th node to 1st node..thus the cost at 2,5 is 28..which is crrct said by sir..
After watching full video I've decided I will not answer from this Travelling Salesman question containing set😅
Sir In second sub tree I got cost from 1 to4 to 3 cost(3)=37 but in the video it was 50. Anybody faced the same.
Ss 37
same here
I got 12 + 25 + 0 = 37 :)
Add properly:)
@@fredchan7155 12+25+13 =50
sir allah mubarak!!
I've been referring your videos to most the topic from my syllabus. I could able to cover 4 units out of 5 units which is like "I'm going to get 80/100 for sure in my final exam". Thank you so much sir !
Shouldn't the cost between 1 an 5 be 26 not 31? or I am wrong?!
Yeah Im getting same answer
No ur wrong make 5th col infinity then u have to reduce matrix further so in second row u have to minus 11 from 12 so now eqn will be 4,5 plus cost of parent plus reduction that will be 0+25+11 : 36
Bro we have minimum value 2 they why we will go for 11@@abhishekjagtap778
Can anyone pls tell quickly how it is 50 for (4,3)
How to find who is commenting from India. Look for word 'Sir' in comments. Indians know how to respect their teachers!
Seriously Abdul, this is fantastic quality instruction. My only feedback - the audio is a bit difficult at times. I would consider upgrading your microphone. Do that, and I can see a lot more people consuming your content.
I'm so happy that I just entered the university last year. Imagine entering university without this video, I would be dead inside
Sir,wondered how ur teaching is so perfect and clear...!!😊
Hello, Sir, thx for your video! But I think we should add the cost from 3-1 at last, because the saleman must go back to the first city, so the right answer is 28+3=31, right?
11:16 why 12 was reduced to infinity ..??
The most exhausting Mr. Bari video ever LoL
Watched all your UA-cam videos from scratch. Teaching in that way, which is simple to understand and will also be quickly absorbed by the students is an ART. You have got this brilliant ART sir. I have grasped all these concepts before college via your videos. Thanks a lot for providing knowledge for free. You are a real teacher and i hope that you will continue teaching us more through your videos.
Sir cost of 5 should be 26 right? as 1+25+0 please confirm
Bro is carrying my cs major
He is not Bro yr 😅
Respect
nightmare if comes in exam :(
May Allah bless you with all what you ever expect for,
Alhamdullilah concept is quite clear for me, I'm watching all your videos with full interest. And this subject is now my favourite because of you sir.
Nicely Explained. But I doubt on 2 to 5 there is no edge, so how 1-4-2-5-3-1 can be the path (hamiltonian cycle)?
I thought the same, but look again at the graph - yes, there is a curved edge from 2 to 5, and from 1-5.
sir this problem is wrong ,means method is correct taking values are messed up
If you have habit of reading comment before watching any teaching video like me to know if the video have positive comments or if it worth to watch, then you don't need to come to comment section before watching Abdul sir's video, this sir has the best explanation of DSA topics on the whole UA-cam.. Come here after watching the full video to appreciate his excellent teaching skills..
I got the concept after watching 2 times thanks sir
But I thought this is not to fine solve in University exam because it's take too much time
🐶🦧🐯🐗🐏🐃🐂🏛🌐🌍🗽🏦🛼🚲🚊🌠🌖🕢🌝🎉🎁🎑⚾🏈🎖🧤👕👔👔📠📞📞📓📃🚭🚫🚰🚹🚱⬅
Thank u for such an explanation I have seen your videos before a day of my exam kudos! We are paying hefty fees structure to the college's nothing else.useless teachers like a worm who is eating our hard earned money.
I thank God every single day for your existence. You are a massive help to university students in Indonesia.
Aao srm walo aao!😂
App step 7 cross check kariya q ki solve karne par dusra answer aa rha hai . Or jo answer aap likho ho board par wo QUANTUM se copy ki ho
Maut aa jaye lekin ye question exam me na aaye
What is the point of reducing the matrixes if you are going to add up the length of the path in the end any way?
did you get that now?
if yes, plz help🙏🙏
With all due respect Sir, if the cost from 3 to 1 is very very large and if return path to node 1 not considered (as leaf node), will it still give optimal result?
Sir please check the sound of the video it's not that good! Hope you pay attention towards the quality if the sound!!!
salesman ro dega sir 😥😥😥😥😂😂
very help me on my college
Sir I am from SRM university . ALL YOUR videos have been really helpful and have scored good marks in my algorithm paper . Thank you once again sir
WOW, that was an amazing illustration. Thanks Bari!
sir node 1 to node 5 cost check once
superb explanation great work sir !!! Masha Allah
But sir how it is possible to go on 5th vertex from 2nd directly bcoz if u see graph then in between path of 2 to 5 there is vertex 3 also and there is no direct path to gon on 5th vertex
Sir, Thanks for your very good explanation. Keeping aside the matrix and looking the solution from the graph point of view, we do not have direct connection from 2 to 5 in the graph.
While taking the direct connected vertices of 1 you got 2 3 4 5 which seems to be valid. But when taking the direct connected vertices of 2 why did you take 3 and 5. 5 don't seem to have direct connection to 2. Please explain
Same thing struck my mind
Sir mere cllg me que. Yhi aaya tha usme diagonal me infinity ki jagah 0 tha to meme infinity put kf diya sahi hoga kyaa
Thank u so much sir well explained 😌
Traveling Salesman Problem - Branch and Bound-------the solution contains to travel from node 2 to 5. But in actual graph there is no edge between the nodes 2 and 5. Hence the solution found is incorrect.
Sir, here you didn't take the possibility of visiting vertices multiple times
Example: weights of edges:
5 -> 4 = 16,
5 -> 2 = 4,
2 -> 4 = 4
hence 5 -> 2 -> 4 = 8
from the approach in the video if vertex 2 is already visited, then we won't come across the possibility of 5 -> 2 -> 4
Could you please give an alternative solution where vertices can be visited multiple times
Won't that needlessly increase the cost? Unless negative costs are involved, I don't see the point of revisiting a visited vertex.
The Best and the clear explanation sir...Thank you so much for this video sir...😊😊😊😊
Me in exam hall opening video and writing the answer😂😂
Sir congratulations for 1million subscribers🎉🕺
sir poora paper hi bata dia aapne to. mai bhi tha namu ke sath iska comment neeche hi hogga. zabardast ek dum sir thank you
Thanks sir you helped a lot for my daa exam
very nice explained
he teached dsa to us in our campus
Clg?
Reasoning behind the steps are missing. Video covers all the steps but don't relate it to why we are doing so and how does it translate in a real world.
You saved my semester!
Thanks a ton. 😊
20:45 mistake , right?
have to make 3 rd row 2nd col as infinite ..but he assigned infinity to 3,1
Everything is Best.
But voice is not clear.
How did you find the cost of node 7 and 8 ?
For node 7 ,the cost from 4 to 3 is 12 and cost of node 4 is 25 and there is no reduction,so it should be 37 .
The same answer
Same answer
I don't understand how you calculate the cost of the 7th node 50?
How we get to the node 2 to node 5 in the solution found? There is no direct path to that node. This shouldn't be feasible solution.
Sir I have my exam tomorrow of Design and Analysis of Algorithms , i must say you are such a great help for clearing concepts and doubts,at most of the places i refer to you not books.
At some places you have told methods and explained but algorithm are missing.
Thanks alot.
May God Bless you.
Same here 🙈😂😂
Going to write exam tomorrow 😅
Sir, could you please explain the method on how to proceed if the minimum cost is found in more than one nodes. How to perform the selection?
I think you can choose either of them, considering the case.Of course if the choice is wrong then the bounding function would kill the node and you would have to backtrack and choose the other one!
Would've spent hours on this topic if I read the theory alone 😇thank you sir
Sir, you're great so blessed to study this from you... I would like to tell you that, I seriously don't know anything about this, but... I saw your lecture and I seriously understood.! hats off to you sir.!
Why don't you code anything btw I anyway love your lectures they are quite interesting.
I will opt for another question in my exam 😁
I did not understand cost value fore node 7 and 8 how it came 50 and 56 for node 7 CRS+ RRS=0 the cost of node 4 is 25 and intersection i=4 and j=3 is 12. 25+12+0=37 how it came 50
First of all thank you Sir for this superb , understandable concept😊 sir... i have a problem! Sir , i solved for
cost(7), which is 38 but your is 50. Is i'm wrong or there's a mistake in writing?☺ plz help. @Abdul_Bari
I think it must be 37 not 50
It is 37 sir not 38
Yess it is 38 .. i also face this issue 😅
Matrix for node 7 is wrong C[4,3] is 37 not 50
Hello Dear sir!
i am from afghanistan studying in a private university in india i just wanna say thanks to you,your teaching method is excellent .
Thanks sir
In node 6 the path is from 4->2 you changed 4th row and 2nd column to infinity and 2->1 to infinity. Why you did not changed 2->4 to infinity?? and please reply
After finding the cost of each node, you are checking which one is smallest. But you are also checking all the nodes (for example : node 6 is having cost 28, but while checking, you also include nodes 2,3 and 5 which is not selected in the first time.)
So my doubt is, what if one of those nodes (2,3 or 5) had smaller cost than the newer ones (6,7 and 8)?
Yes I also have a same doubt
If some other node had smaller cost, then yes, you should change and expand that node. Always the smallest one, at least in this implementation... there are other strategies
Tq you very much sir, this way was very easy and understanding also. 🙏🙏🙏🙏🙏🙏
sir ,r u from sri sairam engineering college,chennai TN
No he's from north!
Sir..matrix will be given or else should we take by our own?
Liked the term "Travelling salesperson problem" instead of salesman. Awesome explanation too. Thanks
there are feminists out there :))
Hi
I really enjoyed this class, it is very explanatory.
What is the name of this relaxation? Lagrangian relaxation?
Thank you
For travelling from node 1 to node 2, row 1 and column 2 are set to infinity because after that node 1 cannot travel to any other node and no other node can travel to node 2. Am I thinking right, or there is something more to it?
its really very very best teaching that i need not to revise this topic again by listing once its very clear and very clarity Thankyou sir
smjaya acha jitna smjaya smj aa gya but jo auto fill kia solve aap ny wo ghalat hai
how it posible to move frm 2 to 5...
The curve that passes from 2 to 5 to 1
Thank u now i saw ur approximation algorithms using via traveling salesman
Thank you soo much Abdul Bari,😊
امكن مكنة في الهند كلها🫡
Thank you so much sir, really helpful video. God bless you😊
Thank you sir ..but one problem is that i cant find out last value (1 to 5) value ans 31 can you explian it
It's 30 bro not 31 (25+5+0)
Sir, I looked at the video but my confusion is there is no path between 2-5 so how come answer is 1-4-2-5-3 ???
Bro there is path. Check the graph again. There is a curved drawn between 1 - 5 and 5 - 2 aswell
Abdul sir bht accha kaam krte ho aap😇🙂
isn't at 15:11 the equation C(1,5) + r + ^r = 1 + 25 + 0 = 26?
Yes crct for me also 26
For me also 26
No it should be C(1,5)+r+r^=1+25+5=31
As we are adding up 2 and 3 the minimum of 2 nd and 5th row.
you're the best sir i literally can't survive this semester if it weren't for you thank you so much
Sir mere cllg me que. Yhi aaya tha usme diagonal me infinity ki jagah 0 tha to meme infinity put kf diya sahi hoga kyaa
a goldmine in UA-cam.
It was great, thank you for your explanation🙏🙏