图搜索问题算法推导及形式化证明

用非形式化方法解决图搜索问题规模受限,对于一些复杂问题难以保证其正确性.传统的形式化方法推导图搜索问题难以理解且不易于形式化证明,现有形式化方法对这类问题的解决方案较少,在保证可靠性和正确性方面有欠缺.该文通过对图搜索问题的深入研究,开发出一种针对解决图搜索算法的新方法.首先刻画问题的规约,利用循环不变式的递归定义技术给出了开发图搜索问题循环不变式的新策略,在此基础上得到Apla抽象算法程序,并对该算法程序进行了形式化证明,再将已验证的Apla算法程序自动生成C++可执行程序,实现了从抽象的形式规约推演出具体的面向计算机的程序代码的程序精化完整过程.以拓扑排序和广度优先遍历为例对所提方法进行实验,实验结果验证了所提方法的有效性,不仅可以推导和证明已知算法,而且对未知算法的推导也有指导性作用.     

寻找λ-边连通子图的一次遍历搜索算法

寻找图的λ-边连通子图时,可利用深度优先搜索算法,但需要经过λ次的遍历搜索过程才能完成.基于图的邻接矩阵储存结构特点,提出了一种新的搜索算法,可以通过一次遍历搜索过程得到图的λ-边连通子图.对比深度优先搜索算法,新算法结构简单,容易实现,大大提高了算法的执行效率.这种搜索算法也可以用于判定图的连通性.     

状态空间搜索的几种算法讨论

论述了状态空间搜索的几种算法,给出了深度优先搜索、广度优先搜索和启发式搜索之间的算法比较.通过比较,得到了这样一个结论在通常情况下,采用启发式搜索算法来进行状态空间的搜索更为方便、快捷.     

广度优先搜索算法在交叉立方体中的应用

给出了互连网络上的广度优先搜索算法，将其应用到交叉立方体上可以得到交叉立方体的广度优先生成树。连通图的广度优先生成树的树高不会超过该图其他同根生成树的高度。利用这一性质，通过分析交叉立方体的广度优先生成树的特征，给出了n维交叉立方体CQ的直径为[(n 1)／2]的另外一种证明方法；该算法可以用来求解单源节点最短路径问题。并为讨论新的互连网络拓扑结构的直径和故障直径问题以及单源广播算法提供了一条新的思路。     

状态空间搜索的几种算法讨论

论述了状态空间搜索的几种算法，给出了深度优先搜索、广度优先搜索和启发式搜索之间的算法比较。通过比较，得到了这样一个结论：在通常情况下，采用启发式搜索算法来进行状态空间搜索更为方便、快捷。     

图的遍历的分析与算法设计

本文分析了图的深度优先搜索和广度优先搜索遍历的思想,用邻接表设计了其算法,并介绍了图的遍历的应用.     

引入方向因子的最小回路、最大回路搜索算法

提出了最小回路、最大回路和方向因子的概念，基于方向因子构造了最小回路、最大回路搜索算法。算法依据图论知识，建立改进后的无向图邻接矩阵，根据节点坐标确定搜索始点，将搜索边失量化，结合节点坐标求解邻接边的方向因子，按方向因子的大小可以快速确定搜索边，形成了无向图中最小回路、最大回路搜索算法。该算法每搜索一次都可以确定一条搜索边，通过生成退化图减小下一次搜索的搜索范围，提高了搜索速度，反映出较小的时间复杂度。根据该算法编制了相应的算法程序，成功解决了建筑工程量计算中的外墙壁和房间划分问题。     

基于攻击模式的广度搜索攻击图生成算法

网络攻击者一旦发生攻击行为,通常希望攻击行为能危害到最大范围,基于这一前提,依据广度优先搜索策略及属性攻击图模型,提出了基于攻击模式的广度搜索攻击图的生成算法,算法可以很快的生成攻击图并且规模明显减小,最后对该算法的性能进行了分析和实验分析。     

基于广度搜索的增量式点云表面重建

将人工智能中广度优先的搜索算法引入散乱点云表面重建领域，借助增量计算思想，基于搜索算法状态不断扩展的特点，渐进均匀地扩展重建整个物体表面.算法以初始三角面片初始化搜索队列，以有向边为搜索元素，借助于八叉树空间划分和搜索约束条件，快速完成最优点评估及三角片重建，具有可视化并行计算、选择性填补空洞以及重建结果与参数弱耦合等特点.实验结果表明，本算法高效、稳定，可以重构任意拓扑结构的二维流形三角形网格.     

一种改进的BNS网络论坛搜索算法

为了提高网页在互联网中的搜索效率,基于非结构化P2P网络的多种搜索算法和网络蜘蛛搜索算法,提出了一种广度优先搜索(BFS)和非贪婪性搜索(NGS)相结合的改进搜索算法(BNS)。并通过该算法的性能分析与大理学院校园BBS的应用测试,结果表明,BNS算法在搜索速率、相关度和准确率上都优于BFS和NGS算法,该算法的实际应用提高了网络论坛运行效率。     

