启发式和algorithm之间有什么区别?

启发式和algorithm之间有什么区别?

    algorithm是对问题的自动化解决scheme的描述。 algorithm做了什么精确定义。 解决scheme可能或不可能是最好的,但你从一开始就知道你会得到什么样的结果。 你使用一些编程语言实现algorithm来获得程序的一部分。

    现在,一些问题很难,你可能无法在可以接受的时间内得到一个可以接受的解决scheme。 在这种情况下,通过应用一些任意的select(受过教育的猜测),你通常可以更快得到一个不错的解决scheme:这是一个启发式的方法

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

    典型的例子来自游戏。 在编写国际象棋游戏程序时,您可以想象在某个深度级别尝试每一个可能的举措,并对棋盘应用一些评估function。 启发式将排除以明显不好的移动开始的完整分支。

    在某些情况下,您不是在寻找最佳解决scheme,而是寻求适合某种约束的解决scheme。 一个好的启发式方法将有助于在短时间内find解决scheme,但如果唯一的解决scheme处于它select不尝试的状态,也可能找不到。

    • 一个algorithm通常是确定性的,并被certificate可以产生最优的结果
    • 启发式没有正确性certificate,往往涉及随机元素,可能不会产生最佳结果。

    许多没有find最佳解决scheme的有效algorithm的问题是已知的,启发式方法非常快速地产生接近最佳的结果。

    有一些重叠:“遗传algorithm”是一个公认的术语,但严格来说,这些是启发式algorithm,而不是algorithm。

    启发式,简而言之,就是“受过教育的猜测”。 维基百科很好地解释了它。 最后,将“普遍接受”方法作为指定问题的最佳解决scheme。

    启发式是基于经验技术的形容词,有助于解决问题,学习和发现。 一个启发式的方法被用来迅速find一个解决scheme,希望接近最好的答案,或“最佳解决scheme”。 启发式是“经验法则”,教育猜测,直觉判断或者简单的常识。 启发式是解决问题的一般方法。 启发式作为名词是启发式方法的另一个名称。

    更确切地说,启发式就是使用容易获取的信息,虽然可以松散地应用,但是信息控制着人类和机器中的问题解决。

    虽然algorithm是一种包含用于解决问题的有限指令集的方法。 该方法已被math或科学certificate可以解决这个问题。 有正式的方法和certificate。

    启发式algorithm是一种能够在许多实际场景中以一般启发式方式产生对于问题的可接受解决scheme的algorithm,但是对此没有正确性的正式certificate。

    其实我不认为他们之间有很多共同之处。 某些algorithm在逻辑中使用启发式(通常是减less计算或获得更快的结果)。 通常在所谓的贪婪algorithm中使用启发式algorithm。

    启发式algorithm是我们假设的一些“知识”,以便在我们的algorithm中获得最佳select(当应该进行select时)。 例如…国际象棋的启发式可能是(如果可以的话,总是把对手的女王,因为你知道这是更强大的数字)。 启发式方法并不能保证你会导致你正确的答案,但是(如果这个假设是正确的)经常在很短的时间内得到接近最好的答案。

    启发式algorithm是algorithm,所以从这个意义上说,没有任何启发式algorithm采用“猜测”的方法来解决问题,产生了一个“足够好”的答案,而不是find一个“最好的”解决scheme。

    一个很好的例子就是你需要一个解决scheme的非常困难(读完NP-complete)的问题,但是没有时间去解决它,所以必须使用基于启发式algorithm的足够好的解决scheme,例如使用遗传algorithm寻找旅行推销员问题的解决scheme。

    algorithm是给定input的一些操作的序列(函数)并输出结果。

    algorithm可能会产生一个确切的或近似的值。

    它也可以计算一个接近精确值的高概率的随机值。

    启发式algorithm使用对input值的一些洞察并计算不精确的值(但可能接近最优)。 在一些特殊情况下,启发式可以find确切的解决scheme。

    algorithm是一组明确定义的解决问题的指令,启发式algorithm包括利用学习和发现的方法来达成解决scheme。

    所以,如果你知道如何解决一个问题然后使用一个algorithm。 如果你需要开发一个解决scheme,那么这是启发式的。

    启发式通常是一种优化或策略,通常提供足够好的答案,但并不总是,也很less是最好的答案。 例如,如果你用暴力来解决旅行商问题,一旦其成本超过当前最好的解决scheme,丢弃一个部分的解决scheme就是一种启发式的方法:有时它有帮助,其他时间则不起作用,改进algorithm的理论(大哦)运行时间

    我认为启发式更多的是在人工智能学习模型中使用的约束,因为未来的解决scheme状态很难预测。

    但是在阅读上面的答案之后,我的疑问是“如何使用随机优化技术成功应用启发式algorithm?或者当它们与随机优化一起使用时,它们可以作为完整的algorithm吗?

    http://en.wikipedia.org/wiki/Stochastic_optimization

    我已阅读的最好的解释之一来自Code Complete ,我现在引用:

    启发式是一种帮助您寻找答案的技巧。 其结果很可能是因为启发式只告诉你如何看,而不是find什么。 它没有告诉你如何直接从A点到B点; 它甚至可能不知道A点和B点在哪里。 实际上,启发式algorithm是一种小丑服装的algorithm。 这是不太可预测的,它更有趣,它没有30天的退款保证。

    这里是一个开车到别人家的algorithm:把167号高速公路南到Puy-allup。 从南山购物中心出口出发,在山上行驶4.5英里。 在杂货店的灯光右转,然后左转。 转入位于北雪松714号左侧的大型棕褐色房屋的车道。

    这是一个启发式的方法来find别人的房子:find我们邮寄给你的最后一封信。 开车到镇上的返回地址。 当你到达城市的时候,问问我们的房子在哪里。 每个人都知道我们 – 有人会乐意帮助你。 如果找不到任何人,请用公用电话给我们打电话,我们会帮你find你的。

    algorithm和启发式之间的区别是微妙的,这两个术语有些重叠。 就本书而言,两者的主要区别在于解决scheme的间接性。 一个algorithm直接给你的指示。 启发式告诉你如何发现你自己的指示,或至less在哪里寻找他们。

    一个algorithm是一个独立的一步一步的操作集合,通常被解释为一个(计算机或人类)指令的有限序列,以确定一个问题的解决scheme,例如:是否存在从A到B,或者A和B之间的最小path。在后一种情况下,你也可以满足“相当接近”的替代解决scheme。

    有一些类别的algorithm,其中启发式algorithm是一个。 在这种情况下,根据algorithm的(certificate的)属性,它属于以下三个类别之一(注1):

    • 确切的说 :这个解决scheme被certificate是input问题的一个最佳(或精确的解决scheme)
    • 近似值 :解的值的偏差被certificate不会比最优值远离一些预先定义的界限(例如,不超过最佳值的50%),
    • 启发式algorithm:algorithm没有被certificate是最优的,也没有在最优解的预定义范围内

    请注意,近似algorithm也是一种启发式algorithm,但是具有更强的性质,它certificate了解决scheme(值)的输出。

    对于一些问题,没有人find一个“高效”的algorithm来计算最优解(注2)。 其中一个问题是众所周知的旅行推销员问题。 例如,Christophides的“旅行推销员问题”algorithm曾被称为启发式algorithm ,因为它没有被certificate在最优解的50%以内。 但是,由于已经certificate,Christophidesalgorithm更准确地称为近似algorithm。

    由于计算机可以做什么的限制,并不总是能够有效地find可能的最佳解决scheme。 如果问题中有足够的结构,即使解空间是巨大的(即在最短path问题中),也可能有一种遍历解空间的有效方法。

    通常通过添加“专家信息”或“受过教育的猜测”来引导search方向,启发式algorithm通常用于改善algorithm的运行时间。 在实践中,启发式也可以是最佳algorithm的子程序,以确定首先看哪里。

    (注1) :此外,algorithm的特点是它们是否包含随机或非确定性元素。 总是以相同方式执行并产生相同答案的algorithm称为确定性(deterministic)。

    (注2) :这被称为P对NP问题,被归类为NP完全和NP难的问题不可能有一个“有效”的algorithm。 注意; 正如@Kriss在评论中提到的那样,甚至有更糟的types的问题,这可能需要指数的时间或空间来计算。

    有几个答案回答了部分问题。 我认为他们不够完整,不够准确,并决定不编辑@Kriss所接受的答案

    他们find一个解决scheme次优,没有任何保证的解决scheme的质量,这是显而易见的启发式多项式的发展是有意义的。 这些方法的应用适合于解决现实世界中的问题或从计算的angular度来看这么尴尬的大问题,甚至连一个algorithm都不能find多项式时间的近似解。