基于Warshall算法的可达矩阵的算法改进及Python程序实现

基于Warshall算法的可达矩阵的算法改进及Python

程序实现冯海亮，亓洪胜(蚌埠学院理学院安徽蚌埠 2 3 3 030 )【摘要】可达矩阵是研究有向图的连通性等问题的重要代数工具.本文利用Warshall算法对可达矩阵的算法进行了 改进，减少了计算量；然后通过实例给出了该算法的Python程序实现.【关快词】可达矩阵；邻接矩阵；Warshall算法；布尔运算；Python【中图分类号】G0 【文献标识码】A 【文章编号】1009-5624 ( 2019 ) 08-0074-021相关概念、性质设有向图 G=,顶点集 V = \\yi，v2,--,vn}, 边集E = {ex,e2,-,em}.定义1.1有向图G的邻接矩阵表示图G中顶点片到顶点Vj长度为m的通路的条数。定理1. 2若从顶点v,(i = 1,2, -,»)到顶点”心= 1,2,存在通路，则从顶点片到顶点少必存在一条长度小于顶点 总数\"的通路。 *证明：设「是从叫到b的一条通路，去掉其中的回

A =其中切为顶点叫邻接到顶点Vj的边的条数，■ =1 9 ... » ' = ] 9 • • • mS 1.1设；烏着向图G的邻接矩阵，记

路(只保留该回路的起始点),剩下一条从叫到Vj的路径, 长度小于\"。证毕定义1.2有向图G的可达矩阵⑴P = (Py)”x”=1,2,3,…,则元素4畀(i = 1,2,…,\"J = 1,2,…，”)

射信道的传输模式进行规律分码，在将此类信号加载波体 进行等向发射。在信号接收过程中，以多个接收天线为 基准，通过信号信道的定向传输模式，将传输过来的数 据进行子流、副本分类，以此来实现数据信息的差异性 检索。从原理层面来讲，BLAST技术和扩谱技术较为相似， 即发射天线设备等同于用户基数，接收天线设备等同于 扩谱拓展增益，釆用动态检测系统来对信号进行分离。 以此种模式为基准，可有效减少信号在传输过程中的过 度损耗，并可实现信号的等量并行传输，以提升实际传

整的分集效益，以此来简化信号传输模式。4 MIM0技术的发展方向现阶段，在技术的不断更新下，MIMO天线技术也逐渐向 成熟方向发展。MIMO天线技术是以硬件设施为搭载平台，对 信号进行网络区域内的精准传输，但在信号实际传输过程中 由于不同种设施的选择，易对传输波率造成一定的损耗，为 提升MIMO技术的实际应用效率，应对硬件设施进行基准设定， 例如模块化选取、开关的切换速度等，以确保MIMO技术可 实现5G商用模式，以提升网络区域内的传输效率。与此同时， 应注重信号传输过程中的影响因子，例如环境因素、其它设 施因素、传播距离因素等，为保证空间传输状态下的稳定性， 应提升信道链路传输的能力，通过统计量(二阶统计模式) 的工作形式来简化信号传输模式，进而减少信号的衰减程度, 进一步提升信号传输的稳定性、效率性与质量性。5结语

综上所述，MIM系统作为通信领域的关键技术之一， 通过对信号进行多项定点的传输，可有效改善网络系统运 行的稳定性，以提升信号的传输质量。输效率。3. 2 STTC关键技术STTC技术是指空时格形码，其作为编码器的一个框架

结构，可将信息传输渠道作为一个限量整体，用来测试传 输状态的平台，以保证对编码器内部信息状态的变化进行 实时监控，进而实现发射天线对信号的基准传输。通过STTC的融合式调节作用，将编码形式、调制模 式进行融合处理，可有效提升译码效率，并实现效率与频

带的多功能调节，以满足信号的传输需求。另外，在STTC 技术的应用下，可提升MIMO技术的分集效益，在同等的 传输资源作用下，可实现令现有系统提升3〜5倍的传输 效率，以满足复杂型的传输状态。3. 3 STBC关键技术【参考文献】[1] 陶玉林.探析无线通信技术及5G关键技术[J].信息通 信,2018(10):235-236.[2] 洪家振.对3D-MIM0天线技术应用的探讨[J].网络安全技 术与应用,2018 (08):71-72.STBC是指空时分组码技术，在同等分集效益的基础上,

