arXiv:2504.05874v1 通知类型: 新 摘要: 本文提出了一种新颖的方法来确定基于哈希的近似模型计数算法 $\mathsf{ApproxMC}$ 的内部参数。在这个问题中，所选择的参数值必须确保 $\mathsf{ApproxMC}$ 是几乎正确的（Probably Approximately Correct, PAC），同时也要使其尽可能高效。现存的方法依赖于启发式方法；而本文则通过将 $\mathsf{ApproxMC}$ 的正确性证明推广到任意参数值来将其形式化为一个优化问题，从而解决了这个问题。我们的方法将算法的正确性和最优性问题分离，使我们能够在不需要重复的案例论证的情况下解决前者，同时为后者提供了一个清晰的框架。此外，在简化后，形成的优化问题具有异常简单的形式，使得基本的搜索算法得以使用，并有助于理解参数值如何影响算法性能。实验结果表明，我们的优化参数可以将最新 $\mathsf{ApproxMC}$ 的运行时间性能提高1.6到2.4倍，具体取决于容许的误差范围。