两种新的电网连通性分析快速算法

第36卷第17期 2008年9月1日 电力系统保护与控制 PowerSystemProtectionandControl 、，01．36No．17 Sep．1，2008 两种新的电网连通性快速算法 黄家栋1，罗伟强1，赵永强2，付保军3 (1．华北电力大学电气工程学院，河北保定071003；2．北京电力公司，北京100054；3．天津电力公司，天津300210) 摘要：不同于以往基于网络节点的算法，在简单数据结构的基础上，依次提出了两种算法效率与网络节点半相关(节点标记 算法)及与网络节点完全无关(往返替换算法)的快速算法。理论分析和实例表明了这两种算法具有编程简单，不舍乘法运 算，需求存储空间小，对网络结构改变适应性良好的特点，大大缩短了电网连通性判别所需时间． 关键词：连通性；电力网络；快速算法；图论；邻接矩阵法 Twonewhigh-speedalgorithmsforelectricalnetworkconnectivityanalysis HUANGJia—don91，LUOWei—qian91，ZHAOYong·qian92，FUBao-jun3 (1．NoahChinaElectricPowerUniversity，Baoding071003，China；2．BeijingElectricPowerCompany。Beijing100054。China； 3．TianjinElectricPowerCompany,Tianjin300210，China) Abstract：UnlikepreviousalgorithmsbasedOilnetworknodes，thispaperproposesanode-branch—relatedalgorithm(NMA)anda branch—relatedalgorithmO'RA)basedonasimpledatastructure．Theoreticalanalysisandexamplesshowthatthetwonew algorithms玳ofnon—multiplication，withmuchlessstoragespace，easytoprogram,shorteningthetimetodiscriminatenetwork connectivity，andadaptabilewhennetworkstructurechanges． Keywords：connectivity；electricitynetwork；high-speedalgorithm；graphtheory；adjacencymatrix 中图分类号：TM744文献标识码： A 文章编号： 1674-34t5(2008)17-0016-03 0 引言 在研究电力系统中电力网，通信网等复杂网络 时，根据图论相关理论，都可以将它们抽象成拓扑 图来研究。网络拓扑研究中，一个基础而又重要的 方面是网络连通性分析问。如该问题可以为在线 潮流计算、状态估计、安全分析等提供网络结构数 据，是配网自动化和DMS高级应用功能的基础【ll。 随着现代电力系统规模扩大，网络节点的增多，网 络拓扑结构日益复杂，对网络连通性分析的有效性 和实时性提出了更高要求。 现有网络连通性分析算法主要有邻接矩阵法 和树搜索法【2’3】。邻接矩阵’法【4】及相关以邻接矩阵为 基础的算法【5】一般都存在存储开销与节点数Ⅳ的平 方成正比，算法效率为O(N2)，乘法运算为O(N4)Ⅲ， 计算量大，费时多，网络结构改变时算法重用性差。 当网络规模比较小的时候，这些算法还比较实用， 但Ⅳ一增长这些算法就很难忍受；树搜索方法主要 采用广度或深度优先的搜索方式，由于在晟坏情况 下得遍历所有节点，算法效率同样是D(Ⅳ2)，逻辑 运算为Max{O(N2)，O(MN)}，似为支路数目)，但 该方法对变电所和环状网络的适应性较差，同时由 于深度优先搜索法需要回溯，使得该方法在搜索过 程中搜索的节点数比实际网络含有的节点数多，而 影响了计算的速度【lJ。 为了解决以前算法存在的问题，本文从根源上 分析了以往算法在效率上很难提升的原因，进而提 出了算法效率及逻辑运算均为O(MN)的节点标记 算法及算法效率及逻辑运算均为D(^严)的往返替换 算法。 1 以往算法特征分析 在存储结构上，邻接矩阵法及相关算法不仅存 储了节点间有直接连接的关系，而且还存储了无直 接连接的关系。后种关系的存储，特别是当网络比 较稀疏，即支路比较少节点比较多时，属于浪费型 存储。 在算法效率上。以往算法均是仅基于节点类型 的算法，即运算或搜索时平均考虑节点间的所有信 息，不区分对待是否直接连接的关系。这类算法【4圳， 不可避免在最坏情况下均要遍历所有节点之间的所 有关系，因此效率必然是O(N2)。 万方数据 黄家栋，等 两种新的电网连通性分析快速算法 ．17． 如果我们把搜索主要放在具有直接连接的关 系——支路上，仅存储直接连接的支路，把支路作 为搜索出发点和内容，就可以避免许多无用搜索， 从而提出计算效率有很大改善的基于支路的算法来。 2新算法的提出 2．1算法的存储结构 为了减少存储空间，算法仅存储网络中的支 路。采用的存储结构如表1所示，因此我们定义两 个二维数组曰[阍，E【蜘，用于记录支路和节点间的 物理关联关系，即若第i条支路连接在节点．f和k 之间，则研司巧，研司或。如果是在Matlab中，则 可以采用一个EX2的矩阵来表示。 表1图的存储数据结构 Tab．1Structureforthedata’sstorage 当网络结构改变时，只要从数组或者矩阵中添 加或删除相应行数据即可。 2．2节点标记算法NMA(NodeMarkingAlgorithm) 该算法的主要是：用数组Ⅳs㈣记录每个 节点连通状态，Ⅳs【M的值表示节点属于哪个区域。 算法依次扫描支路，不断更新支路两端相连的两个 节点的连通状态。扫描完毕后，如果Ⅳs【J7v】中所有 值都一样，则网络连通，否则根据越嘲的值可以 判断该节点属于哪个区域。 根据以上思想，算法具体步骤如下： (1)输入M，Ⅳ及数组BIM]，研明；初始化数 组麒[』v]=0，D=0∞表示区域标记)，i=0。 (2)如果Ⅳs[曰【妇】和Ⅳs【研f】】均等于0，则做操作： ①口I=DI+1；②Ⅳs旧吲=D，Ns【研f】】=D，转(5)。 如果Ⅳs旧【f】】或Ⅳs【E[f】】等于0，则做操作：① Ⅳs[B【f】】=Ⅳs[B【f】】+Ⅳs【目f】】，麒【E【i】】_Ⅳs旧【f】】，转(5)。 如果ⅣS【口蚓◇Ⅳs[日f】】，则做操作：① ．mi。，,aue=min{Ⅳs旧【f]】，Ⅳs[Eli]】)，max，al。e=max(Ⅳs【日【f】】， Ⅳs陋吲l；(砻D=D—l，k=O，转(3)。 (3)如果Ⅳs【明>，，l缸。al。，贝0Ndk]=N,【幻一1；否贝0 如果腿嘲==】I，2双划∞，则腿嘲=蝴n，alue。 (4)k=k+l；如果kI，则输出网络非连通，否则连通。 由算法步骤知，算法所需要存储空间为 inaxfD(1v)，D(加}，在最坏情况下，算法要多次跳 转到步骤(3)，因此算法的效率为O(MN)，逻辑运算 为O(MN)，另外算法中不含有乘法运算，计算速度 十分快，很容易编程实现。 从算法中可以看出，若网络连通则区域标记D 等于1，否则D>I，且Ⅳs嘲值表示第k个节点属于 哪个区域。 2．3往返替换算法TRA(TravelReplacing Algorithm) 节点标记算法是借用了数组N。[N]记录节点连 通状态，那么这个数组Ⅳs【加是不一定需要的，我 们可以直接修改研蜘，E【^幻，通过a[Ml，研蜘最 后的状态来判剐网络是否连通。 图1往返替换算法

