Author |
Topic: Best Strategy for Searching in the Plane (Read 3062 times) |
|
Dudidu
Full Member
Posts: 227
|
 |
Best Strategy for Searching in the Plane
« on: Dec 24th, 2003, 3:33am » |
 Quote  Modify
|
Suppose you need to find a point (x,y) in the plane. You start at the origin (e.g. (0,0)) and you can move in any continues curve in the plane.
We say that you find the desired point if you reached a point (x, y') for any y' or a point (x',y) for any x' (i.e. you find the point if you reach a point which has the same x-cordinate or the same y-cordinate).
1) Devise a strategy for finding a point s.t. x[ge]0, y[ge]0 (and give its competitive ratio2).
2) Devise a strategy for finding a point s.t. x and y are arbitrary (and give its competitive ratio2).
3) Devise a strategy for finding a point s.t. x[ge]0 and y is arbitrary (and give its competitive ratio2).
Notes:
1 A strategy is evaluated by comparing it to an optimal strategy that is given by an oracle (i.e. in the optimal (oracle) strategy we can assume that the desired point cordinates are known and we only need to travel to the nearest "finding point" - e.g. the cost is always min{|x|,|y|}).
2 A competitive ratio is the cost ratio between the optimal (oracle) strategy and a given strategy's worst case cost.
3 If there are any other clearfication questions, post them...
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Best Strategy for Searching in the Plane
« Reply #1 on: Dec 24th, 2003, 3:52am » |
Quote Modify
|
1) ::my instinct is to just follow the line x=y, and the competitive ratio would be 1/2 I think.. Since in the optimal case you'd only have to travel in either the x or the y direction, so that costs half as much as increasing both.::
Are we working in an integer grid? and are all increments/decrements limited to 1?
|
| « Last Edit: Dec 24th, 2003, 3:54am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best Strategy for Searching in the Plane
« Reply #2 on: Dec 24th, 2003, 4:10am » |
Quote Modify
|
on Dec 24th, 2003, 3:52am, towr wrote:| 1) my instinct is to just follow the line... |
|
Your instinct is correct (well done) !
Quote:| the competitive ratio would be 1/2 I think.. |
|
This is not correct (try to calculate it again - its quite easy...).
To be more formal lets define the competitive ratio as c = [cost(strategy) / cost(OPT)]. Thus, the competitive ratio (c) is always c[ge]1.
Quote:| Are we working in an integer grid? and are all increments/decrements limited to 1? |
|
No and No... (sorry)
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Best Strategy for Searching in the Plane
« Reply #3 on: Dec 24th, 2003, 4:41am » |
Quote Modify
|
on Dec 24th, 2003, 3:33am, Dudidu wrote:| 2 A competitive ratio is the cost ratio between the optimal (oracle) strategy and a given strategy's worst case cost. |
|
This suggest to me cost(opt)/cost(strategy), rather than the reverse..
Anyway, in my calculation I assumed integers. Otherwise, what is the cost at all? You can't talk in terms of operations in a real number case.
There's a heap of troubles it gives.. For instance you can scale the y-axis, without anything essentially changing (P(y) stays the same), but you no longer have the line x=y as optimal (or rather all y = a*x, a > 0 are equivalent).
|
| « Last Edit: Dec 24th, 2003, 4:43am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best Strategy for Searching in the Plane
« Reply #4 on: Dec 24th, 2003, 5:08am » |
Quote Modify
|
on Dec 24th, 2003, 4:41am, towr wrote:
This suggest to me cost(opt)/cost(strategy), rather than the reverse.. |
|
Sorry...
Quote:| Anyway, in my calculation I assumed integers. Otherwise, what is the cost at all? You can't talk in terms of operations in a real number case...you no longer have the line x=y as optimal... |
|
towr,
You should think of this problem as trying to find a strategy that minimize the cost on its "worst case point" - every strategy has some weak point/s (i.e. a point which the strategy has a high cost to find (in relation to the optimal (oracle) cost)), we are looking for a strategy that minimizes the cost on the "worst case point" of this strategy.
Now, x=y is optimal strategy in the first sub-question since its competitive ratio is [sqrt]2 (why ?) and every other strategy has a higher competitive ratio (i.e. for each other strategy we can select a (x,y) point such that the competitive ratio for this point is higher then [sqrt]2 (how to choose such a point ?)).
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Best Strategy for Searching in the Plane
« Reply #5 on: Dec 24th, 2003, 5:11am » |
Quote Modify
|
1>::obviously the optimal would be to traverse X or Y axis provided min(x',y')=x' or y' resp.
However since we don't know before hand the values x' and y' but we do know that x,y>=0 hence we must travel x and y equally so as to hit the min(x',y') as fast as possible.This suggests following the line y=x.
finding the cost is simple,draw a rectangle with origin as one corner and (x',y') as diagonally opposite corner.
WLOG assume that min(x',y') = x'
then cost(strategy) = sqrt(2)*x'
cost(opt) = x'
the competitive ratio is sqrt(2)
::
2>::This suggest me the use of equiangular spiral path.
However i get a exponentially increasing competitive ratio.So i think there might be something better.::
3>::Can we exist at two places at the same time? i would use x=|y| then  ::
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best Strategy for Searching in the Plane
« Reply #6 on: Dec 24th, 2003, 6:13am » |
Quote Modify
|
on Dec 24th, 2003, 5:11am, TenaliRaman wrote:This is correct !!!
A "follower": Can you prove (formally - not just intuitively) that this is the optimal strategy ?
Quote:| 2>...equiangular spiral path...exponentially increasing competitive ratio.So i think there might be something better. |
|
You are right (there is something better). Nevertheless, what do you mean by "equiangular spiral path" ?
Quote:| 3> Can we exist at two places at the same time? |
|
I would say... NO ! 
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Best Strategy for Searching in the Plane
« Reply #7 on: Dec 24th, 2003, 7:37am » |
Quote Modify
|
follower to 1>::i don't know how much formal this is? so if you want more formal than this, do let me know and i'll try to work on it.
now x>=0 and y>=0 so we need not work with curves as we can simply travel in a line (and on a euclidean plane , straight line is the shortest path between two points)
now obviously this line has to be of the form y=mx and we want to hit min(x',y') as fast as possible.
Assume,
min(x',y')=x'
then y=mx'
here we would like to decrease the value of y as much as possible to reach x' faster, hence m should 0<=m<=1 with m=0 being the optimal.
Assume,
min(x',y')=y'
then y'=mx
here we would like to decrease x as much as possible to reach y' faster, hence m should m>=1 with m=infinity being the optimal.
as we see, if m is 0<=m<=1 then we would reach x' faster and if m is m>=1 then we would reach y' faster, hence the trade-off occurs at m=1.::
equi-angular spiral aka logarithmic spiral
given by the polar equation r=aeb*theta
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
Attached is an equi-angular spiral (in black) and two related straight-line search patterns (red and blue). These are related inasmuch as they have the same worst-case point. Searching until we find the point P, we get the following competitive ratios (not exact):
spiral: 15.8
square: 21.5
diamond: 14.3
The spiral is bested by the diamond search pattern, with the square pattern lagging. The diamond pattern can do better because of the peculiar distance measure. There is a search pattern, however, that does even better, however, with a competitive ratio of 7.1 (exact but rounded).
The diagram does not necessarily depict the best value of b, but the general result should hold for any b.
|
| « Last Edit: Dec 29th, 2003, 12:31pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Best Strategy for Searching in the Plane
« Reply #9 on: Dec 29th, 2003, 12:30pm » |
Quote Modify
|
And for part 3, the best competitive ratio I've found is 5.099. This is pretty close to optimal, if not completely optimal.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best Strategy for Searching in the Plane
« Reply #10 on: Dec 31st, 2003, 12:41am » |
Quote Modify
|
on Dec 29th, 2003, 12:17pm, James Fingas wrote:| There is a search pattern, however, that does even better, however, with a competitive ratio of 7.1 (exact but rounded). |
|
Quote:| for part 3, the best competitive ratio I've found is 5.099. |
|
James hi,
I would like to know how you got these bounds (i.e. what is the algorithm/strategy and how you calculated the competitive ratio) since it seems to me that these bounds can't be reached (this is beacuse there is a "less hard" (i.e. simpler) problem that has a bigger lower bound competitive ratio...).
Waiting for your explanation...
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Best Strategy for Searching in the Plane
« Reply #11 on: Dec 31st, 2003, 4:41am » |
Quote Modify
|
Hmm ... redoing my math, I screwed up. The numbers should be 12.73 for question 2, and 9.055 for question 4. Forgot a factor of 2 somewhere in there...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best Strategy for Searching in the Plane
« Reply #12 on: Dec 31st, 2003, 5:05am » |
Quote Modify
|
on Dec 31st, 2003, 4:41am, James Fingas wrote:| Hmm ... redoing my math, I screwed up. The numbers should be 12.73 for question 2, and 9.055 for question 4. Forgot a factor of 2 somewhere in there... |
|
Now, its seems to be right. This, of course, imply that you know the strategy (and everyone know what is the mark they should reach)...
Bravo, James !!!
|
| « Last Edit: Dec 31st, 2003, 5:08am by Dudidu » |
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Best Strategy for Searching in the Plane
« Reply #13 on: Dec 31st, 2003, 11:45pm » |
Quote Modify
|
Any hints please!! 
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best Strategy for Searching in the Plane
« Reply #14 on: Dec 31st, 2003, 11:56pm » |
Quote Modify
|
on Dec 31st, 2003, 11:45pm, TenaliRaman wrote:TenaliRaman happy new year,
Hint: I will give you another problem that can help you to solve the 2nd and 3rd sub-questions: Instead of looking for a point in the plain, devise a strategy to find a point on a line (i.e. you are given a stright line, you are on its origin (e.g. position = 0) and you need to find a point x[in][-[infty],[infty]]...).
I hope this helps...
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Best Strategy for Searching in the Plane
« Reply #15 on: Jan 1st, 2004, 3:36am » |
Quote Modify
|
::
On your suggested hint,i can think of only one thing "moving 1 step left,moving 2 steps right ,moving 3 steps left ,moving 4 steps right and so on" continuing till we hit the point.
To speed up the process we can take the steps in exponential order of say 2 i.e "moving 1 step left,moving 2 steps right,moving 4 steps left,moving 8 steps right,moving 16 steps left and so on" continuing till we hit the point.
am i on right lines??
if yes then for 3 i suppose we have to follow this pattern on the y=x line?
also if i am right, how do i calc the competitive ratio for this one?
::
Btw,
HAPPY NEW YEAR HAPPY NEW YEAR HAPPY NEW YEAR HAPPY NEW YEAR HAPPY NEW YEAR HAPPY NEW YEAR HAPPY NEW YEAR HAPPY NEW YEAR HAPPY NEW YEAR HAPPY NEW YEAR HAPPY NEW YEAR HAPPY NEW YEAR HAPPY NEW YEAR HAPPY NEW YEAR
|
| « Last Edit: Jan 1st, 2004, 3:38am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best Strategy for Searching in the Plane
« Reply #16 on: Jan 1st, 2004, 3:55am » |
Quote Modify
|
on Jan 1st, 2004, 3:36am, TenaliRaman wrote:| To speed up the process we can <hide>... |
|
Just to be sure - what will the sequence look like ?
Will it be <1,-1,3,-5,11,...> or will it be <1,-2,4,-8,16,...> ?
Quote:Assuming that you chose the right sequence then you are on right lines.
Quote:You probably meant (2), and your suggestion is correct !
Quote:| also if i am right, how do i calc the competitive ratio... |
|
At first, try to calculate the competitve ratio for the hint question - think about the worst case scenario: you have reached some point x (lets suppose that it is on the positive side) and the searched point is x + [epsilon] - What is the ratio between the way you traversed and x + [epsilon] ?.
Waiting for your answers...
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Best Strategy for Searching in the Plane
« Reply #17 on: Jan 1st, 2004, 5:05am » |
Quote Modify
|
on Jan 1st, 2004, 3:55am, Dudidu wrote:
Just to be sure - what will the sequence look like ?
Will it be [hidden] or will it be [hidden] ?
|
|
::as i had described it was <1,-1,3,-5,..>. is this correct? If i am right, i was wondering whether it is actually optimal and why?::
Quote:
You probably meant (2), and your suggestion is correct ! |
|
yeah meant (2)!!
Quote:
At first, try to calculate the competitve ratio for the hint question - think about the worst case scenario: [hidden].
|
|
ok i did that!!!
::if x is positive then the we will be reaching it after odd number of steps,
x = (4n+2)/6 .. n=2k-1 ,k=1,2,...
we would have traversed 2n+1-1
we see that their ratio is dependent on n?::
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best Strategy for Searching in the Plane
« Reply #18 on: Jan 1st, 2004, 6:08am » |
Quote Modify
|
on Jan 1st, 2004, 5:05am, TenaliRaman wrote:| as i had described it was <hide>. is this correct ?... |
|
Try the other one...
Quote:| if x is positive then the we will be reaching it after odd number of steps...we see that their ratio is dependent on n? |
|
This ain't correct - let me help you some more: lets assume that the sequence is <1,-2,4,8,...>. The worst case scenario1 occurs when we reach some point x (lets suppose that it is on the positive side) and the searched point is x + [epsilon]. Lets assume that x = 2n, so till now we have traveled 20 + (20 + 21) + (21 + 22) + ... + (2n-1 + 2n). To find the point we need to travel another <Your Answer1> units, summing up to a total of <Your Answer2>. Thus, gaining a competitive ratio of <Your Answer2> / (x + [epsilon]) = <Your Answer2> / (2n + [epsilon]).
1This can be proved formally but for the meanwhile lets use our instincts.
Now,its up to you to fill the blanks...
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Best Strategy for Searching in the Plane
« Reply #19 on: Jan 1st, 2004, 7:08am » |
Quote Modify
|
::
i am getting (9*2n+[epsilon])/(2n+[epsilon]).Am i supposed to take limits n->inf, in which case i would get 9 as the competitive ratio.
and i guess the ratio for (2) would be simple 9/cos(45).
[edit]
btw for (3) i think have to perform the same search pattern along x=y and x=-y .. am i right?
[/edit]
::
|
| « Last Edit: Jan 1st, 2004, 7:16am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best Strategy for Searching in the Plane
« Reply #20 on: Jan 1st, 2004, 7:27am » |
Quote Modify
|
on Jan 1st, 2004, 7:08am, TenaliRaman wrote:Thats the point. Well done !
Quote:| and i guess the ratio for (2) would be <hide> |
|
It's correct (see also James's answer).
Just prove to yourself (instead of guessing) why it is so...
Quote:| for (3) i think have to perform the same search pattern along x=y and x=-y .. am i right? |
|
How will you do it ?
lets suppose that you have traveled from (0,0) to (1,1) will you travel next to (-2,-2) or to (2,2) ?
can you improve it even farther (maybe ) ?
Think of it a little more...
|
| « Last Edit: Jan 1st, 2004, 7:28am by Dudidu » |
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Best Strategy for Searching in the Plane
« Reply #21 on: Jan 1st, 2004, 8:19am » |
Quote Modify
|
on Jan 1st, 2004, 7:27am, Dudidu wrote:
Just prove to yourself (instead of guessing) why it is so...
|
|
::That was pretty simple.Competitive ratio of 9 suggests that if i want to reach x i need to travel 9x distance.
However we want to search X and Y axis equally so we are traversing through the line x=y which is rotating the searching axis by 45 degrees.This implies now that to find the same x i have to travel 9x/cos45 which directly gives the competitive ratio as 9/cos45::
Quote:
::
i was thinking like going from (0,0) to (1,1) then going to (1,-2) and from there to (2,-2).
but travelling from (0,0) to (1,1) and then directly to (2,-2) would be faster right?::
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Best Strategy for Searching in the Plane
« Reply #22 on: Jan 4th, 2004, 12:36am » |
Quote Modify
|
on Jan 1st, 2004, 8:19am, TenaliRaman wrote:| ...travelling from (0,0) to (1,1) and then directly to (2,-2) would be faster right? |
|
Of course, triangle inequality... but I'm not suggesting that this is the solution.
p.s. - sorry that it took me so long to response.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Best Strategy for Searching in the Plane
« Reply #23 on: Jan 4th, 2004, 4:58am » |
Quote Modify
|
doh!!
i will think over it again!!
Will post as soon as i have something or as soon as i don't have something??(so P(i will post)=1 )!!
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Best Strategy for Searching in the Plane
« Reply #24 on: Jan 9th, 2004, 10:01am » |
Quote Modify
|
i think i need some help out on the 3rd ques too. 
I have thought hard on it and i somehow end up on the zig zag lines as the best possible line.I must be missing something really obvious. 
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print