期刊文献+
共找到9篇文章
< 1 >
每页显示 20 50 100
An Evolutionary Algorithm Coupled to an Outranking Method for the Multicriteria Shortest Paths Problem
1
作者 Frédéric Guidana Gazawa   +1 位作者 Kolyang Irépran Damakoa 《American Journal of Operations Research》 2019年第3期114-128,共15页
In this article, we are interested in solving a combinatorial optimization problem, the shortest path problem in a multi-attribute graph, by the out-ranking methods. A multi-attribute graph has simultaneously qualitat... In this article, we are interested in solving a combinatorial optimization problem, the shortest path problem in a multi-attribute graph, by the out-ranking methods. A multi-attribute graph has simultaneously qualitative and quantitative criteria. This situation gives rise to incomparable paths thus forming the Pareto front. Outranking methods in Multi-criteria Decision Making (MCDM) are the only methods that can take into account this situation (incomparability of actions). After presenting the categories of Multi-criteria Decision Making (MCDM) and the difficulties related to the problems of the shortest paths, we propose an evolutionary algorithm based on the outranking methods to solve the problem of finding “best” paths in a multi-attribute graph with non-additive criteria. Our approach is based on the exploration of induced subgraphs of the outranking graph. Properties have been established to serve as algorithmic basis. Numerical experiments have been carried out and the results presented in this article. 展开更多
关键词 MULTI-CRITERIA DECISION Making EVOLUTIONARY Algorithm shortest path Outranking Method Induced subgraphS
下载PDF
最短路径子图 被引量:3
2
作者 王涛 李伟生 《北方交通大学学报》 CSCD 北大核心 2004年第2期46-49,共4页
在大型网络中两节点之间的最短路径常常不止一条,而且在带限制条件的路径选择等应用上,常常需要找出多条最优或近优的路径.一些经典的单源最短路径算法,如Dijkstra算法,能找出一条从起始点到目的点的最短路径,但并不能求解两点之间的所... 在大型网络中两节点之间的最短路径常常不止一条,而且在带限制条件的路径选择等应用上,常常需要找出多条最优或近优的路径.一些经典的单源最短路径算法,如Dijkstra算法,能找出一条从起始点到目的点的最短路径,但并不能求解两点之间的所有最短路径.本文给出了最短路径子图的概念,用于存储图中两节点之间所有最短路径信息,能够节约存储空间.并给出了最短路径子图构造算法SPSG,其时间复杂度为O(n+e),比同类算法时间复杂度更低.随机网络模型的仿真结果表明:SPSG算法效率更高. 展开更多
关键词 图论 DIJKSTRA算法 最短路径 最短路径子图
下载PDF
基于Neo4j图数据库的配电网供电可靠性计算 被引量:20
3
作者 蒋玮 王铭华 +3 位作者 陈锦铭 刘江东 濮实 许智祺 《电力系统自动化》 EI CSCD 北大核心 2022年第15期104-111,共8页
为提高复杂配电系统供电可靠性计算的效率,提出一种基于Neo4j图数据库的可靠性计算方法。首先,通过图数据库以节点-边形式存储配电网拓扑结构。同时,利用Neo4j图数据库中边具有不同类型的特点来完成复杂配电系统中的馈线分级及负荷分块... 为提高复杂配电系统供电可靠性计算的效率,提出一种基于Neo4j图数据库的可靠性计算方法。首先,通过图数据库以节点-边形式存储配电网拓扑结构。同时,利用Neo4j图数据库中边具有不同类型的特点来完成复杂配电系统中的馈线分级及负荷分块,构建基于图数据库的配电网图模型。其次,结合路径搜索进行配电网图模型的子图划分,基于各子图完成图模型的简化。最后,在最小路可靠性算法基础上,结合Neo4j图数据库高效率的最短路径查询等功能实现了配电系统的供电可靠性分析。通过比林顿测试系统及中国某10 kV实际配电网进行算法验证,验证了所提方法的有效性。 展开更多
关键词 配电网 供电可靠性 图数据库 图模型 子图划分 最短路径
下载PDF
不同耦合方式下相依网络的级联故障评估 被引量:4
4
作者 王曦 张新刚 《电子技术应用》 北大核心 2017年第4期112-116,共5页
为了更全面地评估级联故障对相依网络的影响,采用随机耦合、同配耦合和异配耦合3种不同的连边耦合方式,构建相依边为逻辑依赖的相依网络。提出一种新的负载全局分配的级联故障模型,从最大连通子图、迭代步长、过载节点分布等方面评估级... 为了更全面地评估级联故障对相依网络的影响,采用随机耦合、同配耦合和异配耦合3种不同的连边耦合方式,构建相依边为逻辑依赖的相依网络。提出一种新的负载全局分配的级联故障模型,从最大连通子图、迭代步长、过载节点分布等方面评估级联故障的结果。仿真结果表明:(1)同配相依网络比随机相依网络和异配相依网络有更小的最大连通子图占比,且非最大连通子图占比的差异非常显著;(2)容忍系数增大时,同配相依网络的迭代步长下降最为缓慢,不同耦合方式的相依网络在容忍系数取值0.1处均取到步长峰值;(3)不同耦合方式的相依网络在首次故障迭代时,过载节点倾向于选择初始故障节点的邻居节点的邻居节点,而非故障节点的邻居节点。 展开更多
关键词 相依网络 级联故障 耦合方式 最大连通子图 迭代步长 最短路径长度
下载PDF
时延约束动态组播路由的快速低代价算法
5
作者 孙光明 王硕 +1 位作者 李晓伟 李伟生 《计算机工程》 CAS CSCD 北大核心 2011年第24期71-73,共3页
提出一种时延约束动态组播路由的快速低代价算法。该算法利用改进的时延约束最短路径子图,在加入组播节点时避免非时延约束最短路径的搜索,提高算法的计算效率。通过使新加入节点与树上已有节点共享最短路径,降低整棵组播树的代价。仿... 提出一种时延约束动态组播路由的快速低代价算法。该算法利用改进的时延约束最短路径子图,在加入组播节点时避免非时延约束最短路径的搜索,提高算法的计算效率。通过使新加入节点与树上已有节点共享最短路径,降低整棵组播树的代价。仿真结果表明,该算法计算时间少,组播树总代价低,能使组播树更稳定。 展开更多
关键词 STEINER树 最短路径子图 动态组播路由 时延约束 快速低代价算法
下载PDF
基于最简子图的链接表示及预测 被引量:2
6
作者 尚振浩 程华 房一泉 《计算机工程与科学》 CSCD 北大核心 2019年第2期253-259,共7页
稀疏网络的传统链接预测准确率低,为了捕捉稀疏网络节点间建立链接的可能性,提出基于节点间最短路径的最简子图概念。最简子图反映了节点间的拓扑紧密关系,在采用node2vec节点向量化方法的基础之上,实现了基于最短路径的链接表示,并采... 稀疏网络的传统链接预测准确率低,为了捕捉稀疏网络节点间建立链接的可能性,提出基于节点间最短路径的最简子图概念。最简子图反映了节点间的拓扑紧密关系,在采用node2vec节点向量化方法的基础之上,实现了基于最短路径的链接表示,并采取长短期记忆循环神经网络(LSTM)学习长链接节点序列的特征,最终实现链接的分类。实验结果表明,该方法与已有方法相比,在4种不同数据集上的预测AUC值平均提高了11.6%,AP值平均提高了13.3%。 展开更多
关键词 最短路径 最简子图 链接表示 长短期记忆网络(LSTM) 链接预测
下载PDF
一种面向无向加权图的子图查询方法 被引量:3
7
作者 朱磊 姚燕妮 +4 位作者 高勇 王一川 姬文江 黑新宏 刘征 《西安理工大学学报》 CAS 北大核心 2019年第3期291-299,共9页
随着图结构的大规模应用,图数据库上的查询已经成为图挖掘的研究热点。针对无向加权图,本文提出一种基于最短权值路径和拉普拉斯图谱的子图查询方法PSQuery。首先,PSQuery方法选取可表示数据图的高效特征属性;接着,对提取的特征属性按... 随着图结构的大规模应用,图数据库上的查询已经成为图挖掘的研究热点。针对无向加权图,本文提出一种基于最短权值路径和拉普拉斯图谱的子图查询方法PSQuery。首先,PSQuery方法选取可表示数据图的高效特征属性;接着,对提取的特征属性按照哈希映射进行编码,将特征编码组合生成节点编码和图编码,并且基于图编码构建索引树;最后,通过实现过滤验证框架得到结果集:按照提取特征的嵌套性质进行过滤生成候选集,再根据VF2算法进行验证得到最终的超图集合。实验结果表明,提出的方法加速了无向加权图数据库上的子图查询过程,提高了查询效率。 展开更多
关键词 图挖掘 子图查询 最短权值路径 拉普拉斯图谱
下载PDF
图的Steiner树问题的改进的快速近似算法
8
作者 吕其诚 《黑龙江大学自然科学学报》 CAS 1996年第3期40-42,共3页
设G=(V,E)是一个边皆有非负权的连通无向图,设Z是G的结点集V的子集。一个最小Steiner树是G的连通子图,它含有Z的全部结点,且是有最小边权和的树。一个启发式算法结果分别由EI—Arbi,plesnik和ko... 设G=(V,E)是一个边皆有非负权的连通无向图,设Z是G的结点集V的子集。一个最小Steiner树是G的连通子图,它含有Z的全部结点,且是有最小边权和的树。一个启发式算法结果分别由EI—Arbi,plesnik和kou等人给出,按该算法得到的Steiner树与最小Steiner树最多只差一常数因子2(1—1/z),这里z=|Z|。该算法要计算出z个单源最短路径且算法的时间复杂度为O(z(nlogn+m)),这里n=|V|,m=|E|。现在我们给出了一个改进的算法,其算法性能仍是2(1—1/z),但它只需计算一个单源最短路径且其时间复杂度为O(nlogn+m),较显著地降低了复杂度的阶数。 展开更多
关键词 连通子图 STEINER树 快速近似算法
下载PDF
最短路径搜索算法的几种优化改进 被引量:6
9
作者 顾运筠 《计算机应用与软件》 CSCD 北大核心 2008年第4期246-247,278,共3页
介绍了GIS领域最短路径搜索的一种优化模式。在Dijkstra’s算法的基础上,从三个方面改进了最短路径的计算。首先引入了多级路线图,在读取线路数据时,根据路线的级别有所选择;其次,在计算最短距离时考虑速度的影响;最后,在道路的转弯处,... 介绍了GIS领域最短路径搜索的一种优化模式。在Dijkstra’s算法的基础上,从三个方面改进了最短路径的计算。首先引入了多级路线图,在读取线路数据时,根据路线的级别有所选择;其次,在计算最短距离时考虑速度的影响;最后,在道路的转弯处,引入虚拟路径来估算转弯对汽车行驶的影响。应用以上三种方法的实验,取得了很好的效果。 展开更多
关键词 最短路径 地图-子地图 速度的影响 转弯处
下载PDF
上一页 1 下一页 到第
使用帮助 返回顶部