图类算法可重用设计及其实现_轩瑞.pdf
《图类算法可重用设计及其实现_轩瑞.pdf》由会员分享,可在线阅读,更多相关《图类算法可重用设计及其实现_轩瑞.pdf(9页珍藏版)》请在咨信网上搜索。
1、收稿日期:2022-10-25基金项目:国家自然科学基金(62062039)和江西省自然科学基金(20212BAB202017)资助项目通信作者:石海鹤(1979),女,江西乐平人,教授,博士,主要从事形式化方法、软件工程和生物信息学的研究 E-mail:haiheshi jxnu edu cn轩瑞,陈磊,石海鹤 图类算法可重用设计及其实现 J 江西师范大学学报(自然科学版),2023,47(1):52-60XUAN ui,CHEN Lei,SHI Haihe The reusable design and implementation of graph algorithms family J
2、 Journal of Jiangxi NormalUniversity(Natural Science),2023,47(1):52-60文章编号:1000-5862(2023)01-0052-09图类算法可重用设计及其实现轩瑞,陈磊,石海鹤*(江西师范大学计算机信息工程学院,江西 南昌330022)摘要:为了提高图算法生成效率和可靠性,该文提出一种将领域特征模型与构件组装技术相结合的可重用的图类算法开发方法 首先,通过对一族图算法的深入分析,揭示出图类算法领域的共性特征和可变特征,建立领域特征模型;然后,分析特征之间的交互过程,设计图类算法的可重用构件,并对构件依赖关系做出描述;最后,借助
3、高可靠平台对算法构件进行开发,建立高可靠可重用构件库,进一步由构件组装出多种图算法,提高了图算法的开发效率和可靠性 实验表明开发出的图算法可重用构件库具有一定的实用性关键词:图算法生成;特征模型;可重用设计;构件中图分类号:TP 311文献标志码:ADOI:10 16357/j cnki issn1000-5862 2023 01 070引言图算法是利用节点之间的关系来推断复杂系统的结构和变化,是图分析的工具之一,也是分析相互关联数据的有效的方法之一1 图算法在社交网络、城市交通网络、生物信息网络等网络领域中扮演着重要的角色2-4,除此之外图算法在防止欺诈、优化呼叫路由以及预测流感的传播等领域
4、中还存在巨大的应用潜力 2010 年,美国航空旅行系统发生了 2起涉及多个拥挤机场的严重事件,网络科学家使用图算法确认事件起因,并使用这些信息提出纠正建议5;2018 年,斗鱼采用图算法来解决流量作弊问题6 图算法还可以用来帮助理解相互关联的数据,从蛋白质相互作用到社交网络、从通信网络到电网、从零售体验到火星任务规划等都有图算法的应用实例1 面对图算法在各个领域中的广泛应用,众多学者从不同角度对其展开了研究7-11,这些研究大多致力于特定问题求解及具体步骤优化,较少面向整个问题领域,且无法保证算法开发的可靠性 当在一个领域中的信息量超过一定限度时,就会变得难以管理和使用12 本文提出了一种将特
5、征模型与构件组装技术相结合的可重用的图类算法开发方法 在面向重用的开发阶段,探索了图类算法领域的共性和可变性,建立了领域特征模型,并进一步基于高可靠平台设计和实现了图类算法的可重用构件库;在利用重用的开发阶段,通过若干构件组装生成了 Dijkstra 算法、Prim 算法和拓扑排序算法等,提高了图类算法的开发效率和可靠性1相关研究工作许多学者对图算法问题进行了研究,文献 10利用 OpenCL 在高性能计算领域中的优势来进行加速计算大脑皮层曲率,实现了 Dijkstra 算法的并行编程 文献 11通过量化权重指标的选择,使用Prim 算法求解公路网布局重要度最大树 文献 13在已有 BFS 算
6、法优化的基础上提出了 2 种面向高通量计算机的优化算法以提高访存效率 文献 14提出了一种新的优化算法来寻找不同的拓扑排序针对在道路网中在线最短路径查询所面临的计算成本高、查询速度慢等问题,文献 15提出了一种新第 47 卷 第 1 期江西师范大学学报(自然科学版)Vol 47 No 12023 年 1 月Journal of Jiangxi Normal University(Natural Science)Jan 2023的基于缓存的时变最短路径查询算法 以上研究主要关注算法层面的应用和优化,较少面向整个问题域在通用图算法框架研究方面,文献 16 建立了一个基于优势关系的广度优先搜索理论,
7、并展示了如何使用该理论推导单源最短路径问题和最小生成树问题 文献 17 采用程序转换步骤系统地推导图算法,从而揭示了算法的具体设计步骤及其基本原理,为从简单组件到创建算法提供了可靠的方法 文献 18 研究了一个适合处理图算法的形式化语言代数,推导出了宽度优先遍历的一般方法,并表明该方法也可以应用于可达性和最短路径问题 文献 19 提出了一种求解有向图路径问题的通用方法:首先在图中构造一个表示路径集的正则表达式集合,然后根据正则表达式到给定问题域的自然映射给出了寻找最短路径所需的映射图;该方法为求解任意路径问题提供了一种通用算法 然而上述研究均没有提供相应的平台来验证所提出理论的可行性,且图算法
8、的推导过程完全依赖于人工,推导效率较低 文献 20 提出了一个用于最优路径查询的通用框架:首先使用特定领域的语言来描述最佳路径查询问题,再由最优路径查询系统将其转换为C+程序,进而查找出最优路径;不过该框架仅研究了最优路径查询问题 文献 21 开发了一个用于解决一般路径问题的通用算法程序,并实例化生成了一些典型的路径算法,如 Floyd 最短路径算法、最大容量路算法2基础知识2 1PA 方法薛锦云提出的 PA21-26 方法是一种统一的算法设计方法,涵盖了多种已知的算法设计技术,如动态规划法、贪心法、分治法、穷举法等,支持算法程序开发的全过程 PA 方法由自定义算法设计语言adl(recurr
9、ence-based algorithm design language)、抽象程序设计语言 Apla(abstract programming lan-guage)和算法程序开发方法及程序生成系统(可生成 Java、C+等可执行程序)组成adl 是基于递推关系的算法建模语言,是为描述算法规范、推导算法的转换规则和算法本身而设计的 它提供了标准数据类型、自定义简单类型、预定义 ADT 和自定义 ADT 机制 用户可以像使用标准数据类型一样使用预定义的 ADT,其常常用作adlApla 转换器的前端语言Apla 是基于功能抽象、数据抽象的抽象编程语言,其主要目的是描述抽象程序 在 Apla 中的
10、关键字、标识符、标准过程、标准函数、符号和类型系统与adl 的表达方式完全一致 不同之处在于:Apla 增加了程序结构、语句过程和函数方面的内容,并且拥有敏捷的泛型机制,支持类型参数化、过程参数化、函数参数化 这些优点使得 Apla 非常适合于形式化实现构件库使用 PA 方法开发高可靠的执行程序有 2 种途径(见图 1)图 1PA 架构2 2特征模型特征模型描述了在领域内实例的通用特征和可变特征以及它们之间的约束与依赖关系,是在特征建模过程中构建的,一般由描述特征层次关系的特征图和相关的文本描述组成 特征建模是领域工程方法的核心活动,它清晰地刻画了特征模型在构建过程中所需的各类特征,是识别和捕
11、捉可变性的关键技术 文献 27 提出了一种面向特征的领域建模方法 FODM,它将在领域中的服务(service)、功能(function)、行为特点(behavior characteristic)作为重点分析对象,本文使用此方法进行建模工作特征建模阶段包含了特征选取、特征建立、特征关系描述以及特征模型建立等过程,在该阶段需要对被研究领域进行分析,充分了解其功能性特征,并找出特征之间的约束和依赖关系以及优先级等附加信息,进而获得该领域的主次特征,建立一种具有更高抽象层次的特征模型或者构件框架特征建模阶段主要包含 4 种特征28:强制特征(mandatory)、可变特征(optional)、XO
12、 特征、O 特征 图 2(a)表示强制特征,被末端为实心圆的边所指向,强制特征表示在领域中的所有实例都必须包含的特征;图 2(b)表示可变特征,被末端为空心圆的边所指向,可变特征表示领域中实例的一个可选35第 1 期轩瑞,等:图类算法可重用设计及其实现特征;图 2(c)表示 XO 特征,被一组用空心弧连接的边所指向,XO 特征表示在领域中的实例有且只能选择一个特征;图 2(d)表示 O 特征,被一组用实心弧连接的边所指向,O 特征表示在领域中的实例至少包含了在该特征中的一个特征(a)(b)(c)(d)图 2特征图上述 4 种特征是特征建模中的主要属性,也是特征模型的重要组成部分,代表了在领域中
13、的通用和可变属性,同时它们之间的约束以及依赖关系则需通过特征内在的层次结构关系、领域业务逻辑设计的约束关系以及在运行时的依赖关系来表示3面向图领域的可重用构件设计图是由顶点集合与边(顶点之间的关系)集合组成的数据结构,是刻画离散结构的一种有力工具在运筹规划、网络研究和计算机程序流程分析中都存在图的实际应用 在生活中通常使用图来表达用文字难以描述的信息,如城市交通图、线路图、网络图等本部分通过提取不同图算法之间的共性和特性,将所有图的遍历问题概括并统一为最佳优先遍历问题,设计出了可重用的算法构件,并使用PA 方法和高可靠 PA 平台对可重用构件进行形式化开发3 1一族图算法问题分析图算法是个庞大
14、的家族,其中大部分成员的主体框架都可归结于图的遍历 图的遍历算法作为图算法的基础,应用十分广泛,一些比较经典的图算法都是在遍历算法的基础上加以改进的,如 Prim 算法、Dijkstra 算法以及拓扑排序算法等,将这类图算法的遍历过程定义为如下形式给定一个图 G,起点为 v1,找到一组满足性质 P的顶点集合 X,即Specification X=X v1 P SG out(v1)其中称运算符 为插入运算符,其定义为 a0,a1,an a=a0,a1,an,a;S 被定义为栈,表示等待被访问的顶点集;G out(v)表示顶点 v 射出边的终点集;属性 P 表示顶点的某种选取方式,它被定义为P S
15、=,S=,P S=Sv P S v+1t Gout(S,v),S ,S v 表示在栈 S 中前 v 个顶点集,t 表示栈尾根据上述定义,使用 P 来描述一些图算法的问题属性,如使用 PBFS、PPrim、PTopological sorting分别表示BFS、Prim 和拓扑排序问题的属性,它们的描述如下:PBFS为优先访问在图中距离起始顶点最近的点;PPrim为优先选取与当前顶点集最近的一个顶点;PTopological sorting为优先选取在图中入度为 0 的顶点根据属性描述可以发现当上述 3 种图算法在图中遍历遇到满足问题属性的新顶点时,其做法有着某种共性特征,这一共性特征可被总结为
16、最佳优先遍历(best first traversal,BFT)框架 为了更直观地描述该特征,将顶点的优先级定义为该类问题的新顶点选取指标,根据每个问题的属性设计出相应的优先级更新方法(priority update method,PUM),随着算法的推进,PUM 不断调整各个顶点的优先级值 BFT 框架的具体搜索过程如下:首先,从某个节点 v0开始搜索,处理完该节点本身的信息;然后,算法通过与该点相连接的所有边,遍历到它的所有邻接点,同时使用相应的 PUM 更新这些顶点的优先级值,在其后的每一步迭代中都选取当前优先级最高的顶点,并将该点与其父节点的联边加入遍历树中;最后,重复上述过程,直至所
17、有顶点都被访问图 3 为该框架的算法流程图,其中 priority 函数用来存储顶点优先级值,visited 为布尔型数组,用来保存顶点状态 这里顶点的 priority 值越大说明其优先级越低,初始阶段将所有的顶点的 priority 值统一设置为最大图 3BFT 框架流程图45江西师范大学学报(自然科学版)2023 年下面以求解单源最短路径的 Dijkstra 算法为例,深入介绍这一框架的具体应用设 G为一个有n个顶点的无向非负权图,V表示在图 G 中所有顶点集合,E 为在图 G 中所有边的集合,则G=(V,E),令V=v1,v2,vn,(v1,v2)表示顶点 v1和顶点 v2之间的边 G
18、 的最短路径树(shortest path tree,SPT)表示为 T=(U;TE),其中U 为T的顶点集,TE为T的边集,U和TE的初始值为空,uV U Dijkstra算法的基本思想是逐步求解,即每次从顶点集V中选出一个距离起点v0最近的顶点 vt加入 U 中,并将其与父节点之间的边加入 TE中,依次重复,直到所有的顶点都并入集合 U 中,由此得到最短路径树 T在这个问题中,将 vi(1 i n)与源点 s 之间的距离作为各顶点的优先级数;每次将一个新的顶点 vi加入 U 后,更新在集合 V U 之中且与 U 之间有关联的顶点的优先级数,即在每次扩充U时,可将集合 V U 中的各个顶点
19、u 到 vi的距离看作 u 的优先级数(若 u 到 vi之间没有联边,则优先级设为+);从而每条最短路径所对应的 vi都会因拥有最高优先级而被选中 图4 给出了Dijkstra 算法的完整执行过程图 4Dijkstra 算法示例图4(a)为一个含有9 个顶点和13 条边的无向图 先任选一个顶点 A 作为源点(见图 4(b),T=(A;);再从 A 到其顶点的边中选择一条权值最小的边(A,B)(见图 4(c),扩充 T,T=(A,B;(A,B),此时能够到达 B 的点有 D、B、C 和 F;然后从 A 到这 4 个点的边中选取一条权值最小的边(A,D)(见如图 4(d),T=(A,B,D;(A,
20、B),(A,D);如此反复,直至最后如图4(j)所示,得到最短路径树 T:T=(A,B,D,E,C,F,H,G,I;(A,B),(A,D),(D,E),(B,C),(B,F),(D,H),(D,G),(H,I)3 2BFT 特征模型基 于对上述一族图算法问题的分析,利用FODM建模方法对在BFT领域中的服务S(service)、功能 F(function)和行为特点B(behavior characteristic)进行特征建模 根据以上分析,动态更新顶点优先级操作是该领域问题的可变特征,而遍历顶点、选择顶点、输出等操作是该领域的共性特征 通过分析在BFT 中的一些主要执行步骤,可以将其进一步
21、划分为初始化图信息、获取用户需求、选择优先级更新方法、算法组装和结果输出等功能,其中顶点初始化、动态更新优先级方法选择、构件组装为必选功能 在上述分析的基础上,顶点优先级的更新方式是该领域的 显著行为特点,本文主要选取了 Prim、DFS、Topological Sorting、BFS 和 Dijkstra 等5 种行为特点BFT 的特征模型图如图 5 所示图 5BFT 框架特征模型图55第 1 期轩瑞,等:图类算法可重用设计及其实现3 3图构件形式化设计和实现通过上述对一族图算法的问题分析以及对 BFT框架的特征建模,本节把在 BFT 特征模型中的功能和特征抽象作为构件,对特征之间的约束以及
22、依赖关系进行设计分析,建立算法构件之间的依赖关系图根据以上分析,将在 BFT 特征模型中的 4 个主要算法功能作为主要构件,其他特征作为辅助构件如图 6 所示,图中实线连接的节点为在 BFT 领域中必须的基本构件,实线箭头表示执行顺序,即操作构件(graph_op)、根据用户需求选择优先级更新方法构件(com_select)、算法组装构件(ass_algorithm)和结果输出构件(result)为主要构件;虚线箭头代表在算法执行过程中所需的数据、结构以及关联操作等,如在算法装配时,ass_algorithm 构件需要使用graph_op 构件和 prio_update 构件提供的操作和数据来
23、进行算法组装;点划线箭头表示在算法执行过程中 2 个构件之间的交互关系,如在 com_select 构件中,需要根据用户需求选择相应的 prio_update 构件中的顶点更新方式图 6算法构件依赖图基于 Apla 的敏捷泛型机制对得到的构件进行形式化实现,进而提高算法的抽象性 首先使用adl 对算法构件进行功能规约的描述,对其进行形式化推导;然后根据构件之间的依赖关系,将同一数据依赖源的构件封装为一个 ADT,并使用 Apla 语言形式化实现所有的 ADT 限于篇幅,这里仅给出了shortest_path 构件的功能规约:|in n:integer;c 0:n 1 0:n 1:array a
24、rray integer ;out dist 0:n 1 0:n 1:array array integer|AQ:n 0 c A:(i,j:0 i n,0 j n:dist i j(MIN p:p path i,j:cost(p),cost(p)(p:p path i,j:c i j)其中 in和 out 分别表示输入、输出变量;AQ 和 A 分别表示前置断言和后置断言;c 是一个 2 维数组,用来保存图的信息;dist 数组刻画了终止状态,为最终输出结果;在后置断言中path(i,j)表示顶点i和顶点j之间的所有路径;cost(p)使用了求和量词来表示顶点 i 和顶点 j 之间各个路径的权
25、值和根据 BFT 框架的特征模型以及构件之间的关系,使用 Apla 语言实现该领域构件 下面给出了主要的泛型算法构件定义以及参数的具体释义1)graph_op 类型构件 该构件被定义为一个ADT,内部包含了一些图算法的基本操作,如判断图类型、查找邻接点、设置权重、记录顶点入度、顶点出度、记录顶点父节点和设置边的状态等define ADT graph_op(sometype elem);type graph_op=private;function create():graph_op;function judge(G:graph_op):String;function nextNbr(i:elem
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 重用 设计 及其 实现 轩瑞
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。