问题标签 [non-deterministic]

确定性函数用“总是返回相同的结果集”来描述

这是什么意思？如果函数总是（无论如何）返回一个定义类型的值？如果是，那么我应该将此功能设为确定性吗？

它可以返回null（一个空集？）或INT，所以我猜它是非确定性函数

我对此感到困惑，如果我将此函数标记为确定性并且它将返回空值，那么它是未定义的行为吗？

也许我可以添加一个条件将 NULL 反转为-1，但这是自残的想法

当代码在等待某个延迟时间不确定的条件时，看起来很多人选择使用指数退避，即等待N秒，检查条件是否满足；如果不是，请等待 2N 秒，检查条件等。与检查恒定/线性增加的时间跨度相比，这有什么好处？

因此，我正在为一项关于下推自动机和无上下文语言的测试而学习，我被困在这个结构上。

除了我将在下面解释的一部分外，我让这个自动机的每一部分都完美地工作。

它需要识别的语言是：{ x#y#z#w | x, y, z, w in {0, 1}+ 其中 x ≠ w 和 y ≠ z }。

所以我遇到的问题是将 Xi 与 Wi 进行比较，因为在自动机处理 W 时，Wi 的元素是未知的，就像我设计的那样。

如果我存储 X 的内容，当需要弹出并将每个元素与 W 的元素进行比较时，它们将以相反的顺序弹出，因此认为 000111 和 111000 是相同的字符串，PDA 会拒绝，什么时候应该明确接受（它们是不同的字符串）。这只是一个例子，这也会导致其他输入被错误地分析。

如果有办法将 X 的内容以相反的顺序推入堆栈，它们将以原始形式弹出，使我能够正确比较字符串的内容。

如果有办法在正常推送后反转堆栈的内容，这也将使我得出解决方案。

任何帮助将不胜感激。谢谢。

我有以下自动机。我应该通过它了解空转换的使用。

我认为这个自动机的正则表达式如下： 0* 1* 2*

我只想知道这个自动机让我们做什么？换句话说，在这种情况下，空转换有什么用？

我在封闭联合运算定理下学习常规语言。我得到了 Q,F,q _o，但我对得到 delta δ 感到困惑。请用示例特别解释增量部分。

正在考虑在 Java 中实现非确定性有限状态机。已经检查过 easyflow和许多其他此类库，但它们提供的是确定性有限状态机。

例如。 用例。 用户处于暂停状态并且有 100 美元的账单到期，现在他可以用现金券重新填充他的帐户。如果他补充的金额使他的用户余额小于 100，那么他将继续处于暂停状态，如果他的帐户余额达到等于或超过 100 美元，那么用户将被发送到活动状态。

因此，该事件是相同的“补充”，但用户非常重视他的用户余额。所以 FSM 不是确定性的。

有没有关于如何处理这个案子的想法？

相反，第二个想法我可以使用drools之类的规则引擎来实现这种不确定的 FSM（或某种 FSM） 。

Oracle BRM似乎正在使用某种状态机。关于如何在 crm 系统中实现 ND-FSM 的任何想法。什么是最常用的库（java）。

如何使关系属性按子表主键排序？我有一个模式，其中许多表都有一个共同的父级，并且父级有一个使用这样的声明性系统的每个子级的列表

所以场景对象有一个属性children，它是一个孩子列表。这很好用，只是列表中子对象的顺序是任意的。这对于应用程序的语义来说很好，它会导致不确定的行为。配置 mixin 以使每个子列表都按其表的主键排序的最佳方法是什么，即使它是复合主键？

我正在尝试为小型游戏的 AI 实现 MCTS 算法。游戏是一个rpg模拟游戏。AI应该决定在战斗中玩什么动作。这是一场回合制战斗（FF6-7 风格）。不涉及任何运动。

我不会详细说明，但我们可以有把握地假设，在任何给定情况下，当轮到该玩家出牌时，我们肯定知道什么动作会选择玩家。

当一方没有单位存活时，游戏结束（4v4）。它可以进行任意数量的回合（也可能永远不会结束）。伤害计算和技能处理中有很多 RNG 元素（攻击可以命中/未命中，暴击与否，有很多 proc 可以“触发”或不“触发”，buff 可以有 % 值发生等。 ..)。每个单元都有大约 6 种技能，可以让您了解分支因素。

我已经建立了一个初步版本的 MCTS，目前结果很差。我在一些事情上遇到了麻烦：

我的主要问题之一是如何处理我的动作的非确定性状态。我已经阅读了几篇关于此的论文，但我仍然一无所知。

有人建议确定游戏信息并在其上运行 MCTS 树，重复该过程 N 次以涵盖广泛的可能游戏状态，并使用该信息做出最终决定。最后，它确实将我们的计算时间乘以一个巨大的因子，因为我们必须计算 N 次 MCTS 树而不是一次。我不能依赖它，因为在战斗过程中我有成千上万的 RNG 元素：2^1000 MCTS 树来计算我已经在哪里挣扎不是一种选择:)

