练习：测试最小化和优先化
我们将使用以下场景。 让我们假设被测试的程序 p 有十个分支，表示为 b1 … b10。 此外，假设有一个包含六个测试用例 t1…t6 的回归测试套件 T，这样：
• t1 的执行会覆盖以下分支：b1、b3、b7。
• t2 的执行会覆盖以下分支：b2、b5、b7。
• t3 的执行会覆盖以下分支：b1、b4、b8、b10。
• 执行t4 导致覆盖以下分支：b2、b6、b9、b10。
• t5 的执行会覆盖以下分支：b2、b5、b8、b9、b10。
• t6 的执行会覆盖以下分支：b1、b4、b7。
问题 1)
针对上述场景回答以下问题。
- 将贪心算法应用于上述场景，以生成仍然达到 100% 分支覆盖率（最小化）的缩减测试套件。 如果贪婪算法可以返回多个可能的测试套件，则全部给出。
-
将额外的贪婪算法应用于上述场景以生成仍然实现 100% 分支覆盖率（最小化）的缩减测试套件。
您应该展示您的工作（即在每个步骤中，确定每个尚未选择的测试用例提供的额外覆盖范围）。 如果有不止一种可能的结果，那么给出一个就足够了。
解决方案
对于第一部分，只需找到每个测试用例覆盖的分支数就足够了。 这是：3、3、4、4、5、3。因此，有 12 种可能的顺序可以考虑测试用例。 这些可以由以下表示：
{t5} {t3t4,t4t3} {t1t2t6, t1t6t2, t2t1t6, t2t6t1, t6t1t2, t6t2t1}
现在考虑可能减少的测试套件。 对于所有订单，我们包括 t5、t3、t4。 这些涵盖所有分支，除了：b3 和 b7。 此外，b3 仅被测试用例 t1 覆盖，而 t1 也覆盖了 b7，因此一旦添加了 t1，算法就会停止。 因此，我们获得了以下可能的简化测试套件。
• {t5; t3; t4; t1}
• {t5; t3; t4; t2; t1}
• {t5; t3; t4; t6; t1}
• {t5; t3; t4; t2; t6; t1}
对于第二部分，我们从具有最大覆盖率的测试用例 t5 开始。 如果我们随后更新覆盖信息，给出测试用例覆盖的当前未覆盖分支的数量，我们得到：
• 对于 t1：b1； b3; b7.
• 对于t2：b7。
• 对于 t3：b1； b4.
• 对于t4：b6。
• 对于 t6：b1； b4; b7
现在可以选择下一个测试用例：t1 或 t6。 让我们假设我们选择了 t6，所以我们现在有订单 t5； t6。
如果我们随后更新覆盖信息，给出测试用例覆盖的当前未覆盖分支的数量，我们得到：
• 对于 t1：b3。
• 对于 t2：无
• 对于 t3：无
• 对于t4：b6。
显然现在有两种可能的顺序，但都导致相同的测试套件：
{t5; t6; t1; t4}
#####################################################
问题2）
针对上述场景回答以下问题。
- 将贪心算法应用于上述场景，为测试用例生成优先顺序。 如果贪心算法有不止一种可能的结果，则给出所有结果（如果有很多，那么您可以使用例如集合表达式来表示所有可能顺序的集合）。
- 将Additional Greedy Algorithm 应用到上述场景中，为测试用例产生一个优先顺序。 您应该展示您的工作（即在每个步骤中，确定每个尚未选择的测试用例提供的额外覆盖范围）。 如果有不止一个可能的结果，那么给出一个。
解决方案
考虑到上述工作，我们得到：
-
以下所代表的所有订单。
{t5} {t3t4,t4t3} {t1t2t6, t1t6t2, t2t1t6, t2t6t1, t6t1t2, t6t2t1} - 顺序：t5t6t1t4 和 t5t6t4t1 – 在这两种情况下，其余测试用例以任意顺序跟随。
#####################################################
问题 3)
考虑您为问题 2) 生成的订单。 给定六个测试用例的排序，我们可以查看前 n 个测试用例提供的覆盖率，其中 1 ≤ n ≤ 6。如果 Greedy 或 Additional Greedy 中的任何一个可以产生多个排序，则选择一个这样的排序作为 用于以下。
- 对于什么长度（n 的值），Greedy 和 Additional Greedy 提供的排序产生相同的分支覆盖？
- 导致覆盖率差异最大的 n 值是多少，这个差异有多大？
解决方案
对于 Greedy，请考虑以下顺序：t5t3t4t2t1t6。
前缀提供的分支覆盖范围由以下给出：
• t5：5 个分支。
• t5t3：7 个分支。
• t5t3t4：8 个分支。
• t5t3t4t2：9 个分支
• t5t3t4t2t1：10 个分支
• t5t3t4t2t1t6：10 个分支。
对于额外的贪婪，考虑：t5； t6; t1; t4（但我们知道其他顺序将为每个 n 提供相同的覆盖范围）。 前缀提供的分支覆盖范围由以下给出：
• t5：5 个分支
• t5t6：8 个分支
• t5t6t1：9 个分支
• t5t6t1t4：所有 10 个分支
在这种情况下，Additional Greedy 实现了长度为 2 到 4 的更高分支覆盖率。