| [ QuizWit ] in KIDS 글 쓴 이(By): kimsr (Pabochet) 날 짜 (Date): 2003년 7월 23일 수요일 오후 06시 47분 56초 제 목(Title): Re: step 4 submarine. Are you really a professor? You were so happy you have found the search time is bounded by some function on the initial position and velocity, that you forgot those values are not known to the heli. (People here have long understood that such bound exists.) You are on the heli, do you know when the search will finish? You don't know. That's precisely an unbounded-time search. However, the search will surely finish in finite time provided the sub follows the rule of the game. When the problem was first presented here, people got confused because they thought they needed a bound that does not depend on the initial position and velocity of the sub. Let's think about the decision versions of the problem. P1. Given a bound on the initial position and velocity of the sub, decide whether such sub exists or not. P2. (Without such bound as in P1) Decide if a sub exists or not. P1 can be solved within some time bound (which can be computed from the given initial position and velocity BOUNDS). Now, think about how you can solve P2. If a sub exists, the search procedure will finish in FINITE time. If no sub exists, then the search will not finish. Please note that however long you spend serching for the sub, there is no time bound after which you can say, "I have searched enough, so there is no sub." Now go back to the original problem. Is it closer to P1 or P2? If someting similar to P1 was given, nobody would have been confused. The original problem is very similar to P2, just with the guarantee that one and only one sub exists. So the search goes on until you find the sub. You will surely find a sub in FINITE time, but before you find one you have no idea how long the search will take (UNBOUNDED time). Seems you are still confused. |