返回题库

无向图搜索

Undirected Graph Search

专题
Statistics / 统计
难度
L4

题目详情

给定一个含 N≥2N \geq 2 个节点的完全无向图。你先均匀随机选择一个节点前往，之后每一步都从图中任意一个节点（包括你当前所在的节点）中均匀随机选择一个前往。求在访问完所有节点之前所执行步数的期望值；当 N=100N=100 时，将答案四舍五入到最近的整数。

You are given a complete undirected graph with N≥2N \geq 2 nodes. You first select a uniformly random node to go to, and then each step after, you select to move to any of the nodes (including the one you are presently on) in the graph uniformly at random. Find the expected number of turns that are performed until you visit all of the nodes with N=100N=100 and round to the nearest integer.

解析

这题等价于 coupon collector（集齐优惠券）问题。

因为每一步都会在 100 个节点中等概率选一个节点前往（包括原地不动），所以当前已经访问过 kk 个不同节点时，下一步访问到“新节点”的概率是 100−k100.\frac{100-k}{100}.

因此，从已经访问了 kk 个不同节点推进到访问 k+1k+1 个不同节点，所需步数的期望是一个几何分布的期望： 100100−k.\frac{100}{100-k}.

把这些阶段加起来，并把第一次落到某个节点也算作一次移动，可得总期望步数 100(1+12+13+⋯+1100)=100H100.100\left(1+\frac12+\frac13+\cdots+\frac1{100}\right)=100H_{100}.

数值上 H100≈5.1873775,H_{100}\approx 5.1873775, 所以 100H100≈518.73775.100H_{100}\approx 518.73775.

四舍五入后得到 519.\boxed{519}.

Original Explanation

We need to solve for the expected number of steps to visit all nodes in a complete graph with N=100 nodes using a random walk.

This is a classic problem known as the "coupon collector problem" or "cover time" for random walks on graphs.

Here's the set up the problem:

  • We have a complete graph with N=100 nodes
  • At each step, we move to any node (including current) with probability 1/N
  • We want the expected time to visit all nodes
  • For a complete graph, this is equivalent to the coupon collector problem. At any time, if we've visited k distinct nodes, the probability of visiting a new node on the next step is (N-k)/N.

Let TkT_k be the expected time to go from having visited kk nodes to visiting k+1k+1 nodes.

Tk=N/(N−k)T_k = N/(N-k)

This is because we need on average N/(N−k)N/(N-k) trials to get a success with probability (N−k)/N(N-k)/N.

The total expected time to visit all N nodes starting from having visited 1 node is:

  • E[T]=T1+T2+...+TN−1E[T] = T_1 + T_2 + ... + T_{N-1}
  • E[T]=N/N+N/(N−1)+N/(N−2)+...+N/1E[T] = N/N + N/(N-1) + N/(N-2) + ... + N/1
  • E[T]=N×(1/N+1/(N−1)+1/(N−2)+...+1/1)E[T] = N × (1/N + 1/(N-1) + 1/(N-2) + ... + 1/1)
  • E[T]=N×HNE[T] = N × H_N

where HNH_N is the N-th harmonic number.

For N=100: H100=1+1/2+1/3+...+1/100≈5.1873H_{100} = 1 + 1/2 + 1/3 + ... + 1/100 \approx 5.1873

Therefore

E[T]=100∗5.1873=518.74≈519E[T] = 100 * 5.1873 = 518.74 \approx \boxed{519}