主页 / 问题 / 785352
Accepted
Michael
Asked:2020-02-15 09:30:13 +0000 UTC2020-02-15 09:30:13 +0000 UTC

确定性和非确定性算法（形式化）

  • 772

面对这样一个事实，即维基百科定义的质量还有很多不足之处。是的，有很多文字，但形式化并不完整和准确。从字面上看，符文的其余部分是空的。也就是说，来自同一个维基百科的数百个复制粘贴站点。搜索有关编程和算法的书籍（特别是）也没有返回任何结果。要么根本没有定义，要么断章取义，要么翻译质量和编辑的工作太离谱，难以把握意思。

我决定自己正式确定它们之间的差异。我意识到我一个人无法应付。我已经做了一些事情，也许在你的帮助下，可以填补定义中的空白，用波浪号表示。

如果您可以更好地制定公式，请给出确定性和非确定性算法的定义（stochastic，已经有最完整的定义，同时不是一个大的但可以理解的定义）。

分支算法包括：

  • 行为完全取决于输入数据的算法称为确定性|deterministic|。他走的每一步都是预先确定的。～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～ ~~~~~~~~~~
    因此，处理相同的输入总是会导致相同的结果。
  • 无法预测行为（它依赖于什么？）的算法称为非确定性|非确定性|。
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    _和不同的结果。

有时，问题的解决方案归结为使用随机变量。

  • 除输入数据外，其行为由随机（伪随机）数生成器的值确定的算法称为随机| randomized|

除了维基百科之外，真的没有人能够给出这些概念的定义吗？原则上，这些概念是编程的基础？有合适的书吗？总得来说很奇怪，那么多人受过高等教育，教授难道真的不给学生这么基本的定义吗？

алгоритм

3 个回答

  1. Best Answer

    这类算法由罗伯特·弗洛伊德在 1967 年提出。如果我们转向原始来源，图片将如下所示：

    您已经在问题中给出了确定性算法的定义。

    非确定性算法与确定性算法的不同之处不在于使用随机数，而在于存在影响结果的其他变量，除了那些从输入数据中获得的变量。如果你采用一些实现非确定性算法的函数，那么对于输入数字，它会返回一个结果，而对于相同的数字，它可能会返回不同的结果。

    这些标准对应于实现 PRNG 的功能。通过调用函数rand()，您每次都会得到一个不同的数字，即使您通过调用显式设置随机数生成器的初始数字srand()。

    #include <iostream>
using namespace std;
 
int main() {
    srand(42);
    std::cout << rand() << std::endl;
    std::cout << rand() << std::endl;
    std::cout << rand() << std::endl;
 
    std::cout << std::endl;
 
    srand(42);
    std::cout << rand() << std::endl;
    std::cout << rand() << std::endl;
    std::cout << rand() << std::endl;
 
    return 0;
}

    输出：

    71876166
708592740
1483128881

71876166
708592740
1483128881

    如您所见，函数的行为是rand()可预测的，并且取决于初始内部状态。但是，如果您不知道初始状态，那么即使不是不可能，也很难预测行为。

    算法的内部状态不是输入。你不一定能影响他们。例如，让我们以一只猫为例。如果猫是饱的和健康的，那么她会很乐意爱抚。如果猫饿了或生病了，那么通过您的相同操作（输入数据），您几乎肯定会被抓伤。因此，我们可以说猫的行为是由非确定性算法决定的。

    由随机数确定的算法是非确定性算法的一个亚种。它们被称为概率算法。例如，可以包括一个简单的神经网络，其中初始权重由随机数表示。对于给定的一组数据和初始权重数据，其他条件相同，训练后，您将始终获得相同的最终权重。另一个同时具有不确定性和概率性的算法示例是包含dropout 层的卷积神经网络。对于相同的输入数据和初始权重，在这样的网络中训练后的最终权重可能会随机不同。

    • 6

  2. 为了避免将不必要的依赖（如时间、输入等）和自省引入算法的黑匣子，我提出如下定义：

    确定性：一种算法，给定多个正确答案，总是产生相同的答案。

    非确定性：一种算法，给定多个正确答案，总是产生其中一个。

    这是因为算法的结果通常通过一个简单的自然问题来检查，找到的路径的长度如何不超过 5？或者在找到的点处函数的值是否等于零？. 并且无论对同一数据使用哪种算法，验证答案都应该是相同的。

    • 2

  3. 在函数式编程中，引入了“纯函数”的概念。这是一个函数，给定某些参数，返回相同的结果。总是。也就是说，它不访问任何外部资源：它不查询数据库，不接收来自随机数生成器的数字，不接收来自控制台的输入，甚至不在任何地方显示数据（这也是诉诸外部资源：如果输出数据，有什么可能 - 一些 I/O 错误，而不是预期的结果，例如可能发生异常）计算此函数的算法是确定性算法。

    非纯函数称为具有副作用的函数。它们包含非确定性算法。随机是他们的亚种。

    例如：

    // эта функция детерминирована
public static int DeterministicAdd(int a, int b)
{
    return a + b;
}

// эта функция недетерминирована    
public static int NonDeterministicAdd(int a, int b)
{
    return a + b + int.Parse(Console.ReadLine());
}
    • 1

相关问题