wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Best Strategy for Searching in the Plane
        
(Message started by: Dudidu on Dec 24th, 2003, 3:33am)
Title: Best Strategy for Searching in the Plane
Post by Dudidu on Dec 24th, 2003, 3:33am
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...
Title: Re: Best Strategy for Searching in the Plane
Post by towr on Dec 24th, 2003, 3:52am
1) ::[hide]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.[/hide]::

Are we working in an integer grid? and are all increments/decrements limited to 1?
Title: Re: Best Strategy for Searching in the Plane
Post by Dudidu on Dec 24th, 2003, 4:10am

on 12/24/03 at 03:52:32, 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)
Title: Re: Best Strategy for Searching in the Plane
Post by towr on Dec 24th, 2003, 4:41am

on 12/24/03 at 03:33:31, 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).
Title: Re: Best Strategy for Searching in the Plane
Post by Dudidu on Dec 24th, 2003, 5:08am

on 12/24/03 at 04:41:43, 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 ?)).
Title: Re: Best Strategy for Searching in the Plane
Post by TenaliRaman on Dec 24th, 2003, 5:11am
1>::[hide]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)
[/hide]::

2>::[hide]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.[/hide]::

3>::[hide]Can we exist at two places at the same time? i would use x=|y| then ::)[/hide]::
Title: Re: Best Strategy for Searching in the Plane
Post by Dudidu on Dec 24th, 2003, 6:13am

on 12/24/03 at 05:11:43, TenaliRaman wrote:
1>...
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 ! ;)
Title: Re: Best Strategy for Searching in the Plane
Post by TenaliRaman on Dec 24th, 2003, 7:37am
follower to 1>::[hide]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.[/hide]::

equi-angular spiral aka logarithmic spiral
given by the polar equation r=aeb*theta
Title: Re: Best Strategy for Searching in the Plane
Post by James Fingas on Dec 29th, 2003, 12:17pm
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.
Title: Re: Best Strategy for Searching in the Plane
Post by James Fingas on Dec 29th, 2003, 12:30pm
And for part 3, the best competitive ratio I've found is 5.099. This is pretty close to optimal, if not completely optimal.
Title: Re: Best Strategy for Searching in the Plane
Post by Dudidu on Dec 31st, 2003, 12:41am

on 12/29/03 at 12:17:12, 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...
Title: Re: Best Strategy for Searching in the Plane
Post by James Fingas on Dec 31st, 2003, 4:41am
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...
Title: Re: Best Strategy for Searching in the Plane
Post by Dudidu on Dec 31st, 2003, 5:05am

on 12/31/03 at 04:41:21, 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 !!!
Title: Re: Best Strategy for Searching in the Plane
Post by TenaliRaman on Dec 31st, 2003, 11:45pm
Any hints please!!  ;D
Title: Re: Best Strategy for Searching in the Plane
Post by Dudidu on Dec 31st, 2003, 11:56pm

on 12/31/03 at 23:45:22, TenaliRaman wrote:
Any hints please!!
TenaliRaman happy new year,
Hint:[hide] 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]...)[/hide].
I hope this helps...
Title: Re: Best Strategy for Searching in the Plane
Post by TenaliRaman on Jan 1st, 2004, 3:36am
::[hide]
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?
[/hide]::
Btw,
HAPPY NEW YEAR
Title: Re: Best Strategy for Searching in the Plane
Post by Dudidu on Jan 1st, 2004, 3:55am

on 01/01/04 at 03:36:33, TenaliRaman wrote:
To speed up the process we can <hide>...
Just to be sure - what will the sequence look like ?
Will it be [hide]<1,-1,3,-5,11,...>[/hide] or will it be [hide]<1,-2,4,-8,16,...>[/hide] ?

Quote:
am i on right lines?
Assuming that you chose the right sequence then you are on right lines.

Quote:
if yes then for 3...
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: [hide]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] ?[/hide].
Waiting for your answers...
Title: Re: Best Strategy for Searching in the Plane
Post by TenaliRaman on Jan 1st, 2004, 5:05am

on 01/01/04 at 03:55:07, Dudidu wrote:
Just to be sure - what will the sequence look like ?
Will it be [hidden] or will it be [hidden] ?

::[hide]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?[/hide]::


Quote:
You probably meant (2), and your suggestion is correct !

yeah meant (2)!!   ;D


Quote:
At first, try to calculate the competitve ratio for the hint question - think about the worst case scenario: [hidden].

ok i did that!!!
::[hide]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?[/hide]::
Title: Re: Best Strategy for Searching in the Plane
Post by Dudidu on Jan 1st, 2004, 6:08am

