我正在使用一些流行的 python 包作为基础，为图形和网络开发一个开源近似算法库。主要目标是包含针对图形和网络上的 NP 完全问题的最新近似算法。这样做的原因是 1) 我还没有看到一个很好的(现代的)综合包来涵盖这个和 2) 这将是一个很好的教学工具，用于学习 NP-Hard 优化问题的近似算法。
在构建这个库时，我使用单元测试来进行健全性检查(正如任何合适的开发人员所做的那样)。我对我的单元测试有些谨慎，因为就其本质而言，近似算法可能不会返回正确的解决方案。目前，我正在手动解决一些小实例，然后确保返回的结果与之匹配，但这是不可取的，在实现意义上也不可扩展。
单元测试近似算法的最佳方法是什么？生成随机实例并确保返回结果小于算法保证的界限？这似乎有误报(当时测试很幸运，不能保证所有实例都低于界限)。
最佳答案
您需要在此处分离两个关注点。你的近似算法的质量和这些算法实现的正确性。
测试近似算法的质量通常不适用于软件开发中使用的单元测试方法。例如，您需要生成代表问题实际大小的随机问题。您可能需要做一些数学工作来获得一些上限/下限来判断无法解决的大型实例的算法质量。或者使用具有已知或最知名解决方案的问题测试集并比较您的结果。但是在任何情况下，单元测试都不会帮助您提高近似算法的质量。这就是您在优化和数学方面的领域知识会有所帮助的地方。
实现的正确性是单元测试真正有用的地方。您可以在此处使用玩具大小的问题，并将已知结果(手动求解，或通过在代码中仔细逐步调试进行验证)与您的代码生成的结果进行比较。有小问题不仅足够而且在这里也是可取的，这样测试可以快速运行并且可以在开发周期中运行多次。这些类型的测试可确保整个算法得出正确的结果。它介于单元测试和集成测试之间，因为您将大部分代码作为黑盒进行测试。但我发现这些类型的测试在优化领域非常有用。我建议为此类测试做的一件事是通过随机数生成器的固定种子消除算法中的所有随机性。这些测试应始终以确定性方式运行，并在 100% 的时间内给出完全相同的结果。 我还建议在算法的较低级别模块中进行单元测试。隔离为图形上的弧分配权重的方法，并检查是否分配了正确的权重。隔离您的目标函数值计算函数并对其进行单元测试。你明白我的意思。
削减这两个部分的另一个问题是性能。您无法通过小玩具问题可靠地测试性能。还非常希望能够快速实现可显着降低工作算法性能的更改。一旦你有了算法的运行版本，你就可以创建更大的测试问题，你可以在其中测量性能并将其自动化为你的性能/集成测试。您可以不那么频繁地运行它们，因为它们会花费更多时间，但至少会在重构或向算法添加新功能期间及早通知您新引入的性能瓶颈
关于algorithm - 单元测试近似算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7391287/