启发法

背景介绍

启发式方法是利用有限的知识和少量的时间，找到问题的适当解决方案的艺术。更正式地说，启发式方法是基于经验的；它们可以利用简单的规则加速搜索解决方案。完整的搜索可能需要太长的时间，也可能太难做到。

更确切地说，启发式方法是利用容易获得的、尽管是松散的信息来控制人类和机器的问题解决的策略。

启发式方法可以用在某些科学领域，但不能用在其他领域。对于经济学来说，一个误差为百分之一的解决方案通常是可以接受的；一个误差为一度的望远镜，如果对准一个遥远的物体，可能就无法使用。同样的望远镜对准街对面的窗户，可能会容忍这个误差；错过一度，对短距离的影响不会很大。

启发式方法可以用来估计一个答案，然后通过在非常小的范围内执行精确的解决方案来使答案更加明确，也许是为了节省项目的时间、金钱或劳动力--例如，对一座桥预计承载多少重量的启发式猜测可以用来确定该桥应该由木材、石头还是钢铁制成，在完成桥梁的精确设计时可以购买适当数量的所需材料。

然而，在某些技术性很强的领域使用启发式方法可能会造成损害--计算机科学就是一个例子。对计算机进行编程，使其或多或少地完成所需的动作，可能会导致严重的故障。因此，计算机任务一般必须相当精确。然而，在某些领域，计算机可以安全地计算启发式解决方案--例如，谷歌的搜索技术在很大程度上依赖于启发式方法，在找不到精确匹配的情况下产生 "近似 "的搜索查询匹配。这使用户能够纠正搜索中产生的任何错误。例如。在搜索 "彼得-史密斯 "这个名字时，如果找不到这个确切的名字，搜索引擎就会启发式地匹配 "彼得-史密斯"，而使用搜索引擎的人必须决定彼得和彼得是否是同一个人。

例子

波利亚

下面是其他一些常用的启发式方法，来自波利亚1945年出版的《如何解决》一书。

• 如果你在理解问题上有困难，可以尝试画图。
• 如果你找不到解决方案，可以试着假设你有一个解决方案，并看看你能从中推导出什么（"向后工作"）。
• 如果问题是抽象的，可以试着研究一个具体的例子。
• 先尝试解决一个更普遍的问题："发明家悖论"：更雄心勃勃的计划可能有更多的成功机会。

包装问题

启发式方法有用的一个例子是一种包装问题。这个问题包括包装一些物品。有一些规则需要被遵守。例如，每个物品都有一个价值和一个重量。现在的问题是以尽可能少的重量获得最有价值的物品。另一个例子是将一些不同大小的物品装入一个有限的空间，如汽车的后备箱。

为了得到问题的完美解决方案，必须尝试所有的可能性。这往往不是一个好的选择，因为尝试它们需要很长的时间，平均来说，必须尝试一半的可能性，直到找到一个解决方案。因此，大多数人的做法是，从最大的物品开始，把它装进去，然后尝试围绕它安排其他物品。在大多数情况下，这将提供一个良好的解决方案。然而，在有些情况下，这样的解决方案是非常糟糕的，必须使用另一种技术。

因此，这是一个启发式的解决方案。

一个包装问题的例子。这是一个一维（约束）Knapsack问题：应该选择哪些箱子来使金额最大化，并使总重量保持在15公斤以下？一个多维问题可以考虑箱子的密度或尺寸，后者是一个典型的包装问题。(在这种情况下，解决方案是选择除绿色箱子以外的所有箱子）。