Page 201 - 《软件学报》2025年第12期

5582 软件学报 2025 年第 36 卷第 12 期

2) 随着跳数的增大, 关系分数的衰减率趋近于 0, 即当路径无限长时, 关系对路径分数的影响趋近于 0.
3) 关系的衰减过程要相对平滑.
根据上述的原则, 本文用 y(i) = e −i 表示路径的衰减率, 其中 i 是路径的跳数. 在此基础上, 对一条长度为 N 的
路径 Path, 本文用公式 (2) 计算其分数:

1 ∑ N
score(Path) = y(n−1)s n (2)
N n=1
其中, s n 表示路径中第 n 个关系在图 7 中对应的分数. 公式 (2) 综合考虑了路径长度和关系分数的层次性, 能够较
为全面地评估一条路径的重要性.
以图 6 中的 4 条路径为例, 按照公式 (2) 的打分函数和图 7 中各个关系的基础分数, 4 条路径的分数可以按照
如下步骤计算.
1
路径 1 (父亲→爷爷→弟弟): (9×e −(1−1) +8×e −(2−1) +7×e −(3−1) ) ≈ 4.297 分.
3
1
路径 2 (父亲→父亲→叔叔): (9×e −(1−1) +9×e −(2−1) +5×e −(3−1) ) ≈ 4.329 分.
3
1
路径 3 (爷爷→叔叔): (8×e −(1−1) +5×e −(2−1) ) ≈ 4.920 分.
2
1
路径 4 (儿子→爷爷→爷爷→弟弟): (9×e −(1−1) +8×e −(2−1) +8×e −(3−1) +7×e −(4−1) ) ≈ 3.344 分.
4
4 条路径分数由高到低分别是 4.920 分 (路径 3)>4.329 分 (路径 2)>4.297 分 (路径 1)>3.344 分 (路径 4), 即系
统认为“张三的爷爷是张大, 张大的叔叔是张郎”能够最精炼地向大模型表述张三和张郎之间的关系, 这也符合大
众对关系亲疏性的选择.
在所提出的路径打分方法的基础上, 本文设计了一种基于大根堆的 Dijkstra 路径排序算法, 以实现在动态变
化的关系路径分数列表中快速查找到能连接目标人物的最优关系路径. 该排序算法的核心步骤为: 若当前长度为
N 的最高分路径无法连通两个人物, 就将该路径与表 2 中的所有关系组合后扩展为 26 条长度为 N+1 的路径, 与
剩余长度为 N 的路径一起参与下一轮排序. 为了在一个动态更新的关系路径分数列表中高效地获取最高分路径,
本文采用大根堆对该分数表进行维护. 第 3.4.1 节具体分析了该算法的时间复杂度和有效性实验. 算法 2 为所提出
路径排序算法的流程.

算法 2. 华谱通路径排序算法.
输入: 待查询的头尾人物姓名 s*和 t*, 所有关系集合 R, 对应的关系分数集合 H, 最大路径长度 max_len;
输出: 最优路径 top_path.

1. new Int hop=1;
2. new List path_list=R; /*初始化路径集合*/
3. new List score_list=H; /*初始化路径分数集合*/
4. new Heap path_heap = Heap(path_list, score_list); /*用一跳路径初始化大根堆*/
5. new List top_path=[None];
6. while True
7. if equal(hop I, 1) and not path_heap.empty() /*先遍历完所有一跳路径*/
8. pass;
9. else
10. if equal(hop I, 1) /*构建所有可能的二跳路径并入堆*/
11. path_list = Group_relation(R, R); /*构建所有可能的二跳路径*/
12. score_list = Calculate_score(H, H); /*计算 path_list 中所有二跳路径的分数*/
13. path_heap.push(path_list, score_list); /*二跳路径入堆*/