流程

快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计

图 Fig．1Flowchartoftravelreplacingalgorithm 由上提出了往返替换算法，该算法分两次扫描 支路，第一次从前往后扫描，根据当前支路两端相 连节点信息来更新后面所有支路两端信息。第二次 扫描是从后往前扫描，根据当前支路两端相连节点 信息来更新前面所有支路两端信息。算法更新方式 为：如果被更新的支路中含有和当前扫描支路相同 的节点，则用当前扫描支路上数值小的节点号替换 被更新支路中那个相同的节点。因此，给这个算法 取名为往返替换算法。扫描完毕，将所有支路左右 万方数据 ．18一 电力系统保护与控羽 交换排序，即如果支路的终止节点编号大于起始节 点，则将它们的值相互交换。网络是否连通的判定 方式为：如果支路的起始节点编号都等于1则网络 连通，否则不连通，根据起始节点编号一致的节点 属于同一子图，便可以判断节点属于哪个区域。 根据以上思想，算法具体流程如图1所示。其 中涉及到的顺替换过程具体步骤如下： (1)如果B[i]==maxv，则B[i]=minv；如果 E[i]==maxv，则E[i]=mJnv。 (2)f=f+l。如果i=0，则转(1)。 左右排序过程如下： (1)置i=O。 (2)如果口【f】>E【刁，贝Utmp=B[i】，B【f】=E【f】， E[i]=tmp。 (3)i=i+l，如果i论文

政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载