检索结果-南通市图书馆

作者：朱哿东北石油大学

学位级别：硕士

软件测试是保证软件开发质量和生命力的重要手段,随着现代软件结构规模的不断扩大和构件化软件开发思想的广泛应用,软件的开发效率有了极大的提高,然而与构件化开发高速发展不符的是,构件的测试技术发展缓慢。由于软件构件自身的特点,... 详细信息

软件测试是保证软件开发质量和生命力的重要手段,随着现代软件结构规模的不断扩大和构件化软件开发思想的广泛应用,软件的开发效率有了极大的提高,然而与构件化开发高速发展不符的是,构件的测试技术发展缓慢。由于软件构件自身的特点,构件的使用者无法获知构件内部的结构,传统的软件测试无法应用于构件的测试工作中。本文针对软件构件难于测试的问题,分析了影响构件测试实施的因素,引入构件内建测试的思想,通过在构件内部建立观察点的方式提高构件的可测试性。同时设计了一种基于改进的遗传算法的构件测试模型,对构件的逻辑路径进行覆盖探测,实现了构件的路径覆盖测试用例自动生成,将其应用在构件的实际开发过程中。本文的主要内容包括:针对构件测试的难点和影响构件测试的因素,提出了通过引入内建自测试思想保证构件的可测试性,在构件开发的同时在其内部留下支持测试的测试点,描述观察点的关键信息,以此支撑测试系统对构件的测试能力。针对构件程序内部逻辑结构复杂难于进行有针对性探测的难点,利用遗传算法强大的非线性搜索能力,进行对构件逻辑路径的覆盖探测,为解决传统遗传算法使用固定遗传算子极易出现过早收敛或陷入迟钝状态的问题,对遗传算法进行了自适应的改进,使得遗传算法能有效避免陷入局部最优的同时最大限度的保留其高效的搜索能力。将本文的构件可测试开发方法和遗传算法路径覆盖测试数据生成技术结合,建立了路径覆盖测试用例生成模型,将利用该模型开发的测试系统应用于油田软件构件开发测试,验证了构件可测试开发和遗传算法路径覆盖测试的实用性与高效性。

关键词：软件构件可测试性内建测试遗传算法路径覆盖

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

有向传感器网络栅栏覆盖研究

有向传感器网络栅栏覆盖研究

作者：肖玉杰太原理工大学

学位级别：硕士

有向传感器网络作为无线传感器网络一种特殊形态,增加了具有方向性的传感器节点如视频传感器、微型麦克风、雷达等,可以采集视频、音频、图像等多媒体信息。覆盖控制作为无线传感器网络的首要问题,它可对网络的时空资源优化分配。栅栏... 详细信息

有向传感器网络作为无线传感器网络一种特殊形态,增加了具有方向性的传感器节点如视频传感器、微型麦克风、雷达等,可以采集视频、音频、图像等多媒体信息。覆盖控制作为无线传感器网络的首要问题,它可对网络的时空资源优化分配。栅栏覆盖作为覆盖控制的子问题,主要研究移动目标穿越监控区域时被传感器节点监测的问题。目前,传统无线传感器网络栅栏覆盖控制研究已经积累了一定研究成果,但有向传感器网络的栅栏覆盖只取得初步成果。因此,迫切需要对有向传感器网络中栅栏覆盖控制算法进行探讨与研究。本文针对有向传感器网络中栅栏覆盖,进行了如下几方面研究:（1）研究了由可移动传感器与固定传感器组成的有向传感器网络中的强栅栏覆盖问题。当有向传感器节点随机部署于窄带区域,传感器之间存在大量重叠感知区域,产生大量冗余信息,不利于资源的有效利用。本文引入了重叠感知比OSR（overlap-sense ratio）概念,基于OSR对随机部署后形成的强连通簇内节点进行调节,减少了重叠感知区域;针对如何利用可移动传感器填充栅栏间隙问题,将该问题转化为二部图赋权匹配问题。并利用改进的匈牙利算法进行解决,最后,提出OSR-SBC算法。仿真实验表明该算法较大幅度减少覆盖重叠区域,同时,所需可移动传感器节点数目与移动距离较大幅度减少。（2）研究了有向传感器网络中路径覆盖问题。路径覆盖本质是著名的art gallery问题,它是NP-hard问题。本文提出以节点“邻居集”共同覆盖率为导向因子的改进粒子群覆盖增强算法。首先,将路径覆盖模型转化为寻求节点最优朝向的优化问题,并将标准粒子群算法应用于该优化问题的解决。其次,针对标准粒子群算法收敛时间长、易陷入局部极值等缺点,提出节点“邻居集”共同覆盖率概念,并将其作为导向因子指导微粒的进化,进而得到最优网络覆盖。最后,通过仿真测试算法的性能。实验结果表明改进的粒子群路径覆盖增强算法能够明显地提高路径覆盖率且克服了标准粒子群算法的缺点。综上所述,本文对有向传感器网络强栅栏覆盖构建和路径覆盖两方面进行研究,并通过仿真实验验证了算法的有效性,为进一步研究有向传感器网络栅栏覆盖提供了理论基础。

