Why can't BiS be used in TS problem ?

[seonguvai]

Hey guys, I am new to this beautiful forum and WELCOME ME
I have a little problem here that I can't find an answer about it ...

There is an exercise in the AI book I read ... that asks :
Why can Bidirectional Search be used in the N-Puzzle problem but not in the Travelling Salesman Problem ?

So there are two things we need for BiS ...

• The Transition States must be the same when we apply them in the opposite way
• We have to fully know the Final/Goal State, not just some characteristics about it .

But they both meet the requirements , we know for both of them where they'll be (N-Puzzle has to count from 1 - N & Travelling Salesman has to travel from the 'A' City to the 'N' City [with the minimal effort] ) .

So what's the answer here ?

[imatfaal]

Whatever the make up of your number puzzle you know (with absolute clarity) the final state - thus you can work back from it. However you only know features of the solution to the Travelling Salesman - ie the it has no distinct format for its answer. What final state would you input into the BiS for it to work back from in the case of the Travelling Salesman?

[mp][/mp]

 

You also need to be specific in exactly what part of the problems you are looking to solve. ie. In TSP you have two questions one of which is NP-H (what is the shortest route) and the other is NP-C ( is there a shorter route than given route X.)