计算机科学 ›› 2020, Vol. 47 ›› Issue (11A): 584-590.doi: 10.11896/jsjkx.200200066
李红豫, 王郁昕
LI Hong-yu, WANG Yu-xin
摘要: 文中给出一种将有向无环图转换成代数表达式树的方法,该方法能够实现图的串联合并、并联合并和串行化合并,并且能够处理图中的函数型顶点。与以往的转换方法相比,文中所给出的转换能够处理类型更为广泛的图和顶点,因此应用也更为广泛。在给出转换方法的同时对转换的运行时间也进行了分析,考虑到实际应用情况,转换时间只与图中边的数量有关,所以转换的效率较高。
中图分类号:
[1] DUFFIN R J.Topology of series-parallel networks[J].Journal of Mathematical Analysis and Applications,1965,10(2):303-318. [2] VALDES J,TARJAN R E,LAWLER E L.The recognition of series parallel digraphs[C]//Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing.ACM:1-12. [3] HE X,YESHA Y.Parallel recognition and decomposition of two terminal series parallel graphs[J].Information and Computation,1987,75(1):15-38. [4] EPPSTEIN D.Parallel recognition of series-parallel graphs[J].Information and Computation,1992,98(1):41-55. [5] WELCH J T.Translating unrestricted relay ladder logic intoboolean form[J].Computers in Industry,1992,20(1):45-61. [6] WELCH J T.An event chaining relay ladder logic solver[J].Computers in industry,1995,27(1):65-74. [7] WELCH J T.Translating relay ladder logic for ccm solving[J].IEEE Transactions on Robotics and Automation,1997,13(1):148-153. [8] ZHOU B,YIN K T,JIANG H H,et al.QoS-based Selection ofMulti-Granularity Web Services for the Composition[J].Journal of Software,2011,6(3):366-373. [9] JAEGER M C,ROJEC-GOLDMANN G,MUHL G.QoS aggregation for Web service composition using workflow patterns[C]//IEEE EDOC Workshop.2004:149-159. [10] JAEGER M C,ROJEC-GOLDMANN G,MÜHL G.QoS Aggregation in Web Service Compositions[C]//IEEE 2005.2005:181-185. [11] ALRIFAI M,RISSE T,NEJDL W.A Hybrid Approach for Efficient Web Service Composition with End-to-End QoS Constraints[J].ACM Transactions on the Web,2012,6(2):1-31. [12] YAN Y,ZHANG H.Compiling ladder diagram into instruction list to comply with iec 61131-3[J].Computers in Industry,2010,61(5):448-462. [13] COMMISSION I E.International standard iec 61131-(third edition)[M].Programmable Logic Controllers part 3,2013. [14] MAN M,JOHANSSON S,RZN K E.Implementation aspects of the plc standard iec 1131-3[J].Control Engineering Practice,1998,6(4):547-555. [15] OTTO A,HELLMANN K.Iec 61131:A general overview and emerging trends[J].Industrial Electronics Magazine,IEEE,2009,3(4):27-31. [16] JOHN K H,TIEGELKAMP M.Theprogramming languages of iec 61131-3,IEC 61131-3[C]//Programming Industrial Automation Systems.2010:99-205. [17] THRAMBOULIDIS K,FREY G.Towards a model-driven iec61131-based development process in industrial automation[J].Journal of Software Engineering and Applications,2011,4(4):217. [18] BONDY J A,MURTY U S R.Graph theory with applications[M].Macmillan London,1976:290. [19] CORMEN T H,RIVEST R L,STEIN C.Introduction to Algorithms(third edition)[M].MIT Press,2009:603-610. [20] CORMEN T H,RIVEST R L,STEIN C.Introduction to Algorithms(third edition)[M].MIT Press,2009:595-602. |
[1] | 柴慧敏, 张勇, 方敏. 基于特征相似度聚类的空中目标分群方法 Aerial Target Grouping Method Based on Feature Similarity Clustering 计算机科学, 2022, 49(9): 70-75. https://doi.org/10.11896/jsjkx.210800203 |
[2] | 刘鑫, 王珺, 宋巧凤, 刘家豪. 一种基于AAE的协同多播主动缓存方案 Collaborative Multicast Proactive Caching Scheme Based on AAE 计算机科学, 2022, 49(9): 260-267. https://doi.org/10.11896/jsjkx.210800019 |
[3] | 宁晗阳, 马苗, 杨波, 刘士昌. 密码学智能化研究进展与分析 Research Progress and Analysis on Intelligent Cryptology 计算机科学, 2022, 49(9): 288-296. https://doi.org/10.11896/jsjkx.220300053 |
[4] | 姜洋洋, 宋丽华, 邢长友, 张国敏, 曾庆伟. 蜜罐博弈中信念驱动的攻防策略优化机制 Belief Driven Attack and Defense Policy Optimization Mechanism in Honeypot Game 计算机科学, 2022, 49(9): 333-339. https://doi.org/10.11896/jsjkx.220400011 |
[5] | 程富豪, 徐泰华, 陈建军, 宋晶晶, 杨习贝. 基于顶点粒k步搜索和粗糙集的强连通分量挖掘算法 Strongly Connected Components Mining Algorithm Based on k-step Search of Vertex Granule and Rough Set Theory 计算机科学, 2022, 49(8): 97-107. https://doi.org/10.11896/jsjkx.210700202 |
[6] | 陈俊, 何庆, 李守玉. 基于自适应反馈调节因子的阿基米德优化算法 Archimedes Optimization Algorithm Based on Adaptive Feedback Adjustment Factor 计算机科学, 2022, 49(8): 237-246. https://doi.org/10.11896/jsjkx.210700150 |
[7] | 刘卫明, 安冉, 毛伊敏. 基于聚类和WOA的并行支持向量机算法 Parallel Support Vector Machine Algorithm Based on Clustering and WOA 计算机科学, 2022, 49(7): 64-72. https://doi.org/10.11896/jsjkx.210500040 |
[8] | 唐枫, 冯翔, 虞慧群. 基于自适应知识迁移与资源分配的多任务协同优化算法 Multi-task Cooperative Optimization Algorithm Based on Adaptive Knowledge Transfer andResource Allocation 计算机科学, 2022, 49(7): 254-262. https://doi.org/10.11896/jsjkx.210600184 |
[9] | 张翀宇, 陈彦明, 李炜. 边缘计算中面向数据流的实时任务调度算法 Task Offloading Online Algorithm for Data Stream Edge Computing 计算机科学, 2022, 49(7): 263-270. https://doi.org/10.11896/jsjkx.210300195 |
[10] | 潘志勇, 程宝雷, 樊建席, 卞庆荣. 数据中心网络BCDC上的顶点独立生成树构造算法 Algorithm to Construct Node-independent Spanning Trees in Data Center Network BCDC 计算机科学, 2022, 49(7): 287-296. https://doi.org/10.11896/jsjkx.210500170 |
[11] | 高荣华, 白强, 王荣, 吴华瑞, 孙想. 改进注意力机制的多叉树网络多作物早期病害识别方法 Multi-tree Network Multi-crop Early Disease Recognition Method Based on Improved Attention Mechanism 计算机科学, 2022, 49(6A): 363-369. https://doi.org/10.11896/jsjkx.210500044 |
[12] | 高文龙, 周天阳, 朱俊虎, 赵子恒. 基于双向蚁群算法的网络攻击路径发现方法 Network Attack Path Discovery Method Based on Bidirectional Ant Colony Algorithm 计算机科学, 2022, 49(6A): 516-522. https://doi.org/10.11896/jsjkx.210500072 |
[13] | 常炳国, 石华龙, 常雨馨. 基于深度学习的黑色素瘤智能诊断多模型算法 Multi Model Algorithm for Intelligent Diagnosis of Melanoma Based on Deep Learning 计算机科学, 2022, 49(6A): 22-26. https://doi.org/10.11896/jsjkx.210500197 |
[14] | 康雁, 王海宁, 陶柳, 杨海潇, 杨学昆, 王飞, 李浩. 混合改进的花授粉算法与灰狼算法用于特征选择 Hybrid Improved Flower Pollination Algorithm and Gray Wolf Algorithm for Feature Selection 计算机科学, 2022, 49(6A): 125-132. https://doi.org/10.11896/jsjkx.210600135 |
[15] | 黄国兴, 杨泽铭, 卢为党, 彭宏, 王静文. 利用粒子滤波方法求解数据包络分析问题 Solve Data Envelopment Analysis Problems with Particle Filter 计算机科学, 2022, 49(6A): 159-164. https://doi.org/10.11896/jsjkx.210600110 |
|