0day20hour's blog

By 0day20hour, 11 months ago, In English,

Recently I learned some of the basics of the hill climbing search. I have successfully used some of the versions to solve a few problems. For discrete domain, it worked as expected most of the time like solving n queens for board of 300 size.

Now, for continuous domain it doesn't works as expected. Although I have solved a few (e.g. Bike Roads from ASC 23 by climbing over two variable theta = [-PI PI]), it was more like a trail and error than a careful design.

As of my current understanding, to optimize(minimize) a function over multivariate continuous domain, I need to make it discrete. The smaller the cell division, the better(less error). For the problem(doesn't require to read it to understand my argument), 106E - Space Rescuers the function we optimize can return a error of 4*10^12*error_in_data. So, making the cell 10^-20 unit apart should be good enough as the error 10^-6 is allowed, otherwise all the ternary search would have failed too IMO.

But, it would make the grid so big. So, instead we use a bigger cell division say 500 apart, then find the minimal point by moving to the adjacent lower point until we can reach a minima. but, which of course have a great error, but the solution is near. Hence, we now divide the grid into twice smaller cell and improve from it. The process continue until we reach the targeted 10^-20 cell division.

I don't see a flaw in this approach. The function is convex, can be optimized with GSS. No place where we accumulate error. But still I ended up in a point which has a error 10^-2. I submitted the problem so many times that I don't know which one to link. So, instead give me some insight about when the method is to be chosen over GSS. And how to control/estimate the error. If there is a flaw in my understanding point it out.

Here is a implementation found online.
An adapted version which is a modification of the previous one to eliminate the fixed number of iteration (As I thought that might be a issue here).

Any resource suggestion will be good enough. :)

  • Vote: I like it
  • +8
  • Vote: I do not like it

11 months ago, # |
  Vote: I like it -37 Vote: I do not like it

we put '-' to u wahahahahahhahhahhha