我有为相同的动作添加 X 个孩子的想法，但它似乎也没有带来一个好的答案。它会稍微平滑 RNG 曲线，但如果 X 的值与特定 RNG 的百分比相比太大/太小，则可以将其向相反方向移动。而且由于我获得了多个 RNG 标准动作（命中变化、暴击几率、触发某些东西的百分比等），我无法找到满足所有情况的合适的 X 值。比其他任何东西都更像是一个坏创可贴。

同样，每个 RNG 元组添加 1 个节点 {hit or miss ,crit or not,proc1 or not,proc2 or not,etc...} 应该涵盖所有可能的情况，但有一些严重的缺点：只有 5 个 RNG 机制意味着每次移动要考虑 2^5 个节点，计算量太大。如果我们设法全部创建它们，我们可以为它们分配一个概率（与节点元组中每个 RNG 元素的概率相关联）并在我们的选择阶段使用该概率。这应该总体上有效，但对 cpu 来说真的很难：/

我也无法将它们“合并”在一个节点中，因为我无法根据两种不同的游戏状态准确地平均玩家/怪物统计数据的值，并且在移动处理过程中平均移动结果本身是可行的，但需要很多简化代码是一种痛苦，无论如何都会很快损害我们的准确性。

你有任何想法如何解决这个问题吗？

该算法的其他一些方面让我无法理解：

在结束状态之前我无法进行完整的播放，因为 A）这将花费我大量的计算时间，并且 B）某些战斗可能永远不会结束（按设计）。我有 2 个解决方案（我可以混合使用） - 随机播放 X 轮 - 使用评估函数尝试对情况进行评分。

即使我只考虑评估健康点，我也无法找到一个好的评估函数来返回给定情况下的可靠值（玩家在 1-4 个单位之间，怪物也一样；我知道他们的 hp 当前/最大值）。令我困扰的是，战斗的长度/权力差异可能会有很大差异。这意味着有时 0.01% 的 Hp 变化很重要（例如，对于长时间的游戏与老板的关系），有时它只是微不足道的（当玩家与他相比的低 lvl 区域时）。

战斗之间的功率差异和 Hp 差异意味着我在 UCB 选择过程中的 Biais 参数很难修复。我目前正在使用非常低的东西，比如 0.03。任何 > 0.1 且探索因子如此之高，以至于我的树是按深度构建的：/

目前，我还在模拟阶段使用偏向的方式来选择移动：它选择玩家在这种情况下会选择的移动，并为 AI 选择随机移动，从而导致模拟偏向于玩家。我已经尝试对两者都使用纯随机的，但它似乎给出了更糟糕的结果。你认为有一个有偏见的模拟阶段是否有悖于算法的目的？我倾向于认为它只会给人工智能带来悲观的看法，不会对最终结果产生太大影响。也许我的想法是错误的。

欢迎任何帮助:)

我多么希望我有一个最小的工作示例！

我正在使用HSL 库做一堆线性代数。我已经打开了我能想到的所有调试标志。

在我的工作站上，我的“确定性”代码的最终结果很少奏效。大多数时候，它抱怨索引错误：

在我的工作站（Mac OS 10.7.5 和 ifort 12）上：

在我的笔记本电脑上（Mac OS 10.10.5 和 ifort 16）：

（您可能会注意到这实际上是两个不同的错误，即使我没有更改它们之间的一行代码。）

我的代码在我的笔记本电脑上使用较新版本的大约 70% 的时间成功运行，但在我的工作站上ifort使用旧版本的只有大约 20% 的时间。ifort奇怪的是，它确实工作的时间通常是在重新编译之后，并且在工作一次之后，它每次都会给出该错误。一次成功，第二次失败，第三次成功。（有时在我的笔记本电脑上，它适用于前 2-3 次运行，但第四次抛出错误。）

我自己的代码是完全确定的：它正在设置求解线性代数例程。它还调用了 HSL 例程，这些例程显然调用了 MKL。我会假设 HSL 和 MKL 都是确定性的——也就是说，相同的输入产生相同的输出。（他们不调用 RAND() 或执行文件 I/O ......）不过，我不确定。

更新：

我查了 ma48d.f 的第 1461 行：

在我的笔记本电脑上，它之所以抱怨是因为k它的值-1（导致错误），而它通常的值是0（导致成功）。奇怪的是，我给这些例程提供了完全相同的输入，而且代码似乎是确定性的，所以它们应该执行完全相同的行……但它们没有。

我的问题：

什么可能导致这种不稳定的行为？

到目前为止，我想到了以下几种可能性：

• 内部编译器错误（支持证据：较新版本的 ifort 似乎产生了更好的结果——但甚至只是不同的——结果。）
• 与堆栈/堆相关的东西 （支持证据：它第一次有效，但之后无效。）
• MKL（BLAS）是非确定性的（不太可能）（支持证据：回溯指向 libintlc.dylib，这是一个英特尔库......可能与 MKL 有关？）
• HSL 是不确定的（可能？？）（支持证据：代码似乎是确定性的，尽管此代码中至少有一个错误。）
• 关于 ifort 的安装或 Mac OS X 的配置？（支持证据：这是一台旧机器，可能某处出了问题？）

我发现 C# 中的 dispose 方法用于确定性垃圾收集，因为您知道在调用该方法时对象已被释放。你能提供一个关于非确定性垃圾收集的简单例子吗？它通常发生在多线程情况下吗？

谢谢