Computer Science Canada Why can't BiS be used in TS problem ? |
| Author: | seonguvai [ Thu Apr 02, 2015 2:43 am ] |
| Post subject: | Why can't BiS be used in TS problem ? |
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 ? |
|
| Author: | Insectoid [ Thu Apr 02, 2015 11:26 am ] |
| Post subject: | RE:Why can\'t BiS be used in TS problem ? |
We don't full know the goal state. 'Minimal distance' is 'just some characteristic of the state'. We have to know what the minimum distance is in order to fully know the goal state. It's possible that I have no idea what I'm talking about though since I'm not very familiar with the bidirectional search. |
|