(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210740846.3 (22)申请日 2022.06.27 (71)申请人 华中科技大 学 地址 430000 湖北省武汉市洪山区珞喻路 1037号 (72)发明人 郑渤龙　马勇　万静意　郜勇勇　 (74)专利代理 机构 成都众恒智合专利代理事务 所(普通合伙) 51239 专利代理师 张洪 (51)Int.Cl. G06F 16/22(2019.01) G06F 16/29(2019.01) G06F 16/2455(2019.01) G06N 3/04(2006.01) G06N 3/08(2006.01)G06Q 10/04(2012.01) (54)发明名称 一种基于强化学习的路网最短路径距离计 算方法 (57)摘要 本发明公开了一种基于强化学习的路网最 短路径距离计算方法， 涉及计算机数据管理技术 领域， 包括： 将构建最短路径距离索引的过程转 化成马尔可夫决策过程； 基于马尔可夫决策过 程， 构建并训练基于强化学习的策略模型； 利用 策略模型构建层级结构的2 ‑hop label索引； 对 2‑hop label索引进行优化； 运用优 化后的2‑hop  label索引处理查询， 并返回查询结果。 本发明构 建的索引结构更均衡， 占用空间少， 查询速度更 快， 具有很强的实用性， 智能化高， 模型构建索引 的速度快， 泛化 性能好。 权利要求书2页 说明书9页 附图5页 CN 114996278 A 2022.09.02 CN 114996278 A 1.一种基于强化学习的路网最短路径 距离计算方法， 其特 征在于， 包括以下步骤： S1、 将构建最短路径 距离索引的过程 转化成马尔可 夫决策过程； S2、 基于马尔可 夫决策过程， 构建并训练基于强化学习的策略模型； S3、 利用策略模型构建层级结构的2 ‑hop label索引； S4、 对2‑hop label索引进行优化； S5、 运用优化后的2 ‑hop label索引处 理查询， 并返回查询结果。 2.根据权利要求1所述基于强化学习的路网最短路径距离计算方法， 其特征在于， 所述 S1包括以下步骤： S11、 定义路网和最短路径查询； S12、 定义 树分解； S13、 基于路网、 最短路径查询和树分解， 定义马尔可 夫决策过程。 3.根据权利要求2所述基于强化学习的路网最短路径 距离计算方法， 其特 征在于， 在树分解的每一步， 都需从剩余未移除的节点中筛选出若干候选节点， 将所有候选节 点的特征拼接后构成马尔可 夫决策过程的状态； 用Vk＝{u1,…,uk}表示筛选出的k个候选节点， 一个马尔可夫决策过程的行为 a＝j表示 从Vk中选择节点uj， 1≤j≤k； 采用同步参考法得到马尔可夫决策过程的奖励， 具体为： 在树分解的每一步中， 从候选 节点中选择节点移除的同时， 同步使用启发式的方法选择节点进行移除， 将该两种操作中 得到的结果差值作为奖励； 马尔可夫决策过程的状态转移表示为一个元组(s,a,s ′,r)， 表示在当前状态s下选择 行为a， 进入下一个 状态s′并得到奖励r的过程。 4.根据权利要求3所述基于强化学习的路网最短路径距离计算方法， 其特征在于， 所述 S2包括以下步骤： S21、 基于De ep Q Network构建基于强化学习的策略模型； S22、 基于马尔可 夫决策过程， 对策略模型进行训练。 5.根据权利要求4所述基于强化学习的路网最短路径距离计算方法， 其特征在于， 所述 S22包括以下步骤： S221、 使用随机参数初始化行为网络Q(s,a； Θ)， 目标网络 的参数初始和行 为网络保持一 致， 初始化经验 池M的容量为N； S222、 判断训练周期是否结束， 若结束， 则跳转至步骤S2 29， 否则继续执 行步骤S2 23； S223、 初始化路网， 得到第一个 状态； S224、 判断是否 达到终止状态， 若是， 则跳转至步骤S2 22， 否则继续执 行步骤S2 25； S225、 按照∈ ‑greedy的方式， 选择行为a， 得到状态s ′和奖励r， 存储状态转移元组(s, a,s′,r)到经验 池M； S226、 判断经验 池M是否达到容量N， 若是， 则继续执 行步骤S2 27， 否则跳转至步骤S2 24； S227、 从经验 池M随机采样一个batc h的状态转移元组训练行为网络Q(s,a； Θ)； S228、 进入下一个 状态， 跳转至步骤S2 24； S229、 训练结束， 得到训练好的行为网络Q(s,a； Θ)。权　利　要　求　书 1/2 页 2 CN 114996278 A 26.根据权利要求5所述基于强化学习的路网最短路径距离计算方法， 其特征在于， 所述 S3包括以下步骤： S31、 基于策略模型将路网转 化为树结构； S32、 对于树结构中的每一个树结点， 按照从上到下的方式计算基于层级结构的2 ‑hop  label索引。 7.根据权利要求6所述基于强化学习的路网最短路径距离计算方法， 其特征在于， 所述 S31包括以下步骤： S311、 获取路网； S312、 根据路网构建倒排表； S313、 从倒排表中选出k个候选节点组成集合Vk， 计算各候选节点的特征值， 将各征值进 行拼接组成状态向量； S314、 将状态向量输入到策略模型， 选择奖励值最大的节点作为移除节点， 进行节点移 除操作和节点连接操作， 将移除节点从未删除节点 集合移动到已删除节点 集合； S315、 判断未删除节点集合是否为空集， 若是， 则输出各移除节点连接而成的树结构， 否则跳转至步骤S312。 8.根据权利要求7所述基于强化学习的路网最短路径距离计算方法， 其特征在于， 索引 包括位置数组pos(v)和距离数组dis(v)， 位置数组pos(v)存储的是步骤S31得到的树结构 的结点X(v)中所有节 点在树结构中的深度， 距离数 组dis(v)存储的是树结构的结点X(v)到 所有祖先节点的最短距离 。 9.根据权利要求8所述基于强化学习的路网最短路径距离计算方法， 其特征在于， 所述 S4包括以下步骤： S41、 计算路网的图密度ρ， 公式如下： 其中， |E|为路网的边总数， |V|为路网的节点总数； S42、 选择对路网进行树分解的方法， 具体为： 设定图密度阈值ρθ， 当ρ ≤ρθ时， 使用最小 度的启发式方法对路网进行树分解， 当ρ >ρθ时， 使用强化学习的方法对路网进行树分解； S43、 对路网进行树分解， 在该过程 中， 对于路网中 同一条没有分叉的路径Line， 找到其 端点X(u)， 并将端点X(u)的结点编号u存 储在该Line的位置数组pos(v)中； S44、 对于Line生成的单叉树， 将其 中所有祖先结点的高度， 依次存放于其位置数组pos (v)中； S45、 从树根到叶子， 依次计算Line中所有结点到单支树中祖先结点的最短路径距离， 并存放在距离数组dis(v)中， 此时， 2 ‑hop label索引的优化过程结束。 10.根据权利要求9所述基于强化学习的路网最短路径距离计算方法， 其特征在于， 在 步骤S5中， 查询过程包括非单支树结点之间的查询、 同一单支树结点之间的查询以及不同 单支树结点之间的查询。权　利　要　求　书 2/2 页 3 CN 114996278 A 3