启发式与算法之间的区别是什么？

Question

启发式与算法之间的区别是什么？

algorithmdefinitionheuristicsnomenclature

114

启发式算法和确定性算法有什么区别？

- streetparade

3

好的，我会尽力进行翻译。以下是您需要翻译的内容：请查看http://en.wikipedia.org/wiki/Heuristic_algorithm - Nick Dandoulakis

1

如果您将一种启发式算法视为一种树形结构，我想您可以称其为特殊目的算法。 - James P.

启发式算法是一种（无法证明）有效的算法。 - JeffE

12个回答

34

算法通常是确定性的，并且被证明能够产生最优结果
启发式算法没有正确性证明，通常涉及随机元素，并且可能无法产生最优结果。

许多问题没有已知的有效算法来找到最优解，但有启发式方法可以快速产生接近最优结果。

一些术语存在重叠： "遗传算法" 是一个被接受的术语，但严格来说，它们是启发式算法，而不是算法。

- Michael Borgwardt

3

我不会说一个算法已经被证明能产生最优结果：这取决于解决问题的算法。 - nbro

1

算法的关键品质不是产生最优结果，而是精确性，即确切的结果，而启发式算法则提供近似结果。 - Marina Dunst

22

启发式（Heuristic）简而言之就是“经验猜测”。维基百科对此做了很好的解释。最终，一种“普遍认可”的方法被视为特定问题的最佳解决方案。

启发式（Heuristic）是一个形容词，用于描述基于经验的技术，帮助问题解决、学习和发现。启发式方法用于快速得出一种被认为接近最佳可能答案或“最优解”的解决方案。启发式是一种“经验法则”，教育性的猜测，直觉判断或者单纯的常识。启发式是解决问题的通用方式。名词启发式是启发式方法的另一个名称。

更精确地说，启发式代表使用易于获取但适用范围较宽的信息来控制人类和机器的问题解决的策略。

而算法是包含有限指令集的方法，用于解决问题。该方法在数学或科学上已被证明适用于该问题。有正式的方法和证明。

启发式算法是一种能够在许多实际场景下产生可接受解决方案的算法，就像一般的启发式方法一样，但并没有形式化证明其正确性。

- Buhake Sindi

9

算法是一个自包含的操作步骤集，按顺序执行4，通常被解释为（计算机或人类）指令的有限序列，用于确定问题的解决方案，例如：是否有从A到B的路径，或者A和B之间的最短路径是多少。在后一种情况下，您可能也满意于“相对接近”的替代解决方案。

有某些种类的算法，其中启发式算法就是其中之一。根据此算法的（已证明的）属性，它可以分为以下三个类别之一（注1）：

精确算法：该解决方案被证明是输入问题的最优（或精确）解决方案
近似算法：已经证明解决方案值的偏差永远不会比预定义的界限更远离最优解（例如，永远不会比最优解大50%以上）
启发式算法：该算法尚未被证明是最优的，也不在预定义的最优解的范围内

请注意，近似算法也是一种启发式算法，但具有更强的属性，即它的解决方案（值）存在已经证明的界限。

对于一些问题，没有人能够找到一个“高效”的算法来计算最优解（注2）。其中一个这样的问题就是著名的旅行商问题。例如，Christophides算法用于旅行商问题，曾经被称为一种启发式算法，因为它没有被证明它可以在最优解的50%以内。然而，自从它被证明后，Christophides算法更准确地被称为近似算法。

由于计算机所能做的事情受到限制，有时不可能高效地找到最好的解决方案。如果问题中有足够的结构，可能会有一种有效的方法来遍历解决方案空间，即使解决方案空间很大（即在最短路径问题中）。

启发式算法通常被应用于改进算法的运行时间，通过添加“专家信息”或“教育猜测”来指导搜索方向。在实践中，启发式算法也可能是最优算法的子程序，用于确定首先查找的位置。 （注1）：此外，算法的特征还取决于它们是否包含随机或非确定性元素。总是以相同方式执行并产生相同答案的算法称为确定性算法。 注2：这被称为P vs NP问题，被归类为NP完全和NP难的问题不太可能有一个“高效”的算法。注意：正如@Kriss在评论中提到的那样，甚至还有需要指数时间或空间来计算的“更糟糕”的问题。

有几个答案回答了部分问题。我认为它们不够完整和准确，决定不编辑由@Kriss提供的已接受的答案。

- Joost

我认为你对算法这个词的定义太过狭隘了。使用“序列”这个词是否意味着非并行？并行算法现在很常见。那么使用神经网络或约束传播工具来解决问题呢？算法？元算法？ - kriss

读者可能会觉得NP问题是最糟糕的问题。但这并不正确。有些问题确实非常难，需要使用指数级别或更糟糕的算法。NP问题之所以特殊，是因为如果我们已经有了解决方案，那么检查它的正确性就很容易和快速；但如果我们没有解决方案，那么找到它就非常困难。就像检查我们是否有正确的指令走出迷宫很容易，但找到出口却很难一样。因此，NP问题既容易又困难——如果我们能同时尝试所有可能的解决方案（非确定性地），那么解决它将非常简单……但我们做不到。 - kriss

