单元测试复杂的算法

Question

您如何编写测试来测试一些相当复杂的算法(如N Queens问题)的解决方案？我的意思是什么应该是测试算法的正确方法

1. 有很多解决方案(你不知道/不关心它们中有多少存在),

2. 你只能拥有所有可能解决方案的一小部分,并且

3. 验证解决方案是否正确可能有点棘手(可能与算法本身的复杂程度相当).

我知道N-Queens问题本身并不存在这些条件,但我提到它提供了一个例子.

Answer 1

在您的示例中,我认为您要对要验证建议解决方案的算法进行单元测试.

您想要涵盖以下情况:

• 快乐路径测试验证算法接受各种正确的解决方案
• 快乐路径测试验证算法拒绝各种不正确的解决方案
• 悲伤路径测试以确保算法正确处理非候选者(例如,具有7个皇后而不是8个等的"解决方案")

在这里,"多样化"意味着您希望解决方案涵盖可能性的空间.但覆盖该空间意味着什么是特定问题.我不熟悉N-queens问题,知道正确的解决方案中存在哪种变体,但是如果我实现测试,那么这些信息将是有用的.对于不正确的解决方案,您需要一些涉及相同的排名,相同的文件,相同的对角线和混合.一些涉及沿着板边缘的曝光,一些涉及从边缘曝光.等等.

此外,如果您有关于解决方案分布的信息,您可能会优先考虑那些更有可能的解决方案,但最终您甚至想要涵盖那些不太可能的解决方案,因为这些解决方案往往会破坏实际情况.生活.

此外,如果算法很复杂,那么将它分解成部分并以相同的方式测试这些部分的正确性是有意义的(区分快乐与悲伤路径,并测试两种类型的输入).

Answer 2

在测试复杂算法时,您需要依赖需要验证的"数据".假设您已经有某种形式的解决方案(数据)问题.您只需获取数据并让算法运行并查看答案是否匹配.以使用算法求解n-puzzle为例,它是非确定性的,但您有一个数据来验证解决方案.

Answer 3

我认为这是一个非常好的问题,没有灵丹妙药.我会告诉你我的经历.

我写了一个算法来找到3D空间中两个圆柱之间最近的点集.这是一个非常复杂的问题,输入空间很大.

为了测试我的代码,起初我只生成了一些规范的情况,它们是相当轴对齐的,因此"正确"的结果是显而易见的.但那太弱了.

然后,我能够通过应用随机变换来"加强"规范案例.这有点帮助.

然后我考虑编写另一个重复的算法和实现,但这非常困难,并且无法知道两个算法是否可能会出现相同的错误.但是,对于另一个问题,这可能是可行的,例如使用暴力:效率不高,但理解和验证非常简单.

然后我想到了解决方案集的属性.例如,分离向量必须是局部最小值,因此我应该能够"环顾"解决方案的每个终点(对于小ε)并确定解是否是局部最小值.

然后我开始考虑将输入映射到输出的函数的拓扑属性.在这种情况下,我知道间隔距离应该平滑变化.所以我选择了一个随机输入和小三角洲,然后在应用和不应用delta的情况下比较输出.如果算法正确,那么输出的差异应该很小.

通过结合所有这些技术,我能够对代码充满信心.