关键词：有向传感器网络栅栏覆盖重叠感知比路径覆盖粒子群优化算法

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于搜索的回归测试数据生成方法研究

基于搜索的回归测试数据生成方法研究

作者：高露西安邮电大学

学位级别：硕士

随着软件应用在各个行业领域的作用日益重要,对软件规模和质量的要求也日益增高。软件测试是目前软件质量保障的主要手段,其中回归测试一般占测试成本的80%,因此提高回归测试的效率是非常有必要的。在软件生命周期中,由于频繁地对软件... 详细信息

随着软件应用在各个行业领域的作用日益重要,对软件规模和质量的要求也日益增高。软件测试是目前软件质量保障的主要手段,其中回归测试一般占测试成本的80%,因此提高回归测试的效率是非常有必要的。在软件生命周期中,由于频繁地对软件进行更新换代,从而导致原测试数据集往往无法覆盖到软件新增或修改的部分,进而无法揭示软件中存在的缺陷或潜在错误。为了保证原测试数据集对新版本软件的完备性,则需要对其进行扩充。本文针对回归测试数据生成过程中存在的不同问题,利用基于搜索的测试数据生成技术,提出适应于各个场景的测试数据生成方法,并通过实验验证方法在特定场景下的可行性。主要工作如下:1、在程序缺陷修复后进行回归测试的场景下,针对测试数据生成过程易陷入局部最优的问题,提出一种基于文化基因算法的回归测试数据集生成方法。对Java程序进行测试执行分析提取理论路径集,基于相关性检测可达路径并进而优化排序,从而得到覆盖目标路径集,再依据路径覆盖准则建立回归测试数据生成模型,并采用文化基因算法进行测试数据的生成。将不同的方法应用于五个基准程序进行对比试验,结果表明该方法覆盖率平均提高14.4%,生成时间平均提高57%,在一定程度上提高了测试数据生成的效率。2、在软件系统新增功能模块之后进行回归测试的场景下,针对原有测试数据集往往不能满足新版本软件测试需求的问题,提出一种基于搜索的分层回归测试数据集扩增方法。依次从方法和语句级别提取覆盖目标,利用贝叶斯理论对覆盖目标方法集进行优先选择,进而对其进行静态分析提取目标路径,再针对目标路径集利用文化基因算法生成测试数据。将本方法与随机法、遗传法、和粒子群算法进行对比实验,结果反映出该方法的生成效率至少提高50.5%,测试数据的检错能力至少提高18.2%,为有效提升测试数据集的充分性提供了一种思路。3、针对多任务测试数据生成问题,提出一种基于Spark的多因子进化回归测试数据集生成方法。获取覆盖目标任务,利用Spark框架的分布式弹性数据集将目标任务集进行分解并下发到各个结点,再启动Spark分布式环境中各个集群结点,利用多因子进化算法生成测试数据。将该方法应用于五个基准程序并与基于独立搜索的方法进行对比,实验证明本方法可以有效地解决多任务问题,且生成效率至少提高3倍。4、依据本文提出的测试数据生成方法,利用UML统一建模语言中的顺序图和交互图,完成对该系统的建模,设计开发了一个面向回归测试数据生成的原型系统。

关键词：回归测试测试数据生成路径覆盖文化基因算法 Spark

基于遗传算法的测试用例产生系统关键技术研究

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于遗传算法的测试用例产生系统关键技术研究

