我有一组测试用例，我想找到运行它们的最佳顺序。顺序约束是:
- 困难:一个测试用例
A可以产生另一个测试用例B所需的输出，因此A必须在B之前处理
- 软:测试用例可以从另一个继承输入数据。如果父测试用例失败，几乎可以肯定子测试用例也会以同样的方式失败。为了更容易进行故障诊断，我们希望先运行父级，这样当我们运行子级时，我们可以查看过去的结果，如果父级失败则跳过子级。即:如果测试用例
B继承自A，则 nice(但绝不是必要的)如果A在B 之前处理
如果我们有这些约束集中的任一个，我们就可以做一个topographical sort并完成它，但将两者结合起来似乎会使事情变得更加棘手，因为它们可能相互矛盾。
我可以看到两种可能的解决方案:
双重排名
给每个项目 2 个等级:项目在硬约束树和软约束树中的深度。然后我们可以根据这些等级排序 - 排序优先级给硬约束等级，当硬约束等级相等时比较软约束等级。
这肯定会给我们一个有效的命令，但我们最终可能会遇到很多不必要的破坏软约束。例如，考虑项目 A、B、C 和 D，其中:
A必须在B之前
C必须在D 之前
- 如果
B在C之前出现就很好
硬约束排序 (A:1,B:2,C:1,D:2) 意味着 C 和 B 之间的硬约束 实际上并不存在，当我们更喜欢 A,B,C,D 时，我们最终得到 A,C,B,D/p>
约束遍历
根据项目S 的集合构建订单列表L:
- 从
S中删除任意项目A - 递归地添加
A的所有尚未在L中的硬约束前辈，并将它们从S中删除 - 递归地添加仍在
S中的A的所有软约束前辈，将它们从S中移除 - 将
A添加到L - 重复直到
S为空。
我认为这会产生一个有效的命令，只在必要时打破软约束(它当然适用于上面的例子)，但我不相信我们不能做得更好。
问题
是否有一种可接受的方法来解决找到完全满足一组约束同时最大化另一组约束的项目排序的问题？
最佳答案
基于硬约束的拓扑排序，程序如下:http://rosettacode.org/wiki/Topological_sort#Python ，它输出可以按任何顺序应用的项目。
应用任何软约束，这些软约束仅在硬约束排序后具有相同优先级的项目之间排序，以拆分为子订单。
关于algorithm - 具有矛盾约束的项目的最佳排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50946299/