O(n)时间内查询n*n网格的局部最小值

Source: Homework of Theoretical Computer Science


Description:

Suppose now that you're given an n*n grid graph G. Each node v is labeled by a real number x_v; you may assume that all these labels are distinct. A node v is a local minimum if the label x_v is less than the labels x_w for all nodes w that are joined to v.
You can determine the value x_v by probing the node v. Show how to find a local minimum of G using only O(n) probes to the nodes of G.


Solution:

First let's think about this, we start at an arbitrary grid, if one of its adjacent grid has a smaller label, then we move to this grid, and repeat the same process. Finally we will reach a local minimum grid. We call the path we are walking through a "decreasing path". This is a simple way to find a local minimum, but the probes we need is O(n^2) instead of O(n). However, we will see this idea useful later.

Now let's consider a subgraph of the G, suppose it is an rectangular grid graph, and v is the smallest grid of the grids on the border of this rectangle. Suppose v' is the grid adjacent to v and inside the rectangle, if v' is smaller than v, then we can conclude that there exist a local minimum inside the triangle. This is because if we can alwasy a "decreasing path" starting from v', ending at at local minimum. This decreasing path will not go across the border of the rectangle, since v' is smaller than all the grids on the border. So, base on this conclusion, we can divide and conquer the problem.

We may assume that the outer of the G has a very large label. At the first step we probe all the grids of the column at the very middle of G. The column divides the graph G into two n*(n/2) rectangular subgraphs. Suppose the smallest grid of the column is v_1, then we probe the two neighbors of v_1 which are not in the same column of v_1. If the two grids are all larger than v_1, then v_1 is a local minimum. Otherwise, at least one of the two neigbhbors is smaller than v_1, so we can determine which rectangular subgraph definitely contains a local minimum, ccording the conclusion we just worked out. And at the second step, we probe all the grids of the row at the very middle of the rectangular subgraph, this row divides the subgraph into two (n/2)*(n/2) square subgraphs. Suppose the smallest grid of the row is v_2, if v_2>v_1, then the decreasing path starting at v_1 will not go across the row, so we choose the square subgraph which contains v_1. (At this situation v_1 will not locate at the common corner of the two squares, since v_1's neighbor is smaller than it and v_2 is larger than it.) If v_2<v_1, then we probe the two neighbor's of v_2 which are not at the same row of v_2, and use the same way as we due with v_1, to select one square subgraph, or assert v_2 itself is a local minimum. (At this situation v_2 will not locate at the common corner of the two squares, since v_1 is the smallest grid of the column and v_2<v_1.) Now we have shrunk the graph in to a (n/2)*(n/2) subgraph, with 3n/2+4 probes at most. We can apply the same process to the subgraph and finally we will get a local minimum. So the total number of probes will be T(n)=T(n/2)+3n/2+4=3n+4log(n)=O(n).