作者：顾鹏华中科技大学

学位级别：硕士

测试用例的自动产生方法是目前软件测试领域研究的重要内容之一。遗传算法作为一种高效的搜索寻优算法,近年来日益受到国际学术界的重视,由于该算法具有较强的建模能力和自适应性,也越来越受到软件测试界的重视,逐渐成为测试用例产生方... 详细信息

测试用例的自动产生方法是目前软件测试领域研究的重要内容之一。遗传算法作为一种高效的搜索寻优算法,近年来日益受到国际学术界的重视,由于该算法具有较强的建模能力和自适应性,也越来越受到软件测试界的重视,逐渐成为测试用例产生方法的重要研究内容之一。将遗传算法用于测试用例产生系统时,适应度函数是影响算法效率的关键,选择算子则是决定算法能否同时产生多条路径上的测试用例的主要因素。目前用遗传算法产生多参数程序的测试用例时效率较低,而且无法同时产生多条路径上的测试用例。为了解决这些问题,需要设计高效的适应度函数,寻求能产生多条路径上测试用例的选择算子。为了克服现有遗传算法产生测试用例时效率较低的缺陷,通过分析适应度函数的特点,研究参数个体及其覆盖路径与适应度函数之间的关系,设计了基于海明距离的适应度函数方案,该适应度函数利用路径覆盖状态的决策变量作为参数。在此基础上,用二重结构编码方法对个体进行编码,除变量码表示个体值外,使用附加码表示交叉和变异操作的操作点范围,以提高算法的局部搜索能力。针对基本遗传算法每次只能产生一条路径上测试用例的问题,研究了选择算子对优化目标准则的影响。从多目标优化的角度设计了基于轮盘赌选择方法的加权选择算子,同时考虑所有目标路径对个体选择概率的影响,提高算法产生多条路径上测试用例的能力。将基于适应度函数和选择算子的改进整合,结合基本遗传算法的体系结构,提出改进遗传算法,并应用到测试用例产生问题中。研究结果表明,改进后的算法搜索效率高于基本遗传算法,并且具备了一次处理多条目标路径的功能,具有一定的实用价值。

关键词：测试用例路径覆盖遗传算法适应度函数选择算子

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

覆盖率导向式灰盒模糊测试优化方法研究

覆盖率导向式灰盒模糊测试优化方法研究

作者：葛羽丰北京交通大学

学位级别：硕士

模糊测试技术(fuzzing)由于自动化程度高,测试速度快的优点,已经被证明是最有效的漏洞检测技术之一。然而模糊测试的测试用例生成方式过于盲目和随机,导致其浪费大量时间用于无效测试。以覆盖率为导向的灰盒模糊测试是一种白盒模糊测试... 详细信息

模糊测试技术(fuzzing)由于自动化程度高,测试速度快的优点,已经被证明是最有效的漏洞检测技术之一。然而模糊测试的测试用例生成方式过于盲目和随机,导致其浪费大量时间用于无效测试。以覆盖率为导向的灰盒模糊测试是一种白盒模糊测试与黑盒模糊测试相结合的漏洞检测技术,它通过在程序中轻量级插桩获取程序运行时的关键信息,同时利用这部分关键信息引导测试用例生成,以探索程序的新路径。AFL(American Fuzzy Lop)是目前最优秀的覆盖率导向式灰盒模糊测试工具之一,也是模糊测试领域的研究重点。AFL的优势明显但依然存在一些缺陷。首先,AFL的变异策略将种子文件的所有字节区域视为等价,这使得AFL浪费太多时间在无效区域的变异上;其次,对于某些较大的种子文件,AFL将陷入挂起状态,这将导致开销急剧增加。针对以上问题,本文的工作如下:(1)提出了一种变异策略优化方法。该方法利用程序的局部性原理对AFL的变异策略进行优化,通过对每个种子文件设置动态偏移量,选择性的对偏移量附近的字节和头部字节进行变异,从而提高模糊测试的路径覆盖率和效率。(2)提出了一种调度策略优化方法。针对某些较大的种子文件,本文通过设置新增路径阈值和时间阈值,当变异不足以产生足够多的路径或者耗费太多时间时,立即跳过当前变异阶段,防止测试进入挂起状态。(3)本文在AFL的基础上利用上述方法实现了覆盖率导向式灰盒模糊测试工具AFLEdge,并以AFL和AFLFast作为基准线,选取四个真实程序和一个公开测试集进行对比实验,分析比较三者的路径覆盖率和漏洞检测能力。实验表明,AFLEdge在24小时内的路径覆盖总数相较于AFL和AFLFast分别提升了92.4%和49.3%;在漏洞检测方面,AFLEdge在24小时内发现的漏洞数比AFL提升了75.0%,基本与AFLFast持平,证明了本文提出的优化方法的有效性。

