Optimizing Your Search: An Approach to Finding the Highest Point on a 2D Map

Given a 2D map (size W×H) as shown above (the map contains mountains, hills, valleys, rivers, oceans, etc.) and a functiongetElevation(x, y) to get the elevation (height) of a given point on the map (𝑥, 𝑦), where 0 ≤ 𝑥 < W and 0 ≤ 𝑦 < H. How can we design an efficient algorithm to find a high point on the map (the optimal solution is the highest point on the map)?

Evaluation

The efficiency of the algorithm will be measured by the number of times the algorithm calls getElevation(x, y).

Quality Score = Elevation × (1 − Punishment Ratio)

where elevation is the height of the point returned by the algorithm, and:

We will only be using the getElevation(x, y) function to retrieve the elevation of a point.

Algorithm

max_calls = int(0.001*W*H)
counter = 0
first_nodes = {}

We first create the variables max_calls, counter, and a dictionary to store the nodes. The algorithm will stop its search when the counter hits a value of 0.001 * W * H. This limits the number of times the function getElevation() is called to less than 0.1% * W * H.

First Search

for w in range(0, W, int(0.05*W))…