启发式算法是解决问题的策略，在许多情况下，解决方案比不知情的搜索更快地找到解决方案。但是，这不能保证。启发式搜索可能需要更多时间，甚至可能导致找不到解决方案。
我们人类成功地将启发式过程用于各种事物。例如，在超市购买蔬菜时，我们只使用一些简单的标准来判断一磅草莓的各种选择，例如价格，外观，生产来源和对卖家的信任，然后我们通过以下方式决定最佳选择：直觉。理论上，在决定是否购买草莓之前，最好对草莓进行基础化学分析。例如，草莓可能会中毒。如果是这样的话，那么分析就是值得的
^ h EURISTIC小号EARCH（开始，目标）
NodeList = [开始]
虽然是真的
Node = First（NodeList）NodeList = Rest（NodeList）
如果GoalReached（节点，目标）返回（“找到解决方案”，节点）NodeList = SortIn（Successors（Node），NodeList）
如果NodeList =∅返回（“无解”）
图6.12 启发式搜索算法
麻烦。但是，我们不进行这种分析，因为我们的启发式选择很有可能成功，并且很快就会达到我们吃美味草莓的目标。
启发式决策与使用有限资源进行实时决策的需求密切相关。在实践中，快速找到的良好解决方案优于最佳解决方案，但是衍生起来非常昂贵。
用于状态的启发式评估函数f（s）用于数学地模拟启发式。我们的目标是以最小的总成本轻松找到解决所述搜索问题的方法。请注意，找到解决方案的努力与此解决方案的总成本之间存在细微差别。例如，从旧金山市政厅到约塞米蒂国家公园的Tuolumne Meadows，可能需要谷歌地图半秒钟的努力，但从旧金山乘车到Tuolumne
Meadows可能需要四个小时和一些钱汽油等（总成本）。
接下来，我们将通过向其添加评估函数来修改广度优先搜索算法。当前打开的节点不再按行从左到右扩展，而是根据其启发式评级。从开放节点集中，始终首先扩展具有最小评级的节点。这是通过在节点扩展时立即评估节点并将它们排序到开放节点列表中来实现的。然后，该列表可以包含树中不同深度的节点。
因为状态的启发式评估对于搜索非常重要，所以我们将从现在开始区分状态和它们的相关节点。节点包含状态和与搜索相关的其他信息，例如搜索树中的深度和状态的启发式评级。因此，生成节点的后继（子节点）的函数“Succes- sors”还必须立即为这些后继节点计算其启发式评级作为每个节点的组件。我们定义一般的搜索算法^ h EURISTIC小号EARCH
在图6.12。
使用起始节点初始化节点列表。然后，在循环中，删除列表中的第一个节点并测试它是否是解决方案节点。如果没有，它将使用“后继者”功能进行扩展，并将其后续添加到列表中
图6.13 他：“亲爱的，想想燃料成本！我会在别的地方为你挑一个。“她：”不，我想那个那边！“
使用“SortIn”功能。“SortIn（X，Y）”将未排序列表X中的元素插入到升序排序列表Y中。启发式评级用作排序键。因此，保证最佳节点（即具有最低启发值的节点）始终位于列表的开头。3
深度优先和广度优先搜索也恰好是函数H的特殊情况EURISTIC小号EARCH 。我们可以通过插入适当的评估函数轻松生成它们（第111 页的练习6.11）。
最好的启发式算法是计算从每个节点到目标的实际成本的函数。但是，要做到这一点，需要遍历整个搜索空间，这正是启发式应该防止的。因此，我们需要一种快速且易于计算的启发式算法。我们如何找到这样的一种神经病学？
找到启发式的一个有趣的想法是简化问题。原始任务已经足够简化，可以用很少的计算成本解决。从简化问题中的状态到目标的成本然后用作对实际问题的估计（参见图6.13）。这个成本估算函数我们表示h。
从当前可用状态列表中选择具有最低估计h值的状态（即，具有最低估计成本的状态）似乎是明智的。该
3 当从节点列表中对新节点进行排序时，检查节点是否已经可用是否有利，如果是，则删除副本。
图6.14 从所有城市到乌尔姆的飞行距离的城市图
然后，成本估算可以直接用作评估函数。对于在函数H的评价EURISTIC小号EARCH我们设置F（S）= H（S） 。这可以在行程计划示例中清楚地看到（第88 页的示例6.2）。我们设定了寻找的任务
从城市到城市的直线路径（即飞行距离）作为问题的简化。我们首先从每个节点确定与目标的飞行距离最小的路线，而不是搜索最佳路线。我们选择乌尔姆作为目的地。因此，成本估算函数变为
H（S）= 飞行距离从城市小号乌尔姆。
所有城市到乌尔姆的飞行距离如图 6.14 所示。
在林茨开始的搜索树在左边第 98 页的图 6.15中表示。我们可以看到树很纤细。搜索因此迅速完成。不幸的是，这种搜索并不总能找到最佳解决方案。例如，在曼海姆开始时，该算法无法找到最佳解决方案（第 98 页的图 6.15）对）。Mannheim-Nürnberg-Ulm路径长401公里。曼海姆 – 卡尔斯鲁厄 – 斯图加特 – 乌尔姆的路线将在238公里处显着缩短。当我们观察图表时，这个问题的原因就变得清晰了。纽伦堡实际上比卡尔斯鲁厄更接近乌尔姆，但从曼海姆到纽伦堡的距离远远大于从曼海姆到卡尔斯鲁厄的距离。启发式只能“贪婪地”向前看，而不是考虑已经放置到当前节点的拉伸。这就是为什么我们给它起名称贪婪的搜索。
|
|
|
|
|
|
|
|
|
|
|
|
|
图6.15贪婪搜索：从林茨到乌尔姆（左）和从曼海姆到乌尔姆（右）。节点列表数据结构为左搜索树，该节点的扩展之前由节点排名分类慕尼黑给出
2.
一个 -Search
我们现在要考虑的是，搜索到当前节点的过程中所累积的费用小号。首先，我们定义成本函数
g（s）= 从开始到当前节点的应计成本总和，
然后加上目标的估计成本并获得启发式评估函数
f（s）= g（s）+ h（s）。
现在我们又添加了一个小而重要的要求。
定义6.4启发式成本估算函数H（S） ，从来没有高估的队友从国家的实际成本小号的目标被称为受理。
=
函数H EURISTIC小号EARCH与评价函数一起F（S）
+
g（s）h（s）和可允许的启发函数h称为A – 算法。这个着名的算法是完整和最优的。 因此，A 始终为每个可解决的搜索问题找到最短的解决方案。我们将在下面的讨论中解释和证明这一点。
首先，我们将A 算法应用于示例。我们正在寻找从法兰克福到乌尔姆的最短路径。
图6.16 从法兰克福到乌尔姆的最佳路线的A搜索树的两个快照。在城市的名称下面的框中小号我们展示克（S） ， H（S）
， ˚F（S） 。城市名称后括号中的数字表示“后继”功能生成节点的顺序
在图6.16 的顶部，我们看到曼海姆的继承者是在维尔茨堡的继承者之前产生的。此后不久，在第八步中产生了最佳解决方案Frankfurt-Würzburg-Ulm，但尚未得到认可。因此，该算法尚未终止，因为节点Karlsruhe（3）具有更好（更低）的f值，因此在行中的节点Ulm（8）之前。只有当所有f值大于或等于解决方案节点Ulm（8）的f值时，我们才能确保我们拥有最优解。否则可能会有另一种成本更低的解决方案。我们现在将证明这一般是正确的。
定理6.2 A 算法是最优的。也就是说，如果启发式h是可接受的，它总是找到具有最低总成本的解决方案。
证明在H EURISTIC小号EARCH算法，每次新生成的节点小号根据其启发式等级函数“SortIn”排序在F（S）
。因此，具有最小评级值的节点位于列表的开头。如果节点l在
图6.17 A找到的第一个解决方案节点 l的 成本从未高于另一个任意节点 l
≤
列表的开头是解决方案节点，然后没有其他节点具有更好的启发式评级。对于所有其他节点š它为真，则该F（升）F（S） 。由于启发式是容许的，没有更好的解决升可以发现，即使所有其他节点的膨胀后（见图6.17）。正式书面：
g（l）= g（1）+ h（1）= f（1）≤f（s）= g（s）+ h（s）≤g（l）。
=
≤
第一个等式成立，因为l是h（l） 0的解决方案节点。第二个是f的定义。第三个（in）等式成立，因为打开节点列表按升序排序。第四个相等也是f的定义。最后，最后一个（不）平等是启发式，从未高估从节点的成本的可受理小号到任意溶液。因此，已经显示g（1）g（1），即，发现的溶液1是最佳的。
3. IDA –搜索
A 搜索从广度优先搜索继承了一个怪癖。它必须在内存中保存许多节点，这可能导致非常高的内存使用。此外，必须对打开的节点列表进行排序。因此，将节点插入列表并从列表中删除节点不再能够在恒定时间内运行，这会略微增加算法的复杂性。基于堆栈算法，我们可以将节点列表构造为具有对数时间复杂度的堆，用于插入和删除节点（参见[CLR90]）。
这两个问题都可以解决 – 类似于广度优先搜索 – 迭代加深。我们使用深度优先搜索并连续提高限制。然而，在这里，我们使用启发式评估f（s）的限制，而不是使用深度限制。此过程称为IDA 算法。
4. 搜索算法的实证比较
在A 或（或者说）IDA中
，我们有一个具有许多良好属性的搜索算法。它是完整和最佳的。因此可以无风险地使用它。然而，最重要的是它与启发式算法一起使用，因此可以显着减少找到解决方案所需的计算时间。我们想在8个拼图的例子中进行经验探索。
对于8-puzzle，有两个简单的可接受的启发式算法。启发式h 1只计算不在正确位置的方块数。很明显，这种启发式是可以接受的。启发式h 2测量曼哈顿距离。每一个
表6.2 不知情搜索和启发式搜索的计算成本与不同深度的可解决8-puzzle问题的比较。测量分为几步和几秒。所有值均为多次运行的平均值（参见上一栏）
深度迭代加深 算法Num。
步时间[秒]
启发式h 1
启发式h 2
步时间[秒]步时间[秒]
运行
|
2 |
20 |
0 。003 |
3 。0 |
0 。0010 |
3 。0 |
0 。0010 |
10 |
|
4 |
81 |
0 。013 |
5 。2 |
0 。0015 |
5 。0 |
0 。0022 |
24 |
|
6 |
806 |
0 。13 |
10 。2 |
0 。0034 |
8 。3 |
0 。0039 |
19 |
|
8 |
6455 |
1 。0 |
17 。3 |
0 。0060 |
12 。2 |
0 。0063 |
14 |
|
10 |
50512 |
7 。9 |
48 。1 |
0 。018 |
22 。1 |
0 。011 |
15 |
|
12 |
486751 |
75 。7 |
162 。2 |
0 。074 56 。0 0 。031 |
12 |
||
|
IDA |
|||||||
|
14 |
– |
– |
10079 。2 |
2 。6 855 。6 0 。25 |
16 |
||
|
16 |
– – |
19 。0 |
3806 。五 |
1 。3 |
13 |
||
|
18 |
– – |
161 。6 |
53941 。五 |
14 。1 |
4 |
||
平方将目标状态中该方块位置的水平和垂直距离相加。然后将该值在所有平方上求和。例如，两个州的曼哈顿距离
按计算
h 2 （s）= 1 + 1 + 1 + 1 + 2 + 0 + 3 + 1 = 10 。
曼哈顿距离的可接受性也很明显（参见第 111 页的练习 6.13 ）。
所描述的算法在Mathematica中实现。为了与不知情的搜索进行比较，将 具有两个启发式h 1和h 2以及迭代加深的A 算法应用于132个随机生成的8-puzzle问题。表6.2 给出了步数和计算时间的平均值。我们看到，与未经形成的搜索相比，启发式方法显着降低了搜索成本。
例如，如果我们将迭代加深与A 与深度12处的h 1 进行比较，则很明显h
1将步数减少了约3,000倍，但计算时间仅减少了1,023倍。这是由于计算启发式的每步成本较高。
仔细检查发现h 1 栏中深度12和深度14之间的步数跳跃。这种跳跃不能仅仅由IDA的重复工作来解释 。它的出现是因为A 算法的实现
删除相同节点的重复项，从而缩小搜索空间。IDA无法实现这一点， 因为它几乎不会节省任何节点。尽管如此，A还是
不能再与IDA 超越14深度竞争，因为新节点中的排序成本会大大增加每个步骤的时间。
有效分支因子的根据（A计算 6.1 ）页上的 87 产生约2.8不知情搜索值。这个数字与Sect的值一致。6.1 。启发式h 1将分支因子降低至约1.5和h 2至约1.3的值。我们可以在表中看到，分支因子从1.5到1.3的小幅降低使我们在计算时间方面具有很大的优势。
因此，启发式搜索具有重要的实际意义，因为它可以解决对于不知情的搜索而言遥不可及的问题。
5.
摘要
在用于不知情搜索的各种搜索算法中，迭代加深是唯一实用的搜索算法，因为它是完整的并且可以用非常少的内存来获得。然而，对于困难的组合搜索问题，由于搜索空间的大小，甚至迭代加深通常也会失败。启发式搜索通过减少有效分支因子来帮助实现这一目标。 与迭代加深一样，IDA 算法是完整的，只需要很少的内存。
如果启发式“好”，启发式自然只会给出显着的优势。在解决困难的搜索问题时，开发人员的实际任务包括设计启发式算法，这大大降低了有效的分支因子。在Sect。6.5 我们将处理这个问题，并展示如何使用机器学习技术自动生成启发式算法。
