在极大的搜索树中搜索解决方案几乎对所有推理系统都存在问题。从起始状态开始，第一推理步骤有很多可能性。对于这些可能性中的每一种，下一步还有许多可能性，依此类推。即使是来自[Ert93]的一个非常简单的公式的证明，其中有三个Horn子句，每个子句最多有三个文字，SLD分辨率的搜索树具有以下形状：
*
树被切断，深度为14，并在叶节点上标有溶液。由于最多两个的分支因子较小以及在深度14处的截止，因此只能表示它。对于实际问题，第一个解决方案的分支因子和深度可能会变得非常大。
≈×
假设分支因子是等于30的常数，第一个解是深度50.搜索树有30
50 7 。2 10 73个叶节点。但是推理步骤的数量甚至更大，因为不仅每个叶节点，而且树的每个内部节点都对应于推理步骤。因此，我们必须在所有级别上添加节点并获得搜索树的节点总数
50 51
1 – 30
30 d = 1 – 30 = 7 。4 × 1073 ，
d = 0
d = 0
×
这不会改变节点数量。显然，这个搜索树的几乎所有节点都在最后一级。正如我们将要看到的，通常就是这种情况。但现在回到7的搜索树。4 10 73个节点。假设我们有10,000个计算机，每个计算机每秒可以执行十亿次推理，我们可以
W. Ertel，人工智能导论，83
计算机科学本科专业，
DOI 10.1007 / 978-0-85729-299-5_6，©Springer-Verlag
London Limited 2011
在所有计算机上免费分配工作。所有7的总计算时间。4 × 10 73个推论约等于
7 。4 × 10 73个推论10000 × 10 9个推论/秒
= 7 。4 × 1060
秒≈ 2 。3 × 1053
年，
这是我们宇宙时代的10 43倍。通过这种简单的思考练习，我们可以很快发现，在这个世界上我们可以利用的手段完全搜索这种搜索空间是不可能的。此外，与搜索空间大小相关的假设是完全现实的。例如，在国际象棋中，对于典型情况，有超过30种可能的移动，持续50次半转的游戏相对较短。
那怎么可能，那里有优秀的国际象棋选手 – 而且现在也是好的国际象棋电脑？数学家如何找到搜索空间更大的定理的证明？显然，我们人类使用智能策略，大大减少了搜索空间。经验丰富的国际象棋选手，就像经验丰富的数学家一样，只要观察情况，就会立即排除许多无意义的行为。通过他的经验，他有能力评估各种行动，以实现其实现目标。通常，一个人会感受到。如果有人向数学家询问他是如何找到证据的，那么他可能会回答在梦中他的直觉。在困难的情况下，许多医生根据所有已知症状找到纯粹基于感觉的诊断。特别是在困难的情况下
通常没有正式的解决方案理论可以保证最优的解决方案。在日常问题中，例如在图1中寻找一只失控的猫。第 85 页的 6.1 ，直觉起着重要作用。我们将在Sect中处理这种启发式搜索方法。6.3 并且另外描述了计算机可以与人类类似地通过学习改进其启发式搜索策略的过程。
然而，首先，我们必须了解不知情的搜索，即盲目地尝试所有可能性，是如何工作的。我们从几个例子开始。
×
示例6.1使用8-puzzle（搜索算法的典型示例[Nil98，RN10]），可以非常明显地说明各种算法。数字1到8的正方形分布在一个3 3矩阵中，如第
86页的图 6.2所示。目标是达到方块的某个排序，例如按行按升序排列，如第 86页的图 6.2所示。在每个步骤中，正方形可以向左，向右，向上或向下移动到空白区域。因此，空的空间在相应的相反方向上移动。为了分析搜索空间，总是可以方便地查看空场的可能移动。
用于起始状态的搜索树在第 86 页的图 6.3中表示。我们
可以看到，两个，三个，和之间的分支因子候补√ FO Ú河 平均
过在一个时间两个层次，我们得到的平均支化因子1的8 ≈ 2 。我们
看到每个状态被重复多次两次，因为在一个简单的不知情的搜索中，每个动作都可以在下一步中被反转。
1 树的平均分支因子是具有恒定分支因子，相等深度和等量叶子节点的树的分支因子。
如果我们不允许长度为2的循环，那么对于相同的起始状态，我们获得第 86 页的图 6.4 中所示的搜索树。平均分支因子减少约1并变为1.8。2
2 对于8拼图，平均分支因子取决于起始状态（参见第 110 页的练习 6.2 ）。
图6.2 8拼图的可能起始和目标状态
图6.3 8拼图的搜索树。右下角表示深度为3的目标状态。为了节省空间，已省略此级别的其他节点
图6.4 没有长度为2的循环的8拼图的搜索树
=
=
在我们开始描述搜索算法之前，需要一些新术语。我们在这里处理离散搜索问题。作为在状态小号，一个动作一个 1所导致一个新的状态小号。因此sa 1 （s）。一个不同的动作可能导致状态s，换句话说：sa
2 （s）。从起始状态开始，将所有可能的动作递归应用到所有状态，产生搜索树。
定义6.1 搜索问题由以下值定义
状态：描述搜索代理发现自身的世界状态。
启动状态：启动搜索代理的初始状态。
目标状态：如果代理达到目标状态，则终止并输出解决方案（如果需要）。
操作：所有代理都允许操作。
解决方案：搜索树中从开始状态到目标状态的路径。
成本函数：为每个操作分配成本值。寻找成本最优解决方案是必要的。
州空间：所有州的集合。
适用于8拼图，我们得到
×
状态：3 3矩阵 S ，其值为1,2,3,4,5,6,7,8（每个一次）和一个空方块。
开始状态：任意状态。
目标状态：任意状态，例如第 86 页的图 6.2中右侧的状态。
= =
= =
动作：空方 Sij 向左移动（如果是 j 1），向右移动（如果是 j 3），向上移动（如果是 i 1），向下移动（如果是 i 3）。
成本函数：常数函数1，因为所有操作都具有相同的成本。
状态空间：状态空间在相互无法访问的域中是退化的（第
110 页的练习 6.4 ）。因此，存在无法解决的8-puzzle问题。
§ 具有n个总节点的深度为d的树的有效分支因子是
b（s），或 b，如果分支因子是常数。
要分析搜索算法，需要以下术语：
定义6.2
§ 状态s的后继状态的数量称为分支因子
定义为具有恒定分支因子，相等深度和相等n 的树将具有的分支因子（参见第 110 页的练习 6.3 ）。
能干的问题。如果完整的搜索算法在没有找到解决方案的情况下终止，则问题无法解决。
§ 如果搜索算法找到每个解决方案的解决方案，则称其为完成
对于给定的深度d和节点数n，可以通过求解该等式来计算有效分支因子
–
=
b d + 1
1
n （6.1）
b – 1
图6.5 德国南部的图表，作为具有成本函数的搜索任务的示例
对于b，因为具有恒定分支因子和深度d的树总共具有
d
n =
i = 0
bi =
b d +
1 – 1
b – 1
（6.2）
对于有限搜索树的搜索算法的实际应用，最后一级尤其重要，因为
定理6.1对于具有大常数分支因子的重分支有限搜索树，几乎所有节点都在最后一级。
这个定理的简单证明作为练习推荐给读者（第
110 页的练习 6.1 ）。
例6.2 我们给出了一个地图，例如图6.5 中所示的地图，作为城市作为节点和城市之间的公路连接作为距离加权边的图。我们正在寻找从 A 市到 B 市的最佳路线。相应模式的描述读取
州：一个城市作为旅行者的当前位置。
开始状态：任意城市。
目标状态：任意城市。
行动：从当前城市到邻近城市旅行。
成本函数：城市之间的距离。每个动作对应于图中的边，其中距离为权重。
状态空间：所有城市，即图的节点。
要找到长度最小的路线，必须考虑成本，因为它们不像8拼图那样是不变的。
定义6.3如果搜索算法存在解决方案，则总是找到成本最低的解决方案，因此称为最优搜索算法。
8拼图问题是确定性的，这意味着每个动作都从一个状态导向一个独特的后继状态。此外，可观察到的是，代理总是知道它处于哪种状态。在实际应用中的路径规划中，并不总是给出特征。“ 从慕尼黑开车到乌尔姆 ” 的行动可能 – 例如由于事故 – 导致继承国“ 慕尼黑 ”。也可能发生旅行者不再知道他在哪里因为他迷路了。我们首先要忽略这些并发症。因此，在本章中，我们将只讨论确定性和可观察性的问题。
像8拼图这样具有确定性和可观察性的问题使得行动计划相对简单，因为由于具有抽象模型，可以找到解决问题的动作序列而无需在现实世界中实际执行动作。在8拼图的情况下，没有必要实际移动现实世界中的方块以找到解决方案。我们可以通过所谓的离线算法找到最佳解决方案。例如，当建造应该踢足球的机器人时，人们面临着不同的挑战。这里永远不会有一个确切的行动抽象模型。例如，在特定方向上踢球的机器人不能确定地预测球将在哪里移动，因为除了其他之外，它不知道对手是否会抓住或偏转球。在这里，需要在线算法，根据每种情况下的传感器信号做出决策。强化学习，见Sect。10，致力于根据经验优化这些决策。
