Prolog 的时间复杂度比天真的蛮力好吗？
Time complexity of Prolog better than naive brute force?
在（最好的）Prolog 中解决任何问题的时间复杂度是否比天真的蛮力回溯实现更好？
我一般说 Prolog 语言...我想知道是否有一些众所周知的算法，例如使 'doing Prolog' 在 Scheme 中使用 call/cc 回溯成为一个糟糕的选择.
编辑："solving anything" 我指的是所有 Prolog 程序。 "question in a question"：我想知道语言设计：完整延续是否比部分延续有任何实用性（主要优点是 Prolog 式，但如果它们不能在时间复杂度上与Prolog)，以及是否另一种语言可以完全吸收 Prolog，或者是否可以通过将程序限制为 Prolog 形式来进行优化（类似于 Fortran 中可能对 C 的优化）。
编辑：我所说的时间复杂度是指大 O，即不可能用通用语言天真地模拟 Prolog 的修剪。
鉴于您要求解决任何问题，Prolog 肯定可以在线性时间内解决一些问题。例如下面的 append/3 谓词：
append([H|A],B,[H|R]) :-
append(A,B,R).
append([],L,L).
现在因为在每一步，只有一个候选谓词，没有分支，因此没有指数时间复杂度。谓词在第一个列表的长度上线性运行。
此外，可以在 Prolog 中允许 制表，这会导致某种动态规划，有时可以在快速算法中转换蛮力回溯算法。
恕我直言，这取决于问题。如果它真的只能通过蛮力和回溯来解决，我认为（即使是理想化的“best”）Prolog 也不会比 e 快。 G。一个写得很好的 C 程序。
另一方面，如果您有 Prolog 可以使用其数据库和演绎方法解决的那种问题（因此，不一定是蛮力回溯），它可能比另一种蛮力具有更好的性能回溯程序。
最后，每种编程语言最终都会创建在您的 CPU 上运行的机器代码，以（希望）解决您的问题。相同的机器代码也可以由其他语言或或多或少直接由程序员生成。所以，总而言之，Prolog 是解决某些问题的好方法，但它不一定是最好/最快/唯一的选择。
你问题中的问题似乎是，如果我在 Scheme 中编写类似 Prolog 的代码，它的性能是否会比在 Prolog 中编写 Prolog 更差？
没有直接的答案。事实上，你的问题中很好地映射到 Prolog 的部分可能会比它在 Prolog 中的表现更差。为什么？因为 Prolog 的内在函数都是用 Prolog 写的，而你的内在函数都是用 Scheme 写的。正如@CommuSoft 用 append/3 指出的那样，内部函数的 Prolog 实现能够利用 Prolog 的优势。您将在这些部分进行艰苦的战斗。此外，我们拥有的 Prolog 实现已经足够古老，可以花费数十年的时间来提高统一的性能，因为这是这里有趣的领域。
与此同时，大多数重要的 Prolog 程序最终都会以一些程序位结束。这些位可能无法与 C 或 Scheme 竞争，因为优化它们没有那么有趣，而且无论对此进行的任何研究都是在 Scheme 和 ML 中进行的。所以你会在这些方面获胜。
作为 Scheme 用户，我认为您会发现以 Scheme 风格编写程序更有利可图：函数式，带有一些宏以使其具有声明性的感觉。如果你有一个对 Prolog 来说非常好的问题，你总是可以抛出 miniKanren 来解决它，但要将它与程序的其余部分隔离开来。让你的语言成为你的语言。
我不同意@ahuemmer 关于 C 与 Prolog 的区别，只是因为劳动力是有限的，而且程序除了性能之外还有很多方面。 C 的作者成本要高得多，所以你会更努力地采用较差的策略，并最终得到不太灵活的代码。即使您将问题 space 限制在一些小的和明确定义的问题上，Prolog 程序员也会有更多的时间来试验和发现更好的解决方案，可能具有更好的时间复杂度。如果我们谈论无限量的劳动，C 版本可能会胜过第一个 Prolog 版本。但是你必须考虑所有的维度。
总的来说，我认为让程序员适应语言比让语言适应问题更重要。
当字面上翻译成 Prolog 时，朴素的强力搜索将保持朴素的强力搜索。
没关系：Plain Prolog 非常适合描述和运行 强力搜索。不过，您可能无法通过用 Prolog 编写的强力搜索来击败任何手动优化的低级版本的强力搜索。另一方面，Prolog 的输入非常简单方便，您可能很快就会通过一些原型设计找到更好的搜索策略，而这些其他策略通常会轻松击败 any 蛮力实现以巨大的优势。即使在天真地翻译时，Prolog 也非常擅长回溯，并且在较低级别代码的某些因素（更小或更大，取决于您使用的 Prolog 实现）因素内有效地进行回溯。
然而，Prolog 在描述搜索问题时相对于许多其他语言的主要优势是 约束：由于所谓的约束 传播，搜索 space 通常可以 显着 和 自动 修剪。您无需特殊规定：约束求解器将为您完成。
约束的承诺，并且该承诺在很大程度上变成了现实，是 (1) 您陈述需求，(2) Prolog 引擎为您找到解决方案。查看 clpfd 该方案的一个非常重要的实例。
因此我提出以下问题：在任何语言中，将天真的暴力搜索转换为更明智的搜索策略有多容易？毕竟，这就是真正重大的改进通常成为可能。
在 Prolog 中，答案通常是：非常简单。在大多数其他语言中，没有那么多。
Pure Prolog（没有 "cut" 运算符或命令式特征）在一个方面表现出色：对于某些 class 问题，它是 "complete refutation procedure"。如果问题没有解决方案，Prolog 程序将终止并宣布没有解决方案。另一方面，如果问题确实有解决方案，程序可能会找到 none 或部分或全部，但无法终止。
如果您使用命令式功能或削减，则所有投注均无效。
Prolog 有时可以处理具有无限多个答案的问题，前提是答案具有正确的模式。
在（最好的）Prolog 中解决任何问题的时间复杂度是否比天真的蛮力回溯实现更好？
我一般说 Prolog 语言...我想知道是否有一些众所周知的算法，例如使 'doing Prolog' 在 Scheme 中使用 call/cc 回溯成为一个糟糕的选择.
编辑："solving anything" 我指的是所有 Prolog 程序。 "question in a question"：我想知道语言设计：完整延续是否比部分延续有任何实用性（主要优点是 Prolog 式，但如果它们不能在时间复杂度上与Prolog)，以及是否另一种语言可以完全吸收 Prolog，或者是否可以通过将程序限制为 Prolog 形式来进行优化（类似于 Fortran 中可能对 C 的优化）。
编辑：我所说的时间复杂度是指大 O，即不可能用通用语言天真地模拟 Prolog 的修剪。
鉴于您要求解决任何问题，Prolog 肯定可以在线性时间内解决一些问题。例如下面的 append/3 谓词：
append([H|A],B,[H|R]) :-
append(A,B,R).
append([],L,L).
现在因为在每一步，只有一个候选谓词，没有分支，因此没有指数时间复杂度。谓词在第一个列表的长度上线性运行。
此外，可以在 Prolog 中允许 制表，这会导致某种动态规划，有时可以在快速算法中转换蛮力回溯算法。
恕我直言，这取决于问题。如果它真的只能通过蛮力和回溯来解决，我认为（即使是理想化的“best”）Prolog 也不会比 e 快。 G。一个写得很好的 C 程序。
另一方面，如果您有 Prolog 可以使用其数据库和演绎方法解决的那种问题（因此，不一定是蛮力回溯），它可能比另一种蛮力具有更好的性能回溯程序。
最后，每种编程语言最终都会创建在您的 CPU 上运行的机器代码，以（希望）解决您的问题。相同的机器代码也可以由其他语言或或多或少直接由程序员生成。所以，总而言之，Prolog 是解决某些问题的好方法，但它不一定是最好/最快/唯一的选择。
你问题中的问题似乎是，如果我在 Scheme 中编写类似 Prolog 的代码，它的性能是否会比在 Prolog 中编写 Prolog 更差？
没有直接的答案。事实上，你的问题中很好地映射到 Prolog 的部分可能会比它在 Prolog 中的表现更差。为什么？因为 Prolog 的内在函数都是用 Prolog 写的，而你的内在函数都是用 Scheme 写的。正如@CommuSoft 用 append/3 指出的那样，内部函数的 Prolog 实现能够利用 Prolog 的优势。您将在这些部分进行艰苦的战斗。此外，我们拥有的 Prolog 实现已经足够古老，可以花费数十年的时间来提高统一的性能，因为这是这里有趣的领域。
与此同时，大多数重要的 Prolog 程序最终都会以一些程序位结束。这些位可能无法与 C 或 Scheme 竞争，因为优化它们没有那么有趣，而且无论对此进行的任何研究都是在 Scheme 和 ML 中进行的。所以你会在这些方面获胜。
作为 Scheme 用户，我认为您会发现以 Scheme 风格编写程序更有利可图：函数式，带有一些宏以使其具有声明性的感觉。如果你有一个对 Prolog 来说非常好的问题，你总是可以抛出 miniKanren 来解决它，但要将它与程序的其余部分隔离开来。让你的语言成为你的语言。
我不同意@ahuemmer 关于 C 与 Prolog 的区别，只是因为劳动力是有限的，而且程序除了性能之外还有很多方面。 C 的作者成本要高得多，所以你会更努力地采用较差的策略，并最终得到不太灵活的代码。即使您将问题 space 限制在一些小的和明确定义的问题上，Prolog 程序员也会有更多的时间来试验和发现更好的解决方案，可能具有更好的时间复杂度。如果我们谈论无限量的劳动，C 版本可能会胜过第一个 Prolog 版本。但是你必须考虑所有的维度。
总的来说，我认为让程序员适应语言比让语言适应问题更重要。
当字面上翻译成 Prolog 时，朴素的强力搜索将保持朴素的强力搜索。
没关系：Plain Prolog 非常适合描述和运行 强力搜索。不过，您可能无法通过用 Prolog 编写的强力搜索来击败任何手动优化的低级版本的强力搜索。另一方面，Prolog 的输入非常简单方便，您可能很快就会通过一些原型设计找到更好的搜索策略，而这些其他策略通常会轻松击败 any 蛮力实现以巨大的优势。即使在天真地翻译时，Prolog 也非常擅长回溯，并且在较低级别代码的某些因素（更小或更大，取决于您使用的 Prolog 实现）因素内有效地进行回溯。
然而，Prolog 在描述搜索问题时相对于许多其他语言的主要优势是 约束：由于所谓的约束 传播，搜索 space 通常可以 显着 和 自动 修剪。您无需特殊规定：约束求解器将为您完成。
约束的承诺，并且该承诺在很大程度上变成了现实，是 (1) 您陈述需求，(2) Prolog 引擎为您找到解决方案。查看 clpfd 该方案的一个非常重要的实例。
因此我提出以下问题：在任何语言中，将天真的暴力搜索转换为更明智的搜索策略有多容易？毕竟，这就是真正重大的改进通常成为可能。
在 Prolog 中，答案通常是：非常简单。在大多数其他语言中，没有那么多。
Pure Prolog（没有 "cut" 运算符或命令式特征）在一个方面表现出色：对于某些 class 问题，它是 "complete refutation procedure"。如果问题没有解决方案，Prolog 程序将终止并宣布没有解决方案。另一方面，如果问题确实有解决方案，程序可能会找到 none 或部分或全部，但无法终止。
如果您使用命令式功能或削减，则所有投注均无效。
Prolog 有时可以处理具有无限多个答案的问题，前提是答案具有正确的模式。