问题标签 [non-deterministic]

我有一个项目，我已经工作了几天，我终于把它编译干净了。但是，同一远程分支的 git clone（在同一台机器上，在同一终端实例中编译）导致编译错误。另一台机器上的新克隆有同样的错误。我认为这是我的工作目录有一些额外的未跟踪文件的问题，但我删除了所有未跟踪的文件，以至于diff除了 .git 文件夹中包含的内容之外，这些目录是相同的。我什至检查了权限tree并将生成的文件与它们进行了比较meld——它们基本上是相同的，尽管一些源文件的执行权限略有不同。

该错误来自我在 maven-compiler-plugin 中排除的文件。这本质上应该意味着文件名永远不会传递给 javac，尽管我不知道它到底是如何工作的。我意识到如果编译器内部的代码出错，编译器显然会从某个地方获取文件。在我的计算机上可以运行的一个目录中，没有错误并且可以完美编译。在 repo 的其他克隆上（根据 ，它们再次相同diff），它在这个（排除的）文件上给出了一个错误。

额外的实验表明，在git clone远程分支、cp -R本地目录或本地目录的新分支git clone上，编译失败。但是，如果我使用该--archive选项执行 cp，则结果目录中的编译成功。我将其缩小到--preserve=timestamps标志（由于与--archive相同而启用-dR --preserve=all）。如果你没听清楚，我会再说一遍。

当我正常复制目录时，它拒绝正确编译。只有当时间戳被保留时，它的行为才会与原始目录相同。

我不明白这一点 - 为什么 java 编译器（或 maven）关心时间戳？

这是一个关于浮点运算的跨平台一致性和确定性的问题（IE 在不同的 CPU/系统上产生不同的结果）

哪一个更有可能保持跨平台一致（伪代码）：

或者

平台是 C# 和 AS3。

.

AS3 版本：

- 好的，我添加了 AS3 版本以进行澄清，相当于上面的“C 伪代码”。正如您在 AS3 中看到的，所有计算，即使是整数，都会自动作为浮点数执行，不需要强制转换（也不能避免它或强制运行时执行真正的整数除法）希望这可以解释为什么我“强制转换”所有内容成花车：我不是！这只是在一种目标语言中发生的事情！

根据维基百科 GLR 的描述，它们“处理非确定性和模棱两可的语法”。 我可以想象一个模棱两可的语法，就像悬空的 else 问题一样，但是什么是不模棱两可的非确定性 CF 语法？

我不了解非确定性图灵机的概念。我想我理解术语非确定性算法：（非确定性算法是一种算法，它可以在不同的运行中表现出不同的行为，而不是确定性算法。）所以算法可能像：

但是对于我读过的非确定性图灵机，它在给定时间可以处于多个状态。还有一篇维基百科文章建议“非确定性图灵机 (NTM)，可能有一组规则，为给定情况规定了多个动作”。

这意味着什么 ？..针对给定情况的不止一个动作...多个状态...我根本不明白这一点。

嗨，我需要一个非确定性约束满足问题工具，因为我需要具有相同问题输入的不同解决方案。有人知道具有这种特性的工具吗？

我只知道像 Gecode (c++)、Choco (Java) 和 Curry (Haskell) 这样的工具，我认为它们以确定性的方式工作。

我想在 Haskell 中建立一个不确定的状态单子。这将允许我使用构建状态生成搜索空间中的所有元素以修剪不良位置。假设我有以下（伪）代码：

这里有几件事是行不通的：我需要了解的最基本的事情是如何做一些事情来陈述，然后将它传递到每个expand分支。我已经尝试了很多使用类型函数的方法，State Int [ State Int Element]但最终，一旦我将 list monad 的分支包装在状态包装器中，我就无法删除它，对吧？那么有没有办法做到这一点？

谢谢。

我想在 haskell 中构建一个不确定的 monad 转换器，我相信它的行为与 ListT 和http://www.haskell.org/haskellwiki/ListT_done_right提出的替代 ListT 不同。其中第一个将 monad 与项目列表相关联；第二个将 monad 与单个项目相关联，但具有给定元素中的 monadic 动作影响列表后续槽中的 monadic 元素的属性。目标是建立一个单子变压器的形式

这样列表中的每个元素都有自己的 monad 与之关联，并且连续的元素具有独立的 monad。在这篇文章的最后，我稍微演示了这个 monad 应该给出的那种行为。如果您知道如何获得 ListT 的一些变体来提供这种行为，那也会很有帮助。

下面是我的尝试。它不完整，因为unpack函数未定义。我该如何定义它？这是定义它的一次不完整的尝试，但它没有处理 monad m 包含EmptyAmb 列表的情况：

完整（不完整）代码：

期望行为示例

在这里，基本单子是State Int

谢谢。

更新：为什么 LogicT 不做我想做的事的一个例子。

这是 LogicT 在上面的简单示例中所做的：

