超时的随机算法

Question

我有一个随机递归回溯算法来生成数独（请参见这里）。平均而言，它的速度足够快，但最坏情况下的运行时间过长。以下是100次试验中运行时间的毫秒数的直方图（"More"大约为200,000ms！）：

我想通过简单地在 ms后超时并使用新的随机种子重新启动来改进算法。为了防止无限重复，我将在n次尝试后停止，或在每次失败尝试后增加。如果远大于中位数，则有很大的机会在随后的尝试中获得更快的运行。

问题：

1. 如何调整不同处理器的超时期？是否有一种快速可靠的方法来在每次运行之前对处理器性能进行基准测试？或者，我应该适应处理器，在此过程中使用所有先前运行的平均运行时间？我在Android上运行此操作，如果相关的话。
2. 是否存在更好的策略以避免运行时间分布中的长尾巴？

- 1''

Answer 1

既然您的算法是递归的，为什么不设定最大递归深度呢？如果特定的随机种子导致递归深度超过了您经验上确定的足够高的阈值，那么在那一点上中止。

通过视觉近似，看起来在4500毫秒后，对于给定的种子，您将不会获得显著的回报。重新运行该基准测试并跟踪递归深度，看看该数字是多少。我建议运行超过100个样本。

这种解决方案与CPU速度无关。

- Eric J.

---

对于我的回溯算法来说，递归深度并不是问题（始终为81，即谜题中的单元格数），而是递归广度：在做出决策之前必须覆盖多少可能解的搜索树。我已经在帖子的顶部链接了我的算法描述。 - 1''

当然可以追踪当前的宽度（或类似的步数计量指标），并应用类似的逻辑，不是吗？ - Eric J.

这是一个有趣的想法，但有效地实现不会很难吗？我可能要遍历数十万个级别，每一步都增加计数器可能会非常缓慢。 - 1''

尝试对计数器进行10万次递增的基准测试。与您最佳的运行时间500毫秒相比，这将是一个非常小的值。 - Eric J.

Answer 2

1.

是的，有一个叫做置信区间的方法。通过在预处理（或实时）中多次运行算法，您可以确定在x%的置信度下（其中x是参数），运行时间中位数所在的区间。
您可以通过减小x或增加算法运行次数来缩小区间大小。

当然，如果您无法真正运行算法本身，可以尝试在某台机器上对其进行基准测试并找到置信区间（设为I），并创建一些函数f(I,s)，给定不同机器（M）上不同算法的计时（其计时为s），预测机器M的区间应该是什么。
使用置信区间以类似的方式来找到s。

2.

您的方法看起来很好，我可能会做同样的事情 - 我将首先设置一个小因子，并在每次失败尝试后增加它。请注意，这与TCP协议中的拥塞控制（来自网络领域）有些相似，用于找到在网络上传输数据包的接受速率。

- amit

---

感谢提供TCP的链接！我可以使用置信区间的中间值，或者只是取样本均值或（可能不太准确的）中位数，但我主要关心的是一种可靠的方法来对处理器进行基准测试。 - 1''

使用一些其他算法（具有“确定性”运行时间）并重复使用置信区间方法，您可以比较不同处理器之间的差异，并估计您的算法的中位数。 - amit