问题标签 [non-deterministic]

我们有一个需要确定性的大而复杂的函数。它是我们公司的主力之一，涵盖了大量的代码。由于 python 的 dict 迭代器，此代码通常变得不确定。这种情况发生了很多次，很难追查到，而且往往不会立即注意到。我们想编写一个自动化测试来检测非确定性，但我不知道该怎么做。

我们尝试在循环中运行该函数，并且测试结果始终相同，但有时，即使该函数是非确定性的，由于 dict 迭代器的任意但有些一致的顺序，该函数也会通​​过此测试。

有没有办法编写一个自动化测试来捕捉这种错误？

也许有一种方法可以破解 python 的 dict 以便在此测试期间迭代器是随机的而不是任意的？这样重复调用函数就更有可能发散？这似乎是一个相当复杂的方法，但我想不出任何其他方法。

编辑：

我们目前使用的是 Python 2.7。

我们对各种子模块进行了单元测试，但是由于 dict 顺序的任意但一致的性质，它们通常不会暴露不确定性。

此外，也许非确定性不是描述这个问题的正确方法。这个函数需要 {id : data}，但是 ids 的值不应该影响代码的结果，但是由于 python dict 排序，它有时会。也许最好的测试方法是用随机值替换 id 并检查在多次运行不同 id 后输出是否相同。

我刚刚克服了弄清楚如何使用 List monad 进行非确定性计算的困难。但是，我相信我的算法将受益于广度优先搜索，而不是从 List monad 获得的深度优先搜索。

这是一段摘录，展示了我的算法中有趣的部分。它是逻辑谜题 Akari 的求解器。

基本上它应用一些基本的确定性规则来查看是否可以解决它。如果不是，它会尝试在不同的地方放灯。如果灯光在递归解决后使谜题不一致，则会在灯光所在和继续进行的位置放置一个排除标记。如果它在放置灯时找到了解决方案，那么它将这些解决方案添加到解决方案列表中。

这工作正常，但速度很慢，因为通常有一个明显的选择来推测哪个坐标会很快导致不一致的谜题，并让您放置一个只有一个（或两个）搜索级别的 x，但如果它没有直到搜索到一半才选择该坐标，然后它会首先咀嚼一堆无趣的东西。因此，广度优先搜索的想法。

我用谷歌搜索了诸如“广度优先非确定性单子”之类的东西，得到了一些我难以理解的结果，例如：

• Control.Monad.Omega这对我需要的东西来说似乎有点矫枉过正，因为它似乎可以防止无限发散的确定性，这对我来说不是这样，而且我并不完全理解它。

• Control.Monad.WeightedSearch Control.Monad.Omega 的文档建议在将其用作 Monad 时使用它，但我认为加权对于我的需求来说也有点矫枉过正。我可能只有 2 个权重，一个用于有解决方案的东西，一个用于没有解决方案的东西。

• Control.Monad.Level我不相信这会为我想要的，因为只有树的叶子有值。

• Data.Tree我认为这可能是我想要使用的，但我不确定如何将我的 List monadic 代码转换为使用它，尽管我觉得有一种很好的方式。

我的下一个问题是关于如何并行化它:)

我是 NDTM 的新手，但我确实了解图灵机的概念。说到 NDTM，我有点困惑，我应该为语言 {a,b,c} 开发一个 NDTM 和

我想知道的第一件事是如何阅读L，例如Ǝ的含义是什么。我确实理解 NDTM 提供了一种结果的 twp 可能性，例如 a：如果我是正确的，我们将有 a 和没有 a，有人可以帮我解决这个问题吗？

多年来，我一直很高兴地使用基于卡尺的模板https://github.com/dcsobral/scala-foreach-benchmark。它多次运行随机构造的问题，然后计算平均时间消耗。

现在我面临着非确定性算法。所以我需要知道跑步时间和由此产生的健康状况。我正在寻找一个 java/scala 基准框架，它可以测量平均和最坏情况下的特征。

非确定性意味着算法依赖于一些随机生成器来做出决定。它曾经找到一个接近最优的解决方案，在这种解决方案中搜索最优将需要太多的处理器时间。例如 TSP 问题的解决方案。

适应度意味着优化过程的成本函数。不同的运行（使用不同的随机种子）可能会带来不同的成本。因此，您不仅需要稳定运行时间，还需要稳定成本价值（适应度）。

我不知道在显示可接受的运行时间变化之前重复调用一个函数是否是基准框架的共同特征，但是卡尺这样做，我搜索了一个类似的框架，它更先进，能够处理除时间之外的适应度。

我读过NP问题在多项式时间内是可验证的，或者等效地，可以通过非确定性图灵机在多项式时间内解决。为什么这些定义是等价的？

我正在实现的搜索算法（一个简单的偏序规划器）在每次调用时只有几个选择。理想情况下，我希望它回溯可能性并返回第一个找到的解决方案。

考虑以下 Haskell 代码：

这会产生以下输出：

但是，我想生成以下输出：

用 JavaScript 这样的不纯语言很容易做到这一点：

你如何在 Haskell 中做同样的事情？

有没有办法在 muZ3 关系规范中不确定地执行递归调用？具体来说，我想翻译如下函数：

到 muZ3 规则格式。

寻找调试随机程序的一般原则，以及在 Python 中执行此操作的任何具体指南。

例如，考虑以下在跳过列表中的插入实现：

这insert取决于随机掷硬币。因此，该函数中的错误变得难以检测，因为它可能会或可能不会出现在每次运行中。在这种情况下，我们如何简化调试？

我正在开发一个必须为用户提供包含加密查询参数的链接的 Groovy 应用程序。目前我们使用 AES 加密算法，所有链接都使用相同的 IV。我们知道这很糟糕（因此我们想要切换），但这样做的原因是为了限制查询参数的大小（包括每个查询参数的 base64 编码的 16 字节初始化向量使链接很长）。我们想切换到非确定性算法，以便我们在查询数据中具有所需的随机性，但不必将 IV 存储在查询参数中。

由于我们使用的是 Groovy，我们可以使用 Java 中的任何东西。尽管我不确定要开始研究哪种算法，但还没有做太多的加密工作。理想情况下，我们想要一个在 Java SE 中可用或作为可免费使用的 Java 库的库。此外，任何有关如何实现这些算法的详细信息的链接都受到高度赞赏。