P4830.第2题-基于最大边际相关性(MMR)的智能示例重排序
题目内容
你正在开发一个智能学习助手，它能够根据用户的问题从知识库中检索相关示例来帮助理解。为了提供既相关又多样化的示例，避免返回大量内容相似的重复结果，你决定采用最大边际相关性(MaximalMarginalRelevance,MMR)算法对候选文档进行重排序。MMR 在保证与查询相关的同时，通过惩罚与已选文档过于相似的候选，提升结果的多样性。
问题描述
给定 N 个候选文档，每个文档有一个唯一的ID 和一个与用户查询的相关性分数（rel[i]，范围 [0,1]）。同时，给出了文档之间的相似度矩阵(sim[i][j])，范围 [0,1]），其中 sim[i][j] 表示文档i 与文档 j的相似度（满足对称性且对角线为1）。你需要实现MMR算法，根据平衡参数λ(0≤λ≤1)和需要返回的数量K，输出按照 MMR得分降序选择的文档ID 列表（按选择顺序）。
MMR算法定义
-
初始化：已选文档集合 S为空集。
-
迭代 K次（0≤K≤N；如果 K=0，输出空列表）：
-
对于每个尚未被选中的文档i，计算其当前边际相关性得分：
MMR(i)=λ⋅rel[i]−(1−λ)⋅maxj∈Ssim[i][j]
- 如果S为空，则max项定义为 0。
-
选择 MMR 得分最高的文档加入S。如果多个文档的得分相等，则选择 ID 较小的那个。
-
将选中文档的 ID 按顺序记录到结果列表中。
输入描述
第一行：一个整数 N(1≤N≤1000)，表示候选文档数量。
接下来 N 行：每行包含一个浮点数 rel 和一个整数 ID，分别表示第i个文档（按输入顺序，索引从0到N−1）的相关性分数和文档 ID。文档 ID 互不相同，范围在 1到 109 之间。
接下来 N 行：每行包含 N 个浮点数，构成相似度矩阵 sim。第i行第 j 列表示文档 i 与文档j的相似度。矩阵保证对称（sim[i][j] = sim[j][i]），对角线 sim[i][i] = 1.00。所有浮点数精确到小数点后2位。
最后一行：一个浮点数λ(0≤λ≤1)和一个整数K(0≤K≤N)，空格分隔。
输出描述
输出一行，包含K 个整数，即被选中文档的 ID，按照选择的顺序排列，ID之间用空格分隔。
如果K=0，输出空行（仅输出换行）。
样例1
输入
3
0.9 101
0.6 102
0.3 103
1.0 0.95 0.2
0.95 1.0 0.1
0.2 0.1 1.0
0.7 2
输出
101 103
说明
初始S为空，MMR得分仅由相关性决定：101(0.63),102(0.42),103(0.21)→选101。
更新后：
- 102:MMR=0.7×0.6−0.3×max(0.95)=0.135
- 103:MMR=0.7×0.3−0.3×max(0.2)=0.15
选 103，输出 [101, 103]。
此时 MMR成功选择了相关性较低但与101 更不相似的 103，体现了多样性。
样例2
输入
3
0.9 101
0.8 102
0.7 103
1.0 0.2 0.3
0.2 1.0 0.9
0.3 0.9 1.0
0.5 2
输出
101 102
说明
初始 S为空，MMR得分仅由相关性决定：101(0.45),102(0.4),103(0.35)→选 101。
更新后：
- 对 102:MMR=0.5×0.8−0.5×max(0.2)=0.4−0.1=0.3
- 对103:MMR=0.5×0.7−0.5×max(0.3)=0.35−0.15=0.2
选 102，输出顺序 [101, 102]
提示
迭代过程中，每次选择后，剩余文档的 MMR得分会因 max 项的变化而重新计算。
