Travelling Salesman Problem using Dynamic Programming - Easiest Approach with Code
Вставка
- Опубліковано 26 лис 2017
- Check courses on - online.codingblocks.com [Free Trial Available]
Coding Blocks is pleased to announce courses like C++ and Java, Data Structures and Algorithms, Web and Android Development(Java and Kotlin), Competitive Programming, Coding Interview Preparation and Machine Learning, AI and more.
#CodingBlocks #ProgrammingMadeEasy #LearnCodingOnline
Code - codingblocks.com/ide/#/s/3899
Like our FaceBook Page - / codingblocksindia
Follow us on Instagram - / codingblocks
Follow us on Twitter - / codingblocksin
Source code available on -github.com/coding-blocks
For more interesting tutorials - / @codingblocksindia
![Dijkstra's Algorithm with Code[C++] - Prateek Narang | Coding Blocks](http://i.ytimg.com/vi/NR4fpjuxnPA/mqdefault.jpg)
I watched all the videos of TSP (Abdul bari, William Fiset, Tushar Roy) . This is the best Explaination along with code.
I think those vids were not useless. They helped in installing the idea and some part of the logic in your mind and then finally in this vid you got the Ahha! moment. :D
@@bestsaurabh exactly this happens lot of time yr
Prateeek bhaiya op
bro can you help where is the code, im not geeting it, i have submission today?
I used the Hamiltonian cycle algorithm for my university's delivery service final project. It was the fastest delivery service out of every project submitted.
Bit Manipulation explanation saved lot of hair : ]. Thanks for such a elegant and simple explanation
Amazing tutorial, looked online for hours but this is definitely the best introduction to the tsp problem. :)
Thanks for the appreciation !
Its really brilliant lectures on youtube. Coding blocks always rocks..
You've explained it soo nicely!!! Thank you so much!
You've explained it soo nicely!!! Thank you so much!🙏
Thank you so much for the video! I had been looking for a good DP solution for a while now. And you explained it in great depth. Appreciate the work you have put in :)
I loved it. You explained the bitmask concept soo well. :)
You are great bro understood in one go .
Very intuitive video. Can you give some information on how we can get a path in output?
Do you have the answer now?
Excellent explanation.
very helpful video, thank you!! just one question, how would one modify this code so that it could visit 1000 cities? n would be 1000, and so it would throw a shift counter overflow error.
Great.. loved it!
Amazing explanation.. thank you
Simply superb approach
I just loved it. Thank you very much.
Glad you enjoyed it!
This is one of the best tutorial that I have ever seen when it comes to TSP using DP with the code side by side. Respect _/\_
usually i don't comment much .... but this is seriously beautiful :)
Time complexity is O(n^2 * 2 ^ n) as we are filling each value in the dp table and to compute the optimal value for each cell in dp table we are traversing to all possible next cities which are n.
is this correct?
Nice video..how do we reconstruct the optimal tour?
Can we use bool array for keeping track of visited nodes,if no then why not?
Being an algorithm analyst what do you think, "If TSP problem is solved by using dynamic programming approach, will it provide feasible solution better than greedy approach?
The base case is a bit confusing to me. I think the correct value to return should be dist[pos][origin_pos] instead of dist[pos][0]. The answer is still correct for this example in this video because the origin_pos is queal to 0.
This is one of the best tutorial to explain the TSP solution🎉🎉🎉
bro, we always get a hamiltonian cycle and cycle means no start point, so if you are doing this problem from any node as start point, it doesnt matter, answer will be the same, so if you are using 0 as start node then base case will be returning to 0 as in that case you have confirmed that you have found a cycle, so dp[pos][0]
@@utkarshgangwar2173 nah if you start from the city 2 you will want to end at city 2, but in the code 0 is hardcoded, which will not produce the desired result, so alex is correct
I have a question i hope you could answer to me. How would you print all the visited nodes besides printing the total distance? What could be (and where should be) the line of code? Thanks in advance!
this is great, thanks 👍🏻
Best Explaination on Travelling Salesman Problem.
Thanks
Thank you !
Best Explanation, thanks
After visiting all node why just return the weight of direct edge to source from the destination (mask==all_visiting, return adj[mask][pos] ), there may be some indirect path to the source of minimum weight from the destination. can you explain it a little further?
How to use dynamic programming if there are more cities than number of bits in integer variable?
what if there is no direct path from the last node to the first node . in that case the Dist will be 0.but than here we should some other path from last city to the first city, instead of just returning the Dist[last][first].
Nice explanation but you should have printed path also.
Thank you very much sir!
Like , Share and Subscribe!!
What is the time complexity of this implementation?
Do we ever even hit cache for such small # of cities as in this example? What # of cities would need to hit cache？
Dp array of 2^n by n would cause MLE for even a small n
I got to know about bitmasking here,
used in my lab question of tsp with pickup and delivery
boom
11 sec code got accepted in just 4 sec.
loved it!!
best explanation :)
Great explanation keep it up
Hey! Great video. Quick question though - do we make use of the values in the dp table ie. memoization? I tired the below code (java implementation of the code in the video), seems like we never make use of the dp table values.
Please correct me if I am wrong. Appreciate any help. Thanks for the video!
import java.util.* ;
class Salesman{
int travel(int a[][], int start){
int n = a.length;
int row = 1
sen adamsın alfaların şahısın daşşanı gezdiren yesin
I think the same, the dp optimisation is probably of no use. The recursive code itself is of O(n^2 2^n) time complexity
.
Can you pin in chat the time complexity before and the after the memoization?
what is benefit of storing the results in dp table..??it is never used again in the code..
Simple and best so far
Thanks Ravi.
@@CodingBlocksIndia what is the time complexity ?
Is this the held-karp algo? @CodingBlocks
can anyone explain if there is no route from one distance to another and must take another route, what integer should be in the matrix or in the row
How can we print the path taken ?
Best tutorial for TSP
ha bhai
Is it possible to find also the path and not only the weight ?
Great solution
auuuuuu thannkkyouuuuu for the detailed explanation!!!! looking for hours to understand this topic . Can i ask is anybody know how to print output the path that has the min cost?
Why can't we just use a boolean vector to store visited state of the nodes in the graph instead of using bitmask
👏👏👏 the explanation!!
Glad you liked it!! Keep Learning.
Sir, how do we convert this code to iterative bottom up dp?
good explanation of code
best explanation
Is there a way to keep track of the shortest path cycle also??
visited all(1
can you share some problem based on this concept for practise ?
Thankx
It was very nice, and so beautifully explained.
But you didn't tell the time complexity of the DP solution and also didn't show the overlapping example.
Best tutorial :)
At 16:45, I can't see any overlapping subproblems. Can you give some example where I can see that?
yes.There are none.
Hi, is that GRASP Metaheuristic ?
How do we get the path now?
Here you have taken the origin as always node 0 for all permutations. What will be the solution if that wasn't the case? i.e. we could start from any node and come back to it after travelling all the nodes.
n*(n!) in case of bruteforce and for dp part n^2(2^n) I suppose
Please provide a code for displaying the path thank u
bro can you help where is the code, im not geeting it, i have submission today?
you showed us how to find cost i need to know how do i find the path
The MASK created is of type Integer, so it can store max of 32 bit, or 80 with long long. But what if the number of cities is too large(1000) , in that case MASK won't be able to show, how many cities are visited, we will have a overflow. So what to do???.
Use array but time will also increase as no of cities increase
@@CodingBlocksIndia How to store an array in a DP cache ?
DOnt try to do this is NodeJS, bit manipulation is weird there, it backflows way before the max safe int limit for some reason.
what if edge d to a is not present
Nice video all works fine but tell me how can I get a path to this result?
did you figure it out?
@@rahulduggal4799 did you figure it out?
@@user-gp8fr1nd3w hey man, did you find a solution of how i am getting the path ?
Hi sir,
For the below test case, the given output is 11 as per your code. But the actual answer is 20.
{
{ 0, 1, 2, 0, 8},
{ 1, 0, 3, 5, 6},
{ 2, 3, 0, 4, 0},
{ 0, 5, 4, 0, 7},
{ 8, 6, 0, 7, 0}
}
Hey the problem arises because (If my assumption is correct) you are denoting unreachable nodes weight by 0 so in that case the algo will take the path A->D->C->E->B->A with a total cost of 11.Instead what you could do is take the unreachable nodes weight as infinity(or some big number) then the algo will produce the desired result . Hope this helps :)
How to find the path ?
shouldn't the source be changed everytime?
Can someone tell me what this "10" does in "dist[10][10]"
I dont think DP do any optimization because same sub problem will never occur with same mask value and same node
Sir path kaise print hoga ismein ?
please explain how we can get a path in output.
did you figure it out?
This doesn't work for cities more than 8. Anyone has a solution for that?
check this out ua-cam.com/video/JK31jQ632fw/v-deo.html
bhai 22:25 pr mask& kyu kra hai ??
Are u Rishab sir?
Prateek sir
Can you provide the solution of how to print the shortest path
did you figure it out?
@@user-gp8fr1nd3w yes but i didn't got the answer
@@kshitijgupta7991 What did you exactly figure out then? I was able to print out the cost but I'm having a problem with the path itself. I tried so many things but nothing is working.
@@user-gp8fr1nd3w ya i also tried but didn't get the path.It was always showing 0-0-0-0-0.The path was not coming by any method
Kshitij Gupta where did you put your code and what was it? Maybe I’ll be able to fix it.
woww
How do I do that in Java?
This might help. Implemented the code given in the video in java.
import java.util.* ;
class Salesman{
int travel(int a[][], int start){
int n = a.length;
int row = 1
@@aishwaryasingh246 I think there is an error in your code if starting point becomes 1 then your code will wrong output. Have a look and correct me if I am wrong.
plzz make in python also
why is it 2^n -1 instead of 2^n
@user-pc8ou4uu3t for visited all you are asking?
How to get the path now?
did you figure it out?
hey man, did you find a solution to your answer , cause i need it please!
everything was fine until i hit DP part, i don't see sub problems
doesnt work for 5 cities??
Above code assumes all 5 nodes form a complete graph. It should work then. Or add infinite distance edges if two nodes are not connected.
actually i dont understand can u el elaborate this .we require this code for 5 cities
and how to display path as well
even i wantd to get the path. u got any idea??
I'm sure that the algorithm fails for 30 cities or more.
shivam sharma use long long then
That should be enough for any competitive cases
Sir plz hindi mai bhi bano
dp[mask][pos] will aplway be -1, we are not updating it anywhere.
can any send me code pls pls