Beemer (dr_tectonic) wrote,

Math-ish blather

So, speaking of algorithms:

Does anyone know if you can prove that hill-climbing will work on a curvilinear grid?

Which is to say, I have a set of points that have the same combinatorial structure as a regular grid, though it may be all stretched out in lat/lon space. I want to find the point nearest to some target by starting at on point in the grid and repeatedly moving to the neighboring point that's closest to the target. This will work as long as there aren't any local minima in the distance field.

The question is, are there simple conditions under which you can be certain there aren't any local minima? Or certain that there are? Because it would be useful to check whether getting the right answer is guaranteed or not. (Of course, it has to be less work to check that condition than it would be to evaluate every candidate point, or there's no point in using a clever algorithm rather than the brute-force approach...)
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded