Travelling salesman problem

#1

I am not getting which subproblems are overlapping can you give example?? with photo

#2

Suppose you are in the state 1010 then in this case, if u visit 3 bit before 1st bit then u will store this answer in dp array. If somewhere, u visit 1st bit before 3rd bit then, u can use the answer already stored in dp array.

#3

But it depends on present parent source the arrangement is same but that parent is different can you name a diagram and denote overlapping subproblems??

#4

Please clear it sir …

#5

Pls elabarote ur doubt

#6

Means as we made overlapping subproblems tree diagram of fibonacci make a tree diagram for travelling salesman and show overlapping subproblems… I m not able to make it

#7

Can you clear it?? …

#8

https://docs.google.com/document/d/1Zn9_3KViDJzSbf8dghZAPhbXzRlbTtO7G7xt3JsKo4I/edit

#9

It is not accessible

#10

https://docs.google.com/document/d/1Zn9_3KViDJzSbf8dghZAPhbXzRlbTtO7G7xt3JsKo4I/edit

#11

Is it now accessable??

#12

No it is forwarding request then cancel

#13

https://docs.google.com/document/d/1Zn9_3KViDJzSbf8dghZAPhbXzRlbTtO7G7xt3JsKo4I/edit?usp=sharing

#14

How 001 has overlapping subproblems??

#15

Ohh!! sorry, wo toh ek hi baar hai… the node more than one having same bits have the overlapping subproblem.

#16

Why it is np hard problem ??

#17

it has no quicks olution and the complexity of calculating the best route will increase when you add more destinations to the problem