解题思路

MMR 的定义是：

其中：

题目内容

你正在开发一个智能学习助手，它能够根据用户的问题从知识库中检索相关示例来帮助理解。为了提供既相关又多样化的示例，避免返回大量内容相似的重复结果，你决定采用最大边际相关性$(Maximal Marginal Relevance, 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$算法定义

1. 初始化：已选文档集合 $S$为空集。

2. 迭代 $K$次（$0≤K≤N$；如果 $K=0$，输出空列表）：

   • 对于每个尚未被选中的文档$i$，计算其当前边际相关性得分：

     $MMR(i)=λ⋅rel[i]−(1−λ)⋅max_{j∈S}sim[i][j]$

     • 如果$S$为空，则$max$项定义为 $0$。

   • 选择 $MMR$ 得分最高的文档加入$S$。如果多个文档的得分相等，则选择 $ID$ 较小的那个。

   • 将选中文档的 $ID$ 按顺序记录到结果列表中。

输入描述

第一行：一个整数 $N (1≤N≤1000)$，表示候选文档数量。

接下来 $N$ 行：每行包含一个浮点数 $rel$ 和一个整数 $ID$，分别表示第$i$个文档（按输入顺序，索引从$0$到$N−1$）的相关性分数和文档 $ID$。文档 $ID$ 互不相同，范围在 $1$到 $10^9$ 之间。

接下来 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$ 项的变化而重新计算。