我有一个随机递归回溯算法来生成数独游戏(参见 here )。它平均运行速度足够快，但最坏情况下的运行时间慢得令人无法接受。这是 100 次试验的运行时间直方图(以毫秒为单位)(“更多”约为 200,000 毫秒!):
我想通过简单地在 t 毫秒后将其超时并使用新的随机种子重新启动来改进算法。为了防止这种情况无限重复，我会在 n 次尝试后停止，或者在每次失败的尝试后增加 t。如果 t 远大于中位数，则很有可能在后续尝试中获得更快的运行速度。
问题:
- 如何调整不同处理器的超时时间t？是否有一种快速、可靠的方法来在每次运行之前对处理器性能进行基准测试？或者，我是否应该在多次运行中适应处理器，例如使用所有先前运行的平均运行时间？如果相关的话，我正在 Android 上运行它。
- 是否有更好的策略来完全避免运行时分布中的长尾现象？
最佳答案
既然你的算法是递归的，为什么不建立一个最大递归深度呢？如果特定的随机种子导致您根据经验确定的递归深度足够高，您将击中长尾，则在该点中止。
通过视觉近似，看起来在 4500 毫秒后，您不会从给定种子的投资中获得可观的返回。重新运行该基准测试并跟踪递归深度，并查看该数字是多少。不过，我会运行 100 多个样本。
该解决方案与 CPU 速度无关。
关于algorithm - 超时随机算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14267619/