on 01/01/04 at 05:05:56, 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: [hide]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.[/hide]

Now,its up to you to fill the blanks...
Title: Re: Best Strategy for Searching in the Plane
Post by TenaliRaman on Jan 1st, 2004, 7:08am
::[hide]
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]
[/hide]::
Title: Re: Best Strategy for Searching in the Plane
Post by Dudidu on Jan 1st, 2004, 7:27am

on 01/01/04 at 07:08:04, TenaliRaman wrote:
i am getting <hide>
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...
Title: Re: Best Strategy for Searching in the Plane
Post by TenaliRaman on Jan 1st, 2004, 8:19am

on 01/01/04 at 07:27:11, Dudidu wrote:
Just prove to yourself (instead of guessing) why it is so...

::[hide]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[/hide]::


Quote:
How will you do it ?

::[hide]
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?[/hide]::
Title: Re: Best Strategy for Searching in the Plane
Post by Dudidu on Jan 4th, 2004, 12:36am

on 01/01/04 at 08:19:56, 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.
Title: Re: Best Strategy for Searching in the Plane
Post by TenaliRaman on Jan 4th, 2004, 4:58am
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  ;))!!
Title: Re: Best Strategy for Searching in the Plane
Post by TenaliRaman on Jan 9th, 2004, 10:01am
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.  :-[
Title: Re: Best Strategy for Searching in the Plane
Post by Dudidu on Jan 11th, 2004, 12:35am

on 01/09/04 at 10:01:40, TenaliRaman wrote:
i think i need some help out on the 3rd ques too.
O.k.
Your intuition is right, you should go on zig zag lines. Now, you just need to figure what is the best angle for advancing (i.e. lets suppose that you set your traversal y coordinates by some pattern (hint:[hide] use the idea from the line search strategy[/hide]) - what should the corresponding x coordinates be (what is the "best" angle (e.g. ratio) between the horizontal and vertical advance) ?)
Hope this helps (if not just notify me)...
Title: Re: Best Strategy for Searching in the Plane
Post by TenaliRaman on Jan 11th, 2004, 1:35am
A 45 degree turn which would make it an equal search in both axis following the same pattern of movement as in line search.Though i do have problems here in calculating the competitive ratio.HELP!
Title: Re: Best Strategy for Searching in the Plane
Post by Dudidu on Jan 11th, 2004, 2:35am

on 01/11/04 at 01:35:25, TenaliRaman wrote:
HELP!
As I hinted on my previous thread, lets set the y coordinates by the following pattern:
(0,0), (x0, 1) , (x1, -2), ... (xi, 2i)...
Now, we would like to find some slope (i.e. angle) of the zig-zag traversal. Lets call this slope X - this slope intuitively indicates that if we "advance" a unit in the y axis then we advance X units in the x axis (moreover x0 = 0 + X*|1 - 0|, x1 = x0 + X*|-2 - 1| and so on...).
Now there are two case:
1) If  y = min(x,y) then we will traverse at most <Your Answer1> distance (<Your Answer1> is an expression dependent on X).
2) If  x = min(x,y) then we will traverse at most <Your Answer2> distance (<Your Answer2> is an expression dependent on X).
After getting the two equations, look for an X that will minimize the competitve ratio (i.e. X such that <Your Answer1> / y and <Your Answer2> / x are minimized).
If you need more help...

P.S. - 45 degrees isn't optimal (since you'll advance quite fast on the x-axis relatively to your movment on the y-axis, thus if the searched point y's coordinate is small relatively to the x coordinate, you'll relatively travel quite a lot).
Title: Re: Best Strategy for Searching in the Plane
Post by TenaliRaman on Jan 11th, 2004, 10:27am
Let di be the distance traversed to get to (xi, yi).
I get,
di = sqrt(X2+1)(3*2i-2)
xi = 3X(2i-1)
yi = (-1)i*2i

limi->inf d/(xi+[epsilon]) = sqrt(X2+1)/X
limi->inf d/(yi+[epsilon]) = 9*sqrt(X2+1)

Now we have to minimise both of the above so we need to find the intersection points of both the above expression. I got only one intersection point X = 1/9 so that has to be the minimal we are after.

the competitive ratio i get is 9.055385138
Title: Re: Best Strategy for Searching in the Plane
Post by Dudidu on Jan 14th, 2004, 12:29am

on 01/11/04 at 10:27:00, TenaliRaman wrote:
the competitive ratio i get is 9.055385138
That what I was waiting for...
Bravo TenaliRaman !
Title: Re: Best Strategy for Searching in the Plane
Post by TenaliRaman on Jan 14th, 2004, 2:05am
Thx Dudidu for showing such abundance of patience with me!


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board