我用 Java 制作了一个遗传算法，它是一个库的形式，可以添加到多个应用程序中。在开发过程中，我做了一些可能是功能测试的（jUnit）测试，但它们没有断言，因为算法是不确定的。所以，它们不适合自动测试，当运行一段时间后你必须花时间看看解决方案。

解决方案是车辆路线，可以打印为 XLS 格式，并在必要时进行实际测试，因此您知道在那一刻要寻找什么。它们有一个距离值和一个时间值，每个示例都有一个合理的值，以及路线本身，不能有某些锯齿形，尽管有时必须有锯齿形。

我可以断言这些值在那个合理的范围内，但这些并不清楚，我不确定我不会陷入糟糕的解决方案。很高兴知道人们在做什么，或者您对此事有何看法。

编辑：澄清目标：

• 单元测试已经解决了。我可以将随机数生成代码与不同函数中的逻辑代码隔离开来，并且我测试逻辑函数，将它们从测试代码中传递给非随机数。
• 我想进行一些功能测试，比如 Cucumber 或 Selenium 测试，没有虚假数据。产生真实输出的真实输入。（我并不是说我想专门使用 Cucumber 或 Selenium，只是说我要求的不是单元测试，并且算法的行为必须是真实的，并且不能以任何方式伪造）

该库用于不同的项目，每个项目的输入数据遵循相同的模型，但偏向不同。一个项目数据可以有很多相同点的重复，而另一个项目则没有。可以让车辆非常快地达到极限容量，而在其他情况下，这个极限几乎无法达到。

目标是从插入的每个项目中获取样本数据，以便在修改算法时快速反馈算法的行为（例如修改或添加变异或交叉运算符，或添加新的参数化）。因此，不得以任何方式伪造其行为。

鉴于这一切，我要问的问题是找到一种方法来对整个行为做出有效的断言。我想问一下其他人是如何处理这个问题的，或者你们对此有什么看法。

我试图找出在三种情况下接受重复字符串（ww）的图灵机的时间复杂度：1 磁带确定性机器、2 磁带确定性机器和 1 磁带非确定性机器。

现在我的想法是

• 1-tape 确定性机器需要 O(n^2) 来找到中点（通过重复删除输入中的第一个和最后一个符号）和 O(n^2) 来比较前半部分和后半部分（因为它必须来回 n/2 次，每次通过 n/2 的字符串），

• 2-tape TM 需要 O(n^2) 找到中点，O(n) 将后半部分复制到第二个磁带，然后 O(n) 同时比较两半，

• 而不确定的人猜测中点并取 O(n^2) 来比较两半。

但是，我觉得这三种情况不应该都具有相同的 O(n^2) 时间复杂度，所以想知道我的推理是否在某个地方不正确（或者我是否正确并且只是在思考这个问题）。任何输入将不胜感激！

我已经阅读了很多关于 .NET 中浮点确定性的内容，即确保具有相同输入的相同代码在不同的机器上给出相同的结果。由于 .NET 缺少 Java 的 fpstrict 和 MSVC 的 fp:strict 之类的选项，因此一致认为使用纯托管代码无法解决此问题。C# 游戏 AI Wars 已决定使用定点数学，但这是一个繁琐的解决方案。

主要问题似乎是 CLR 允许中间结果存在于精度高于类型的本机精度的 FPU 寄存器中，从而导致无法预测的高精度结果。CLR 工程师 David Notario的MSDN 文章解释了以下内容：

请注意，使用当前规范，它仍然是提供“可预测性”的语言选择。该语言可以在每个 FP 操作之后插入 conv.r4 或 conv.r8 指令以获得“可预测”的行为。 显然，这确实很昂贵，而且不同的语言有不同的折衷方案。例如，C# 什么都不做，如果你想缩小，你将不得不手动插入 (float) 和 (double) 强制转换。

这表明可以通过为每个表达式和计算结果为 float 的子表达式插入显式强制转换来实现浮点确定性。有人可能会围绕 float 编写一个包装器类型来自动执行此任务。这将是一个简单而理想的解决方案！

然而，其他评论表明它并不那么简单。Eric Lippert 最近表示（强调我的）：

在运行时的某些版本中，显式转换为浮动会产生与不这样做不同的结果。当您显式转换为浮点数时，C# 编译器会提示运行时说“如果您碰巧使用此优化，请将此事物退出超高精度模式”。

这个运行时的“提示”是什么？C# 规范是否规定显式强制转换为浮点数会导致在 IL 中插入 conv.r4？CLR 规范是否规定 conv.r4 指令会导致将值缩小到其本机大小？只有当这两个都为真时，我们才能依靠显式转换来提供浮点“可预测性”，正如 David Notario 所解释的那样。

最后，即使我们确实可以将所有中间结果强制转换为类型的原生大小，这是否足以保证跨机器的可重复性，或者是否还有其他因素，例如 FPU/SSE 运行时设置？