m*******s
发帖数: 9 | 1 一个算法题,
Given a chessboard G, each node v is labeled by a real number x(v), how to
find a local minimum of G using only O(n) probes to the nodes of G.
*. A chessboard can be thought of as a graph, whose node set is the set of
all ordered pairs of natural numbers (i, j), where 1 <= i <= n and 1 <= j <=
n; the nodes (i, j) and (k, l) are joined by an edge if and only if |i – k
| + |j – l| = 1
*.a node v of T is a local minimum if the label x(v) is less than the label
x(w) for all nodes w that are j | r********g
发帖数: 1351 | 2 starting from any row a,
1. find the smallest element in row a, suppose its column is b
2. find the smallest element in column b, suppose its row is c, if(c==a)
return G[a][b];else goto 3
3. find the smallest element in row c, suppose its column is d; if(d==b)
return
G[c][b];else goto 4
4. return G[c][d] | m*******s
发帖数: 9 | 3 谢谢.
但有一个问题, 你怎样保证G[C][D}比G[C-1][D] 和G[C+1][D]小呢? | r********g
发帖数: 1351 | 4 you can see G[c][d] is the smallest element among elements in row a,c and
column b,d
【在 m*******s 的大作中提到】
: 谢谢.
: 但有一个问题, 你怎样保证G[C][D}比G[C-1][D] 和G[C+1][D]小呢?
| m*******s
发帖数: 9 | 5 G[c][d]是row a,c and column b里最小的,
但我不明白 G[c][d]怎么是column d 里最小的呢? 谢了. | r********g
发帖数: 1351 | 6 sorry. making a mistake
what about this.
From row a , a+1 ,a+2 , find the smallest element?
【在 m*******s 的大作中提到】
: G[c][d]是row a,c and column b里最小的,
: 但我不明白 G[c][d]怎么是column d 里最小的呢? 谢了.
| m*******s
发帖数: 9 | 7 Thanks a lot for discussion.
你能不能把你"From row a , a+1 ,a+2 , find the smallest element?"的想法说详细
一些, 怎么保证O(n) 复杂度呢? | g*******g
发帖数: 18 | 8 I think it's impossible to find such number in O(n). |
|
