Please correct this compilation error

#1

Linkhttps://ide.codingblocks.com/s/344235

#2

hello @KetanPandey

use different name for ur distance array (distance is a function in c++ thats why due to ambiguity ur code is rasing issue).

#3

Ok i got it,Please also explain overlapping subproblems in this question,i do not understandthee are no subproblems overlapping here

#4

consider this->

1->2->3-> { 4, 5, 6 } ->1 … case 1
1->3->2-> {4, 5, 6 } -> 1 … case 2

here if u see subproblem
{4,5,6} -> 1 it is there in both the cases right?

now to compute the cost we will first solve this subproblem ( {4,5,6}->1 ) let say it return x (it will be same in both the case irrespective of what previous city is).
now here comes the role of previous city.
to determine the cost from previous city we need to add cost from previous city to one of the city ( {4,5,6} )
in case one it may be c1 , in case 2 it may be c2
so overall cost from previous city to 1 for case 1 is c1 + x
overall cost from previous city to 1 for case 2 is c2 + x.

so this problem has overlapping subproblem shown above,
it has optimal substructure and hence we can say it is dp problem.

In terms of mask and city->
{4,5,6} can be represented as {111000}
overall state for case 1 -> {111000,3}
overall state for case 2 -> {111000,2}

#5

so in first case ,it will call:tsp(111000,3) and for( second case it will call tsp(111000,2)::::so their are different calls made,although their are overlapping subproblems but the caller is not making the right call.Please explain

#6

and their are no overlapping subproblem till n=5 right???

#7

i tried to explain it in my previous reply .if it is not clear then psl refer this->link

#8

Yes i am goinf through it but one thing i am not getting is for n=4,its written that we are making 6 calls but in actual for n=4,we are making 16 calls as per our recursion table.Please explain

#9

may i know how?
can u please share the screen shot,as per my knowledge it should be (n-1)! which is 3!-> 6

#10

There is no way to send screenshot,no option available here…see from from 1 we call (2,3,4) from 2 we call (3,4) and again(4,3),than from 3 we call (2,4) and (4,2) and from 3 we call (2,3)and (3,2)so in total there are 16 calls from n=4

#11

i mean 1-2-3-4,1-2-4-3,1-3-2-4,1-3-4-2,1-4-2-3,1-4-3-2 these are the calls made and in total they are even more than16 as every tme we are calling function 4 times

#12

and please also tell are their no overlapping subpriblems till n=5?

#13

yeah valid point, calls are greater than six, valid paths are 6 ( n-1!)

#14

yes please tell me whether their are no overlapping problems till n=5 and also can you send me screenshot of ur dp table and circle which calls are overlapping,it would be very helpful.Thankyou