启发式算法和算法有什么区别?
-
22-09-2019 - |
题
启发式算法和算法有什么区别?
解决方案
的算法是一个的自动化解决方案的一个问题强>描述。算法所作的精确定义。该解决方案可以或不可以是最好的一个,但你从一开始什么样的结果,你会得到了解。您可以实现的算法使用某种编程语言来获得(的一部分)的程序
现在,有些问题很难,你可能无法得到在可接受的时间内接受的解决方案。在这种情况下,你往往可以得到一个不太坏的解决方案更快,通过应用一些任意选择(猜测):这是一个启发式
一个启发式仍然是一种的算法的,但一个不会探讨问题的所有可能状态,或将通过探索的最可能的那些开始。
的典型实例是从游戏。当编写一个象棋游戏程序,你可以试想一下,在一些深度级别每一个可能的举动,并运用一些评价功能的主板。启发式将排除满枝头,与明显不良动作开始。
在某些情况下,你不寻找最佳的解决方案,但对于任何解决方案安装一些约束。一个很好的启发,将有助于寻找在短时间内解决,但也可能无法找到任何如果唯一的解决方案是在美国它选择不要尝试。
其他提示
- 算法通常是确定性的,并被证明可以产生最佳结果
- 启发式方法没有正确性证明,通常涉及随机元素,并且可能不会产生最佳结果。
许多问题没有已知的有效算法来找到最佳解决方案,而启发式方法可以非常快速地产生接近最佳的结果。
有一些重叠:“遗传算法”是一个公认的术语,但严格来说,这些是启发式算法,而不是算法。
启发式,概括地说是一个“猜测”。维基百科很好解释它。在末端,一“普遍接受”方法作为最优解到指定的问题。
启发式为形容词 基于经验的技术,帮助 在解决问题,学习和 发现。启发式方法用于 迅速得出一个解决方案, 希望接近最佳 答案,或“最优解”。 启发式是“拇指规则”, 猜测,直观的判断 或者干脆常识。启发式是 解决问题的一般方法。 启发式作为一个名词是另一个名字 启发式方法。
在更精确的术语,试探法 主张使用现成的策略 访问,虽然松散的适用, 信息控制解决问题 在人类和机器。
虽然算法是含有有限组用于解决问题的指令的方法。该方法已在数学或科学证明,对这个问题的工作。有正式的方法和证明。
<强>启发式算法强>是一种算法,它能够产生一个 上可接受的解决办法的一个问题 许多实际情况下,在 一般启发式的时尚,但 对此有没有正式的证明 它的正确性。
其实我不认为有很多在他们之间共同的。在他们的逻辑有些算法使用启发式(往往使更少的计算或获得更快的结果)。通常启发式在所谓的贪婪算法中使用。
启发式扫描是一些“知识”,我们认为是很好的利用,以获得最佳的选择,在我们的算法(当选择应考虑)。例如...在棋启发式扫描,可能是(总,如果你可以把对手的皇后,因为你知道这是强图)。启发式不向你保证,将导致你正确的答案,但(如果假设是正确的)经常会得到答案,是接近最好在更短的时间。
一个 算法 是要执行的一组独立的分步操作 4, ,通常解释为(计算机或人类)指令的有限序列,以确定问题的解决方案,例如:是否存在从 A 到 B 的路径,或者 A 和 B 之间的最小路径是什么?在后一种情况下,您也可能会对“相当接近”的替代解决方案感到满意。
算法有某些类别,启发式算法就是其中之一。根据本例中算法的(已证明的)属性,它属于以下三类之一(注 1):
- 精确的: :该解决方案被证明是最佳的(或 精确的 解)输入问题
- 近似: :事实证明,解值的偏差永远不会比某个预定义的界限更远离最优值(例如,永远不会比最优值大 50% 以上)
- 启发式: :该算法尚未被证明是最优的,也不在最优解的预定义范围内
请注意,近似算法也是一种启发式算法,但具有更强的属性,即它输出的解决方案(值)有经过证明的界限。
对于某些问题,没有人找到一种“有效”的算法来计算最优解(注 2)。这些问题之一是著名的旅行商问题。例如,Christophides 的旅行商问题算法过去被称为 启发式, ,因为尚未证明其与最优解的误差在 50% 以内。然而,由于已经被证明,Christophides 的算法更准确地称为近似算法。
由于计算机功能的限制,并不总是能够 有效率的 找出 最好的 可能的解决方案。如果问题中有足够的结构,则可能有一种有效的方法来遍历解空间,即使解空间很大(即在最短路径问题中)。
启发式方法通常用于通过添加“专家信息”或“有根据的猜测”来指导搜索方向,从而提高算法的运行时间。在实践中,启发式也可能是最佳算法的子例程,以确定在哪里寻找 第一的.
(注1): :此外,算法的特征还在于它们是否包含随机元素或非确定性元素。始终以相同方式执行并产生相同答案的算法称为确定性算法。
(笔记2): :这称为 P vs NP 问题,被分类为 NP 完全和 NP 困难的问题不太可能有“有效”算法。笔记;正如 @Kriss 在评论中提到的,甚至还有“更糟糕”类型的问题,可能需要指数时间或空间来计算。
有几个答案可以回答部分问题。我认为它们不太完整且不够准确,因此决定不编辑 @Kriss 所做的已接受答案
启发式算法,所以在这个意义上是没有的,但是,启发式采取“猜测”的方式来解决问题,产生一个“足够好”的答案,而不是寻找一个“最佳”的解决方案。
一个很好的例子是,你有一个非常困难的(读NP完全)问题,你想一个解决方案,但没有到达它的时间,因此必须使用基于启发式算法足够好的解决方案如使用遗传算法找到解决一个旅行推销员问题。
算法是某些操作给定的输入单位计算的东西(的函数)的一个序列,并输出其结果。
算法可以产生一个精确的或近似的值。
它还可以计算随机值,该值是高概率接近准确值。
一个启发式算法使用输入值的一些见解而不是计算精确值(也可以是接近最佳)。 在某些特殊情况下,启发式可以找到精确解。
的算法是一个明确界定的指令集以解决一个问题,启发式涉及利用学习和发现的一种方法来达到的溶液中。
所以,如果你知道如何解决问题,那么使用的算法。如果你需要制定一个解决方案,然后它的启发。
一个启发式通常是优化或通常提供足够好的答案,但并非总是如此,很少最佳答案的策略。例如,如果你要解决蛮力旅行商问题,丢弃部分解决,一旦成本超过了目前最好的解决方案是一种启发式:有时有帮助,它没有其他时候,它肯定没有按”吨提高理论(大-OH表示法)运行的算法
的时间我认为启发式更人工基于学习模型中使用的约束的智能,因为未来溶液状态是难以预料的。
但随后阅读上述答案后我的怀疑是 “怎么会启发式可以成功地使用随机优化技术应用?或者随机优化使用时,它们可以作为完全成熟的算法?”
一个我看过的最好的解释来自于伟大的书代码完成一>,我现在引述如下:
一个启发是一种技术,可以帮助您寻找答案。它的 结果受到的机会,因为启发式告诉你如何只 一看,没找到什么。它不会告诉你如何获得直接 从点A到点B;它可能甚至不知道在哪里点A和 B点是。实际上,启发式是一个小丑服的算法。 这是predict-能力较差,这是更多的乐趣,而且都是有30天, 退款保证。
下面是开车到别人的房子的算法:以167公路 南多姆allup。就拿南山商场出口,推动4.5英里 上山。右转灯由杂货店,然后 第一个路口左转。转成黄褐色大房子的车道上 左侧,在714北雪松。
下面是用于获取到别人的房子启发:找到最后一个 信寄给我们你。行驶到返回地址镇。什么时候 你到镇,请同学们在那里我们的房子。谁都知道 美国有人会很乐意帮助你。如果你不能找到任何人,来电咨询 从公共电话,我们会来给你。
的算法和一种启发式之间的差异是微妙的,并且 两个词有点过一圈。对于这本书的目的,主要 两者之间的区别是间接的从水平 解。算法直接给你的指令。一种 启发式告诉你如何去发现说明自己,或 至少在哪里查找它们。
他们发现不作任何保证解决方案未达最佳的为溶液中发现的质量,很明显,它是有道理的启发式只多项式的发展。这些方法的应用是合适的解决现实世界问题或大问题从视计算点这样笨拙,对他们甚至没有能够发现在多项式时间近似解的算法。