关键词：灰盒模糊测试 AFL 路径覆盖漏洞挖掘变异策略调度策略

基于改进差分进化算法的软件测试用例自动化生成问题求解

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于改进差分进化算法的软件测试用例自动化生成问题求解

作者：卓晓燕华南理工大学

学位级别：硕士

为了确保软件产品的质量,需要对产品进行软件测试。为了获得零缺陷质量的软件产品,需要生成无限个测试用例;但在现实世界中,这种穷举调试是不可行的,所以在测试过程中需要找到一种优化方法,自动化生成软件测试用例,在不对质量妥协的前... 详细信息

为了确保软件产品的质量,需要对产品进行软件测试。为了获得零缺陷质量的软件产品,需要生成无限个测试用例;但在现实世界中,这种穷举调试是不可行的,所以在测试过程中需要找到一种优化方法,自动化生成软件测试用例,在不对质量妥协的前提下降低所需的资源。在所有基于覆盖的测试数据生成方式中,路径覆盖具有较强的纠错能力,可以较为全面地检测软件中的缺陷,因而受到广泛的关注。基于路径覆盖的软件测试用例自动化生成问题已有大量的研究成果,多数研究从群智能算法出发,但仍有很多问题需要解决,例如如何优化算法的求解性能。本文分析了基于路径覆盖的软件测试用例自动化生成问题的特点,设计了适合多路径同时搜索的自适应适应值评估函数,提出了基于局部搜索的差分进化算法,应用于该问题的求解,研究工作包括以下三个方面:(1)设计了适合多路径同时搜索的自适应适应值评估函数,比起以往的评估函数,该函数不需要随机选定一条路径作为目标,可以引导个体去覆盖任何一条未被覆盖过的分支。研究中结合新提出的适应值函数,将适合求解多变量的组合优化问题的差分进化算法应用到基于路径覆盖的软件测试用例自动化生成问题的求解中,与随机算法、遗传算法和人工蜂群算法相比,基于自适应适应值函数的差分进化算法表现出了更优的性能,在实现对待测软件程序路径100%覆盖率时消耗的候选测试用例更少。(2)针对软件程序不同路径之间存在差异性的特点,研究中尝试通过引导个体去探索未被开发的区域来改进差分进化算法的搜索能力,提出基于局部搜索的差分进化算法。当某个个体长时间未能生成覆盖新路径的有效用例,并且未生成有效用例的累计次数超过一定阈值时,算法将引导该个体在有效测试用例落点最少的区域进行探索,从而优化算法求解问题的性能。(3)设计了一个基于路径覆盖的软件测试用例自动化生成软件,并将文中提出的改进差分进化算法作为核心算法。将软件应用到天气决策树软件、字典树软件的测试用例生成中,运行结果表明,该软件能在较短时间内生成覆盖待测软件程序不同路径的有效测试用例,并且路径覆盖率可以达到100%。

关键词：差分进化算法自适应适应值函数路径覆盖测试用例生成

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于遗传算法的测试用例自动生成技术研究

基于遗传算法的测试用例自动生成技术研究

作者：林惠娟四川大学

学位级别：硕士

随着计算机技术的不断发展,软件的规模越来越大,复杂度也不断提高;因而软件的错误也越来越隐蔽,造成的后果也就越来越严重。因此,提高软件质量及可靠性已成为软件工程领域当前的重要任务。软件测试是软件开发过程中极其重要的一环,是... 详细信息

