r*****t 发帖数: 286 | 1 ☆─────────────────────────────────────☆
mechanics (mechanics) 于 (Wed Feb 14 12:25:34 2007) 提到:
一个算法题,
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 |
|