谢谢您的反馈！我稍微修改了措辞，并采用了不同的方法。在我看来，约束传播是一种处理问题的技术，但还不是描述如何逐步达到约束传播所描述的解决方案的算法。您当然对expspace和“更糟”的类别是正确的，我也加了一条注释。顺便说一下：请将NP-Complete和/或NP-Hard完全写出，因为NP的子集也包含“有效”可解决的问题，这些问题（据推测）与NP-Hard并不相同。 - Joost

当然，你是对的，我应该写成NP-Complete。我的错。 - kriss

这比我的一个同事所称的“NP-ness”要好得多（听起来很糟糕，有点恶心...） - Joost

6

实际上，我认为它们之间没有太多共同点。一些算法在其逻辑中使用启发式（通常是为了减少计算量或获得更快的结果）。通常启发式用于所谓的贪心算法。

启发式是我们假设在算法中使用会很好的“知识”（当需要做出选择时）。例如...在国际象棋中，一种启发式可能是（如果可以的话，总是拿对手的皇后，因为你知道这是最强的棋子）。启发式不能保证您会得到正确的答案，但是（如果假设是正确的）通常会在更短的时间内得到接近最佳答案的答案。

- anthares

5

算法是一组明确定义的指令，用于解决问题。而启发式方法则利用学习和探索的方法来达到解决问题的目的。

因此，如果您知道如何解决问题，则使用算法。如果您需要开发解决方案，则需要使用启发式方法。

- Lazarus

这应该是被接受的答案。应该强调程序员和（复杂的）算法都可以使用启发式方法。 - G M

5

启发式算法是一种算法，因此本质上没有最佳解决方案，但是启发式算法采用“猜测”方法来解决问题，产生“足够好”的答案，而不是找到“最佳可能”的解决方案。

一个很好的例子是，当你想要解决一个非常困难（即NP完全）的问题，但没有时间去解决它时，就必须使用基于启发式算法的足够好的解决方案，例如使用遗传算法来解决旅行商问题。

- dsm

4

算法是一系列操作的顺序，给定一个输入计算出某个东西（函数），并输出结果。

算法可能产生精确或近似值。

它也可以计算一个随机值，该值很有可能接近于精确值。

启发式算法利用对输入值的一些见解，并计算出不精确的值（但可能接近最优解）。在某些特殊情况下，启发式方法可以找到精确解。

- Slava

2

启发式通常是一种优化或策略，通常提供足够好的答案，但不总是最佳答案。例如，如果您要使用暴力方法解决旅行商问题，则在成本超过当前最佳解决方案的情况下丢弃部分解决方案是一种启发式：有时它有帮助，有时它没有，而且肯定不能改善算法的理论（大O符号）运行时间。

- IVlad

2

我读过的最好的解释之一来自伟大的书籍Code Complete，现在我引用它：

一种启发式是一种帮助你寻找答案的技巧。由于启发式只告诉你如何寻找，而不是要找到什么，因此其结果受到机会的影响。它不告诉你如何直接从A点到B点；甚至可能不知道A点和B点在哪里。实际上，启发式是一个穿着小丑服的算法。它不太可预测，更有趣，并且不带有30天退款保证。

以下是开车去某人家的算法：沿167号高速公路向南到普亚拉普。走南山购物中心出口，沿山路行驶4.5英里。在杂货店旁边的红绿灯处右转，然后第一条左拐。在左侧的大号码为714的北雪松街房子的车道口转弯。

以下是到某人家的启发式：找到我们邮寄给你的最后一封信。开车到回信地址所在的城镇。当你到达城镇时，问别人我们家在哪里。每个人都认识我们——肯定会有人乐意帮助你。如果找不到任何人，请从公用电话打电话给我们，我们会去接你。

算法和启发式之间的区别微妙，两个术语有些重叠。对于本书的目的，两者之间的主要区别是与解决方案的间接性水平相关。算法直接给出指令。启发式告诉你如何自己发现指令，或至少在哪里寻找它们。

- Edwin Dalorzo

声称算法和启发式之间存在差异就像声称鸟和鸡之间存在差异一样。启发式是一种算法。 - Joost

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kriss · Accepted Answer

算法是一种描述自动解决问题的方法。算法所做的事情被明确定义了。解决方案可能是最好的，也可能不是最好的，但你从一开始就知道会得到什么样的结果。你使用一些编程语言来实现算法，以得到（部分）程序。

有些问题很难，你可能无法在合理的时间内得到可接受的解决方案。在这种情况下，通过应用一些任意选择（有根据的猜测）通常可以更快地得到一个不错的解决方案：这就是启发式。

启发式仍然是一种算法，但它不会探索问题的所有可能状态，或者会从最有可能的状态开始探索。

典型的例子来自于游戏。当编写国际象棋游戏程序时，你可以想象在某个深度级别上尝试每一种可能的移动并对棋盘应用一些评估函数。启发式将排除以显然错误的移动开头的完整分支。

在某些情况下，你不是在寻找最佳解决方案，而是在寻找符合某些限制条件的任何解决方案。好的启发式能够帮助你在短时间内找到一个解决方案，但也可能在没有尝试的状态中找不到任何解决方案。