实时全额支付系统中基于基本环的高效多边撮合算法分析和设计

• 作者: 李世梁
• 来源期刊: 计算机应用与软件
• 学科: 工学
• 关键词: 基本环 实时全额支付系统 清算 多边撮合
• 年，卷（期）: 2016,（9）
• 所属期刊栏目: 算 法
• 页码范围: 296-300
• 页数: 5页
• 分类号: TP3
• 字数: 5719字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-386x.2016.09.069

摘要

传统撮合法一般会找到一个可撮合环后，就立即进行撮合，属于典型的贪心算法。针对这种情况，提出从全局角度考虑多环清算。算法首先使用双边撮合和拓扑排序对有向图进行简化处理，剩下节点和边必然构成环，提高了查找基本环算法（时间复杂度：O n32()n ）的效率；对于多环共用公共节点的情况，利用银行家算法得出多环的安全推进序列；对于多环共用有向边的情况，不仅给出多环的安全推进序列，还考虑了共同撮合的情景。通过以上步骤，提升了多边撮合的性能，节约了参与机构的流动性、提高了资金使用效率。最后，给出了算法的时间复杂度分析和复杂案例应用（多环交于多点或多边）。