#P3892. 第2题-迷你PageRank
-
ID: 3256
Tried: 19
Accepted: 4
Difficulty: 5
所属公司 :
美团
时间 :2025年10月11日-算法岗
-
算法标签>构造列随机矩阵
第2题-迷你PageRank
题解思路
-
建模与符号
-
设节点数为 N,边集为
edges
,每条边 (u,v) 表示从 u→v。 -
构造列随机转移矩阵 S∈RN×N,令第 j 列表示“从节点 j”在一步内跳到各节点的概率分布:
Sij=Pr(j→i)因此每一列和为 1。
-
-
处理悬挂节点(无出边)
- 若节点 j 出度为 0,则按题意把其出边分布设为均匀分布:第 j 列全为 1/N。
-
普通节点的列向量
- 若节点 j 出度为 outdeg(j)>0,则对其每条出边 j→i 计入 Sij+=1/outdeg(j)。 (若输入里有重复边,出度与计数一致,列和仍为 1。)
-
幂迭代(列随机形式)
-
设阻尼系数 d=0.85,随机跳转向量 v=N11,初始 r(0)=v。
-
迭代更新:
r(t+1)=dSr(t)+(1−d)v -
以 L1 范数做收敛判据:∥r(t+1)−r(t)∥1<10−8 时停止;否则最多迭代 1000 次。
-
在固定 d 下,该过程收敛到唯一平稳分布(无需平局处理)。
-
-
输出
- 将最终 r 按节点编号从小到大输出为JSON 数组,并对每个分量执行
round(x, 6)
。
- 将最终 r 按节点编号从小到大输出为JSON 数组,并对每个分量执行
python
import sys
import json
import re
import numpy as np
def _sanitize_json_like(s: str) -> str:
"""把常见“看起来像 JSON 但不合法”的输入修正为合法 JSON。
- 去掉 BOM
- 去掉 // 和 /* */ 注释
- 替换中文引号为 ASCII 引号
- 替换中文标点(:,;)为对应英文;并把 key 后面的分号修正为冒号
- 去掉结尾多余逗号
- 把 `] ; "key"` 这种把分号当分隔符的情况修成逗号
对于本就合法的 JSON,这些替换是“无害”的(基本为 no-op)。
"""
s = s.lstrip("\ufeff").strip()
# 去注释
s = re.sub(r'//.*?(?=\n|$)', '', s) # 行注释 //
s = re.sub(r'/\*.*?\*/', '', s, flags=re.S) # 块注释 /* */
# 统一引号为 ASCII 双引号
s = (s.replace('“', '"').replace('”', '"')
.replace('„', '"').replace('‟', '"').replace('"', '"'))
# 中文标点转英文
s = s.replace(':', ':').replace(',', ',').replace(';', ';')
# 修正:键名后误用了分号(如 "N";2)→ 冒号
s = re.sub(r'("[-\w]+")\s*;\s*', r'\1: ', s)
# 某些人用分号分隔项: ] ; "key" → ], "key"
s = re.sub(r'\]\s*;\s*(")', r'], \1', s)
# 去掉对象/数组末尾多余逗号:{... ,} 或 [... ,]
s = re.sub(r',\s*([}\]])', r'\1', s)
return s
def main():
# 读取整段输入并清洗
raw = sys.stdin.read()
cleaned = _sanitize_json_like(raw)
# 尝试解析
try:
data = json.loads(cleaned)
except json.JSONDecodeError as e:
# 解析仍失败时,给出更直观的提示并打印原始与清洗后的前后文
msg = (
"输入不是合法 JSON(请确保用英文冒号/逗号/引号且无注释)。\n"
f"JSONDecodeError: {e}\n"
"示例合法输入:{\"edges\":[[0,1],[1,0]],\"N\":2}\n"
)
print(msg, file=sys.stderr)
raise
edges = data.get("edges", [])
N = int(data["N"])
# 超参数
d = 0.85
max_iter = 1000
tol = 1e-8
# 构造列随机矩阵 S,S[i, j] = P(j -> i)
S = np.zeros((N, N), dtype=float)
# 统计出度
outdeg = np.zeros(N, dtype=int)
for u, v in edges:
if 0 <= u < N and 0 <= v < N:
outdeg[u] += 1
# 悬挂节点:整列置为 1/N
for j in range(N):
if outdeg[j] == 0:
S[:, j] = 1.0 / N
# 非悬挂节点:按出度均分
for u, v in edges:
if 0 <= u < N and 0 <= v < N and outdeg[u] > 0:
S[v, u] += 1.0 / outdeg[u]
# 幂迭代
r = np.full(N, 1.0 / N, dtype=float) # 初始均匀分布
teleport = (1.0 - d) / N
for _ in range(max_iter):
r_new = d * (S @ r) + teleport
if np.abs(r_new - r).sum() < tol:
r = r_new
break
r = r_new
# 归一,防微小数值误差
ssum = r.sum()
if ssum > 0:
r = r / ssum
# 输出:按要求 round 到 6 位并以 JSON 数组打印
out = [round(float(x), 6) for x in r.tolist()]
print(json.dumps(out, ensure_ascii=False))
if __name__ == "__main__":
main()
题目内容
请手写实现经典 PageRank 算法(列随机、幂迭代形式),用于极小的有向图(节点 ≤6 个)。
1.固定超参数
阻尼系数 d 0.85
随机跳转 (1−d)/N
收敛判据 当两次迭代 L1 差 <1e−8 或迭代次数达 1000 即停止
初始 PageRank 向量为均匀分布 (1/N,...,1/N) 。
2.输出格式
一行:长度为 N 的 JSON 数组,依节点编号顺序给出最终 PageRank 。
3.确定性说明
幂迭代在固定阻尼系数下会收敛到唯一的平稳分布;无需额外平局处理。
输入描述
一行 JSON :
{
"edges”:[[u1,v1],[u2,v2],…],//有向边,节点编号从0开始"
"N”:4 / 节点总数(2≤N≤6)
}
若某节点没有任何出边(悬挂节点),请在构造转移矩阵时对出边(悬挂节点)做均匀分布处理。
输出描述
使用 round(x,6) 保留小数位即可
示例:
[0.486486,0.256757,0.256757]
补充说明
为了确保通过测试用例,仅使用 NumPy 实现
样例1
输入
{"edges":[[0,1],[1,0]],"N";2}
输出
[0.5,0.5]