Author |
Topic: Best Strategy for Searching in the Plane (Read 3060 times) |
|
Dudidu
Full Member
Posts: 227
|
 |
Re: Best Strategy for Searching in the Plane
« Reply #25 on: Jan 11th, 2004, 12:35am » |
 Quote  Modify
|
on Jan 9th, 2004, 10:01am, 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: use the idea from the line search strategy) - 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)...
|
|
 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 #26 on: Jan 11th, 2004, 1:35am » |
Quote Modify
|
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!
|
|
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 #27 on: Jan 11th, 2004, 2:35am » |
Quote Modify
|
on Jan 11th, 2004, 1:35am, TenaliRaman wrote: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).
|
| « Last Edit: Jan 11th, 2004, 2:39am 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 #28 on: Jan 11th, 2004, 10:27am » |
Quote Modify
|
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
|
| « Last Edit: Jan 11th, 2004, 10:29am 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 #29 on: Jan 14th, 2004, 12:29am » |
Quote Modify
|
on Jan 11th, 2004, 10:27am, TenaliRaman wrote:| the competitive ratio i get is 9.055385138 |
|
That what I was waiting for...
Bravo TenaliRaman !
|
|
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 #30 on: Jan 14th, 2004, 2:05am » |
Quote Modify
|
Thx Dudidu for showing such abundance of patience with me!
|
|
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