边坡稳定的三维有限元直接搜索法

提出了一种基于三维有限元应力场计算边坡安全系数与直接搜索临界滑裂面的新方法.对临界滑裂面上的应力分布直接使用三维有限元计算的应力结果,并且直接利用三维有限元的单元体网格面作为滑移面搜索网格面.鉴于有限元单元体网格和图的直观相似性,可以把网格抽象成图,通过引用动态规划中最优化思想搜索临界滑裂面.以三维均质边坡为例,通过三维极限平衡法、三维强度折减法与本文方法的对比分析,验证了本文方法的正确性与合理性.     

基于构件的若干图算法开发和生成

软件构件技术可显著提高程序的可靠性和开发效率,极大减少开发成本.泛型程序设计有助于降低编程的复杂度,为重用构件开发提供有效支持.介绍了生成式程序设计思想及泛型程序设计技术,分析了图算法领域的关键特征及领域共性问题,并对广度优先搜索、单源最短路径、所有顶点对最短路径等一类问题进行抽象,设计出相应的泛型图算法构件,进一步借助PAR方法中的泛型机制进行描述,并在PAR平台程序生成系统上进行构件组装生成具体的算法程序.     

交通系统中最少换乘算法及其实现

把图论中针对单个结点的广度优先搜索思想,推广到拥有若干个结点集合的广度优先搜索上,对旅游路线中最佳路径的问题,提出一种新的算法,可解决旅游路线中的最少换乘问题,并巳成功地在计算机上实现。     

混合的深度优先及宽度优先球形译码算法

结合深度优先及宽度优先算法,提出了一种混合算法,将搜索树分成两部分:一部分进行深度优先搜索;另一部分进行宽度优先搜索.利用深度优先搜索的结果裁剪宽度优先搜索中那些距离较大的点,以降低搜索复杂度.该算法合理地综合了2种算法的优点,具有较低的计算复杂度及较高的性能.仿真结果表明,该算法的性能与最优算法相比差别非常小,与宽度优先算法相比节省了大量的计算复杂度,在高信噪比的情况下,计算复杂度的节省尤其明显.     

Efficient Heuristic Variable Ordering of OBDDs

Introduction　　Orderedbinarydecisiondiagrams(OBDDs)[1]areefficientrepresentationsofBooleanfunctions.However,thesizeofOBDDsdependsheavilyonvariableordering[1].HowtofindasatisfyingvariableorderisthuscrucialtotheapplicationofOBDDs[211].HeuristicanddynamicmethodsarewidelyusedinorderingthevariablesforOBDDs.Heuristicmethodsusetheinformationimpliedinthecircuitstructure,whiledynamicmethodsimprovethevariableordergraduallyongivenOBDDs.Althoughadynamicmethodmaygivebetterresults,itsruntimedepen…     

利用超链接信息改进网页爬行器的搜索策略

网页爬行器在Web空间中爬行时,要面对如下两个问题:1)由于Internet上的信息量十分巨大,网络搜索引擎不可能包含整个Web网页;2)受到硬件资源的限制,它所能存储的网页是有限的.爬行器如果按照传统的宽度优先搜索策略在Web空间中爬行,它对所有的网页都采取一视同仁的态度,这样爬行的结果就导致了它所爬行回来的网页质量不高.为此,给出了利用超链接信息改进网页爬行器搜索策略的算法.该算法充分考虑了网页之间的超链接信息,克服了传统的宽度优先搜索策略的盲目性爬行.实验表明,利用该算法爬行得到的网页与某一特定主题相关的网页超过50%.     

一种多约束的应用层组播路由算法

由于IP多播在应用上的困难。应用层网络作为多播服务平台逐步被人们认可。针对实时多媒体应用对带宽需求和时延约束的特性,提出了一种新的构造应用层最小直径多播树的启发式算法PCT,该算法结合深度可调的广度优先搜索策略,根据带宽和时延的策略函数选择既满足要求又节约网络资源的路径。实验表明该算法能够有效地降低多播树的直径,减少多播树时延并具有广泛的适应性。     

基于信噪比排序的MIMO-OFDM信号检测方法

在多输入多输出(multiple-input multiple-output,MIMO)系统信号检测中,基于虚实分解的宽度优先检测算法(QR decomposition associated with the M-algorithm to MLD,QRD-M)通过QR分解和对每层星座点的筛选,实现了较低复杂度的检测,具有很好的应用前景.但该算法随收发天线数和调制阶数的增加而难以实现性能与复杂度的折衷.针对此缺点,提出了一种基于信噪比排序的信号检测改进方法.该方法在传统QRD-M算法的基础上,通过对不同接收天线进行信噪比(signal-noise ratio,SNR)排序,从信噪比最大的天线开始检测,避免了误差传播现象,从而加速树搜索过程,再结合动态门限树搜索,不断缩小搜索半径,直至找到最小累计度量值所在分支.仿真结果表明,与传统QRD-MLD算法相比,基于性噪比排序的动态门限信号检测算法能以较低的复杂度获得接近于最大似然检测的性能.