白盒测试中的路径覆盖法

所谓的路径覆盖法是指在测试时设计若干个测试用例，然后运行被测程序，要求覆盖程序中所有可能的路径；

有如下被测试程序的流程图：

按照路径覆盖法的要求可以设计如下测试用例，将程序的所有分支路径都给覆盖到：

另外路径覆盖的困难如下：

上图中包含的不同执行路径数达5的20次方条路径，假定对每一条路径进行测试需要1毫秒，一年工作365 × 24小时，要想把所有路径测试完，需3170年。

测试中做到完全的路径覆盖是无法实现的，为解决这一难题只得把覆盖的路径数压缩到一定限度内。

我的算法:

我采用贪心的算法,

按照左端点排序,

建立一个以线段右端点为关键字的大根堆.

依次尝试插入线段,

对于当前的一个线段,

如果能够覆盖,显然我们选择覆盖,

而如果不能覆盖,

我们进行一下讨论.

首先我们需要知道

(1)

如果线段发生相交,

那么只可能是两条线段相交:

理由:

对于前面的所有线段,贪心法保证,也显然,已经满足两两不相交了,

那么如果当前的线段,和另外两条线段相交,

则必然将一条线段包含,

而我们按照线段左端点排序,

按次序尝试覆盖,

因此这种情况是不存在的.

那么我们假设当前的线段是

[L0,

R0]

发生相交的线段是

[L1,

R1]

即有

L0

>=

L1

R0

<=

R1

这两条线段是不能共存的.

显然,我们要从中留下一个而舍去一个,

舍去哪个呢?

就应该选择右端点小的那个!

为什么?

因为右端点越靠左,对后面的线段的覆盖产生的影响(就是发生覆盖的机会)就越小!

很直观的,

我们可以知道这种贪心法的正确性.

问题就解决了

时间复杂度

O(N

log

N)

我写的代码:

#include<cstdio>

#include<vector>

#include<queue>

#include<algorithm>

using

namespace

std

const

int

maxn

=

10010

struct

event

{

int

l,

r

}e[maxn]

struct

__Comp

{

inline

int

operator()

(const

event

&a,

const

event

&b)

const

{

return

a.r

<

b.r

}

}

priority_queue<event,

vector<event>,

__Comp>

hp

int

n,

l,

r

inline

int

comp(const

event

&a,

const

event

&b)

{return

a.l

<

b.l}

int

main()

{

scanf("%d",

&n)

for

(int

i=0i<n++i)

{

scanf("%d

%d",

&l,

&r)

e[i]

=

(event){l<?r,

l>?r}

}sort(e,

e+n,

comp)

for

(int

i=0i<n++i)

{

if

(!i)

{hp.push(e[0])

continue}

if

(e[i].l

>=

hp.top().r)

hp.push(e[i])

else

if

(hp.top().r

>

e[i].r)

{

hp.pop()

hp.push(e[i])

}

}

printf("%d\n",

hp.size())

scanf("%*s")

}

---