I got the idea that in tsp we need to generate all the permutation of all the places and back to the source using brute force approach and find the minimum weight among those arrangement of places back to the source. So it will take O(n!) time complexity.
But, yah samjh nai aya ki kyun fir O((n-1)!) bhi ho sakta hai, optimization karne ke baad…
Aur, yah optimization kese kiya?
hello @Kinjal
it doesnt matter from where u start answer will remain same.
so what we are doing is instead of considering each node as starting node we are considering any one node as starting node and finding path from there.
so bascially out of n nodes we have fixed one node and then we are left with n-1 nodes . ways of permuting it is n-1 ! factorial.
so this is one small optimisation we are doing here
And why we are fixing one node? Is it because according to the problem there is a source from where salesman starts his journey and after traversing each and every station once, come back to source again and source is also fixed throughout the problem?
even if they dont mention source. we can fix any one node as source and compute answer from it .
we are forming circle/circult thats why source is not creating any difference.
here we can say a is source or d is source or e or g but it will not create any difference because. all are forming same circuit -> a->d->e->g->a
But if source is fixed in the problem then technically we can say that there will be less no of ways to find the solution compare to the problem where source is not given implicitly…right?
bro i already explained why src is not important for this problem.
in both the cases( source given or not ) we can reduce it to n-1 ! factorial in worst case
Yes. You have said that.
Another thing, can we say that O((n-1)!) time complexity is similar to the exponential time complexity(~O(2^n)) of this problem?
no.
the first one is bigger than the later
oh. It means, this brute force approach is worsen than the DP problem time complexity so we should use DP.
yeah correct… … … … …
Okay. Got it. Thanks bhaiya. Appreciate your help.
Bhiaya, yah tourist problem ko tsp ki tarah solve kar sakte hai kya?
nahi , yaha pe har position pe constraint hai direction ki.
2 d dp lagega sayad
Haan bhaiya, 2-D DP hi lagega. Magar problem ka solution ko thoda sa hack kiya gya hai, uske meaning ke hisab se.
In the problem, we need to find out the maximum distance covered from source to destination and then maximum distance covered from destination to source.
Solution:
So from the first hand in the problem, we will likely to find 2 paths from source to destination so that there is no requirement for finding a path from destination to source. This is the small HACK in this problems solution.
PS. Aur isi problem ke dauran mujhe manhattan distance ke bare meh pata chala aur thoda sa confuse bhi ho gya tha like what is the role of manhattan distance concept in this problem to get the solution so I asked in dm.
sorry bro i didnt see that,actually i m not checking dms anymore kyunki sab bacche dm maar rahe hain.
Apne yah wala problem kiya hai kya?
Thik hai…