随着计算机技术的不断发展,软件的规模越来越大,复杂度也不断提高;因而软件的错误也越来越隐蔽,造成的后果也就越来越严重。因此,提高软件质量及可靠性已成为软件工程领域当前的重要任务。软件测试是软件开发过程中极其重要的一环,是保证软件质量、提高软件可靠性的关键。同时,它也是一个复杂的过程,需要耗费巨大的人力、物力和时间,其成本约占整个软件开发成本的40– 50 %。可见,提高软件测试的自动化程度对于确保软件开发质量、降低软件开发成本非常重要,而其中,提高生成测试用例的自动化程度又是提高测试自动化程度的关键。本文作者从这一问题入手进行了研究,主要工作如下: 1.测试及遗传算法的基本理论研究文中首先介绍了软件测试及软件测试用例生成技术的基本理论,然后介绍了遗传算法的基本原理和主要操作。 2.基于遗传算法的分支覆盖测试用例自动生成模型研究在现有测试用例生成技术及遗传算法基本原理的基础上,本文介绍了基于遗传算法的分支覆盖测试用例自动生成模型,重点研究了系统模型中的参数编码,及其选择、交叉、变异等操作的实现。此外,针对“生成分支覆盖测试用例”这一具体问题,对适值函数、遗传算子等操作做了改进,增强了算法的实用性,,提高生成效率。 3.用C#语言实现了基于遗传算法的分支覆盖测试用例生成算法,并对结果进行了分析

关键词：测试用例遗传算法分支覆盖路径覆盖

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于模糊测试的缓冲区溢出漏洞检测研究

基于模糊测试的缓冲区溢出漏洞检测研究

作者：陈诚昆明理工大学

学位级别：硕士

当前软件漏洞问题日益严重,恶意攻击者最常使用的手法就是利用缓冲区溢出(Buffer Overflow,BOF)漏洞对目标程序进行攻击,所以对BOF漏洞的检测研究意义重大。使用模糊测试技术进行BOF漏洞检测是最有效的手段之一,但目前主要存在两个问题... 详细信息

当前软件漏洞问题日益严重,恶意攻击者最常使用的手法就是利用缓冲区溢出(Buffer Overflow,BOF)漏洞对目标程序进行攻击,所以对BOF漏洞的检测研究意义重大。使用模糊测试技术进行BOF漏洞检测是最有效的手段之一,但目前主要存在两个问题:一是由模糊测试生成的样本的针对性和有效性差;二是样本对待测软件中可能导致BOF的代码覆盖率低。本论文针对这两个问题进行研究:针对问题一,首先结合静态分析根据BOF漏洞的攻击方式,将不触发BOF的样本归为无效样本并删除,在不降低样本能覆盖的基本块的情况下根据基于动态规划的改进算法删减样本;然后结合动态污点分析(Dynamic Taint Analysis,DTA)技术跟踪测试样本的传播路径,得到程序异常位置、触发异常的样本和样本的传播指令序列,计算多个样本的传播路径相似度,若高于阀值则只保留其中一个样本,删除其他样本;最后根据本文提出的基于遗传算法(Genetic Algorithm,GA)构造新样本的算法,针对已触发程序异常的样本,通过遗传变异操作,构造新的样本。针对问题二,首先对经典BOF漏洞的出现错误的原因进行详细分析;然后对待测程序进行反汇编,利用本文提出的算法判断函数是否满足BOF漏洞存在条件,收集满足条件的函数中的BOF漏洞的脆弱点,得出目标程序中BOF漏洞的脆弱点集;最后结合符号执行技术提出一种基于禁忌搜索(Tabu Search,TS)的改进算法,将遍历过的脆弱点存入禁忌表中,避免重复探测同一路径同时避免陷入循环搜索,由此遍历目标程序中BOF漏洞的脆弱点集,生成脆弱点的路径约束,指导生成测试样本对软件进行测试。最后由实验得出:针对问题一,本论文提出的方法有效减小了测试样本规模,并且提高了样本的针对性;针对问题二,本论文提出的方法保证了对脆弱点的覆盖,提升了BOF漏洞的发现率。

关键词：缓冲区溢出漏洞模糊测试测试样本脆弱点路径覆盖

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于概率模型的模糊测试种子生成与优化

基于概率模型的模糊测试种子生成与优化

作者：邬骁杰华中科技大学

学位级别：硕士

开源软件的不断发展导致了软件漏洞的数量呈现上升趋势,因此软件漏洞自动挖掘技术也得到了越来越多研究者的关注。模糊测试技术一种自动化的软件测试技术,因其具有自动化程度高的特点被广泛用于漏洞挖掘的领域。随着程序代码量的不断增... 详细信息