可对发射天线设备、接收天线设备的数量进行自主转换，

以提升MIMO技术的应用范围。STBC技术的实际工作原理 是以正交模式为主，在空间维度、时间维度的正交编码下, 将信号合理地分配到发射天线中，以保证STBC可获取完

基金项目：移动通信中的小型MIMO天线设计研究，课题编号: 2016WXYB005,项目负责人：‘范荣74______________________________________________信息记录材料2019年8月第2 0卷第8期fQ：技术与应用〕其中P°=l当且仅当顶点叫可达顶点少；否则 Ptj = 0 > i = l,2,- -,n,j-\\,2,- -,n .#导入numpy包import numpy as np规定儿可达叫¢ = 1,2,-/),即P的主对角线上的 元素全为1.2可达矩阵的算法利用定理1.1和定理1. 2可得可达矩阵的如下算法：#输入邻接矩阵adj_matrix=np. matrix([[0,1, 0, 0,0], [0, 0, 0,1, 0], [0, 0, 0, 0, 0], [1, 0, 1, 2, 0]])[0, 0,1, 0,1],#把所有非0元素和主对角线元素改为1reach_matrix=adj_matrix+np. eye(len(adj_matrix)) for i in range(0, len(reach_matrix)):算法2.1写出G的邻接矩阵计算P0 = A + A2 +■■■ + A\"-',把矩阵人的非0元素和主对角线元素全部改为1,即 得可达矩阵P.算法2.2写出G的邻接矩阵X,把彳的所有非0元

for j in range(0, len(reach_matrix)):

reach_matrix[i,j]=1 if reach_

matrix[i, j]!=0 else 0素和主对角线元素全部改为1,记为4),则G的可达矩阵p = 4)+ 4)2 + …+4>\"“，#按Warshall算法对改造后的邻接矩阵进行迭代for k in range(0, len(reach_matrix)):其中矩阵的运算按布尔加法和乘法进行，如表2-1和 for i in range(0, len(reach_matrix)):

for j in range(0, len(reach_matrix)):

reach_matrix[i, j]= reach_

表 2-2：表2-1布尔加法+matrix[i, k]* reach_matrix[k, j]\\1001if reach_matrix[i, j]=0 else 10111#输出可达矩阵print(reach_matrix)表2-2布尔乘法*00010101<11结果为说明：这两种算法没有本质的区别，都是遍历了任

11111111001100001011111意两个顶点间长度小于总顶点数的所有通路，需要进行 \"2 (“2 _ 2“ + 3)(“ - 2)次加法运算和\"’5-1)(\" 一2)次乘2 2

4结论本文介绍了可达矩阵的常规算法，并利用Warshall

法运算。由此可以引申出ISM算法図。3算法的改进及Python程序实现1962年，Warshall提出了一个求关系的传递闭包

算法对其进行改进，然后给出了算法的Python程序。 只要去掉主对角线全为1的硬性规定，并对Python程 序做出相应调整，就可以实现对有向无环图(DAG)⑶

的算法。该算法从邻接矩阵/出发，得到矩阵序列 \"血…人，对九仗= 1,2,…，”)仅寻找任意两点间的

的判定。这样的通路——中间只经过中的节点，需 要进行\"3次加法运算和\"3次乘法运算，从而可以有效减 少计算量。下面通过一个实例给出该算法的Python程序.[参考文献1[1] 丁树良，罗芬，汪文义，熊建华.0-1和多值可达矩阵的 性质及应用[N],江西：江西师范大学学报(自然科学版)，

例3.1求有向图的可达矩阵.2015. 01: -6&[2] 白冰，李平.基于ISM的可达矩阵的简便算法[J],价值工程, 2015 (04): 213-215.[3] 王福友.基于分离树的含潜变量有向无环图的结构学习[D],

吉林：长春工业大学，2018.作者简介：冯海亮( 1982-),男，汉族，山东临购人，硕士 研究生，助教，研究方向：解析数论.75