Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Why can't BiS be used in TS problem ?
Index -> General Discussion
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
seonguvai




PostPosted: 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 ?
Sponsor
Sponsor
Sponsor
sponsor
Insectoid




PostPosted: 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.
Display posts from previous:   
   Index -> General Discussion
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 2 Posts ]
Jump to:   


Style:  
Search: