一种新的最短路径查询方法 和 一种新的斯坦纳树构造方法
【摘要】 该最短路径查询方法 完全避免了Dijstras需要多次更新节点到起点的最短路径的值；
该斯坦纳树Steiner tree构造方法，充分考虑了权重的组合特性，在权重除以某个数值后，再构造斯坦纳树。
- 一种基于知识图谱最短路径的信息获取方法及装置
查询网址 http://epub.cnipa.gov.cn 查询关键字 2022110583932
该方法的功能与最短路径算法Dijstras一样。但其完全避免了Dijstras需要多次更新节点到起点的最短路径的值，一次性确定节点的最短路径的数值；同时，基于该方法，对A*算法做出了改进。 - 一种斯坦纳树构建方法及装置
查询网址 http://epub.cnipa.gov.cn 查询关键字 2023100980047
该方法考虑到每一条邻接边连接T节点的能力，通过统计方法得到一个整数，把邻接边除以该整数得到更新后的邻接边权重。
该方法是一种全新的斯坦纳树构建方式，其通过（1）把图分割为多个字图（可使用2022110583932中方法）、（2）根据多个联通的子图间路径的联通情况，把重要邻接边的权重除以某个整数、（3）根据更新权重的子图计算子图中节点的重要度、（4）根据重要度选择节点和邻接边构造斯坦纳树。当然，也可在（3）中的子图上，用已有方法构造斯坦纳树。
该方法尤其适用于多目标斯坦纳树的构造。 - 斯坦纳树问题
无向邻接边加权连通图𝐺=(𝑉,𝐸)、边成本𝑐:𝐸→ℚ*和一组𝑇⊆𝑉终端，图的斯坦纳树（Steiner tree）问题是找到包含𝑇中所有节点的树𝑆⊆𝐺，使得c(E(S))最小化，是组合优化中研究最多的问题之一。
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）