4

我有一个随机递归回溯算法来生成数独谜题（见这里）。它的平均工作速度足够快，但最坏情况下的运行时间慢得令人无法接受。这是 100 次试验的运行时间直方图（以毫秒为单位）（“更多”约为 200,000 毫秒！）：

在此处输入图像描述

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

问题：

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

2 回答 2

2

既然你的算法是递归的，为什么不建立一个最大递归深度呢？如果特定的随机种子导致您根据经验确定的递归深度足够高，以至于您将击中长尾，则在该点中止。

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

该解决方案与 CPU 速度无关。

于 2013-01-10T21:36:21.923 回答
1

  1. 是的，它被称为置信区间。通过在预处理中（或在运行中）多次运行算法，您可以用 x% 置信度（x参数在哪里）确定运行时间中位数所在的 区间
    。您可以通过以下方式减小区间大小减少x或增加算法运行的次数。

    当然，如果你不能真正运行算法本身，你可以尝试在某台机器上对其进行基准测试并找到置信区间（让它成为I），并创建一些f(I,s)给定不同算法时序的函数（它的时序是 s ) 在不同的机器 (M) 上，预测机器 M 的间隔应该是多少。
    s以类似的方式进行查找- 使用置信区间。

  2. 您的方法似乎很好，我可能也会这样做 - 我将首先设置一个小因素，并在每次尝试失败后增加它。请注意，这在某种程度上类似于TCP 协议中的拥塞控制（来自网络领域），以查找网络上可接受的包传输速率。

于 2013-01-10T21:41:42.933 回答