开源软件的不断发展导致了软件漏洞的数量呈现上升趋势,因此软件漏洞自动挖掘技术也得到了越来越多研究者的关注。模糊测试技术一种自动化的软件测试技术,因其具有自动化程度高的特点被广泛用于漏洞挖掘的领域。随着程序代码量的不断增长,传统的模糊测试的方法的问题也渐渐显露,比如生成的测试用例种子的随机变异,导致种子的有效性不高,难以覆盖到全部的路径。测试时不能完成利用程序的反馈信息,导致生成的用例不够有代表性。如果在模糊测试中引入智能的方法,产生有效的测试用例,便可以提升代码的覆盖率进而提升模糊测试的性能。提出一种新的种子生成的方法进行模糊测试,利用代码语言概率模型与模糊测试相结合,利用概率模型和覆盖率的反馈进行指导生成测试用例。具体来说,从大量代码数据中构建出代码语言概率模型,利用概率模型来指导测试用例的生成。利用路径覆盖的反馈信息,目的是使模糊测试向提高路径覆盖的方向发展。通过这两种方式的结合指导,设计出合理的种子变异淘汰策略,利用这种方法进而构建出语法有效并具有语义多样性的种子,从而对模糊测试性能进行优化。基于概率模型的模糊测试种子生成的方法设计了一个模糊测试系统LMFuzzer,设计对比实验对软件Closure和Rhino进行测试,与Zest和Rlcheck方法在种子有效性,路径覆盖总数和单位时间产生异常的个数指标上进行对比。实验结果表明,LMFuzzer能够对种子的有效性进行提升,路径覆盖分支总数提高了12%～31%,在单位时间产生的异常也有明显的增加。

关键词：模糊测试种子生成语言模型路径覆盖

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

点集覆盖问题的计算复杂性与参数算法研究

点集覆盖问题的计算复杂性与参数算法研究

作者：姚金毅中南大学

学位级别：硕士

点集覆盖问题是计算几何领域的一类基本问题,其中包括了直线覆盖、路径覆盖、回路覆盖等问题。此类问题的研究不仅具有重大的理论意义,而且在电路设计、重型器械移动、路径规划等领域有着重大的应用价值。本文分别从计算复杂性和固定参... 详细信息

点集覆盖问题是计算几何领域的一类基本问题,其中包括了直线覆盖、路径覆盖、回路覆盖等问题。此类问题的研究不仅具有重大的理论意义,而且在电路设计、重型器械移动、路径规划等领域有着重大的应用价值。本文分别从计算复杂性和固定参数算法的角度,着重研究了此类问题中的直角路径覆盖问题和直角回路覆盖问题。从计算复杂性的角度,本文研究了直角路径覆盖问题在二维平面上的NP复杂性。本文通过受限二分图顶点覆盖问题到二维平面上的直角路径覆盖问题的多项式时间规约,证明了二维平面上的直角路径覆盖问题是NP-完全问题。利用类似的方法,本文也证明了二维平面上的直角回路覆盖问题是NP-完全问题。以上证明解决了这两个问题在二维平面上是否为NP-完全问题的开放问题,完善了这两个问题的计算复杂性研究。从参数计算理论的角度,本文研究了直角路径覆盖问题的一种简化形式：受限直角路径覆盖问题。本文利用核心化技术分析了该问题的结构特征,提出了三条规约规则,在O（n2）时间内获得了该问题一个大小为O（k2）的核。通过运用分支搜索和动态规划技术,本文提出了一个时间复杂度为O（dk+12kk2+dkn）的固定参数算法,极大地改进了当时最好的结果O(（0.74dk）k（kd+n）（?k）,并且是该问题第一个复杂度形如O*(2O（k）的算法。在d=2时,本文通过进一步优化分支搜索的策略,提出了时间复杂度为O（3.24kk2+1.62kn）的固定参数算法。同时,本文论证了这两个算法通过修改也能适用于受限直角回路覆盖问题。最后,本文通过实验分析了以上提出的改进算法的实际运行效率,证明了以上改进算法能有效的解决一部分实际问题。

关键词：路径覆盖回路覆盖固定参数算法 NP-完全计算几何