下载掌阅APP，畅读海量书库
立即打开
问题求解的方法已被应用于大量任务环境中。我们在这里列出一些典型问题，区分为标准化问题和真实世界问题。 标准化问题 （standardized problem）常用于说明或训练各种问题求解方法。它具有简洁、准确的描述，因此适合作为研究人员比较算法性能的基准。 真实世界问题 （real-world problem），如机器人导航，则意味着这一问题的解是人们实际使用的，且问题的形式化是独特的而非标准化的，因为例如在机器人导航问题中，每个机器人具有不同的传感器，产生不同的数据。
网格世界 （grid world）问题是一个由正方形单元格组成的二维矩形阵列，在这个阵列中，智能体可以从一个单元格移动到另一个单元格。一般来说，智能体可以水平或垂直地移动到任何无障碍的相邻单元格，在某些问题中还可以沿对角线移动。单元格中可以包含智能体能拿起、推开或施加其他动作的物体，也可以存在阻止智能体进入单元格内的墙壁或其他不可逾越的障碍。2.1节中的 真空吸尘器世界 （vacuum world）可以表示为一个网格世界问题。
● 状态： 即哪些对象在哪些单元格中。在真空吸尘器世界中，对象就是智能体和灰尘。对于只有两个单元格的简单情形，智能体可以位于这两个单元格中的任何一个，每个单元格都可能存在灰尘，所以共有2×2×2 = 8个状态（见图3-2）。一般来说，存在 n 个单元格的真空吸尘器环境有 n ×2 n 个状态。
● 初始状态： 任一状态都可以被指定为初始状态。
● 动作： 在只有两个单元格的情形中，我们可以定义3种动作，即吸尘（ Suck ）、向左（ Left ）移动和向右（ Right ）移动。在二维多单元格世界中，我们则需要更多种移动动作。我们可以增加向上（ Upward ）和向下（ Downward ）的动作，从而得到4种 绝对的 （absolute）移动动作，或者可以将其转换为 以自我为中心的动作 ，即从相对于智能体的角度来定义，例如，向前（ Forward ）、向后（ Backward ）、右转（ TurnRight ）和左转（ TurnLe ft ）。
● 转移模型： Suck 将去除单元格内的任何灰尘； Forward 将智能体朝它所面对的方向向前移动一个单元格，除非它撞到墙（在这种情况下，这个行动不起作用）。 Backward 让智能体朝相反的方向移动一个单元格，而 TurnRight 和 TurnLeft 则将智能体的朝向旋转90°。
● 目标状态： 每个单元格都保持干净的状态。
● 动作代价： 每个动作的代价都是1。
图3-2 两个单元格的真空吸尘器世界的状态空间图。共有8个状态，每个状态有3种动作： L = Left （向左）、 R = Right （向右）、 S = Suck （吸尘）
另一种类型的网格世界是
推箱子问题
（sokoban puzzle），在这个问题中，智能体的目标是将一些散落在网格中的箱子推到指定的存储位置。每个单元格最多容纳一个箱子。当智能体向前移动到放有一个箱子的单元格，而箱子另一侧的单元格为空时，箱子和智能体都向前移动一格。智能体不能把一个箱子推到另一个箱子上或墙上。对于存在
n
个无障碍单元格和
b
个箱子的世界，共有
个状态；例如，在一个存在12个箱子的8×8网格中，有超过200万亿个状态。
在 滑块问题 （sliding-tile puzzle）中，若干滑块（有时称为块或片）排列在一个有若干空白区域的网格中，其中滑块可以滑进空白区域。它的一个变体是汽车华容道问题（Rush Hour puzzle），在这个问题中，我们需要在6×6的网格中滑动汽车和卡车，目标是将一辆汽车从交通堵塞中解救出来。滑块问题中最著名的变体是 8数码问题 （8-puzzle）（见图3-3），它由一个3×3的网格、8个带编号的滑块和一个空格组成，目标是达到指定的状态，如图3-3中右侧所示。类似的还有由4×4的网格组成的 15数码问题 （15-puzzle）。对8数码问题做如下形式化处理。
● 状态： 指定每个滑块位置的状态描述。
● 初始状态： 任何状态都可以被指定为初始状态。注意，可以根据奇偶性划分状态空间——任何给定目标都可以从恰好一半的可能初始状态到达（见习题 3.PART）。
● 动作： 虽然在真实世界中是滑块在移动，但描述动作的最简单方法是假设空格执行 Left 、 Right 、 Up 或 Down 动作。如果空格位于边缘或角落，则不是所有的动作都可用。
● 转移模型： 将状态和动作映射为一个结果状态；例如，图3-3中，对于初始状态，我们采取 Left 动作，那么结果状态中滑块5和空格将交换位置。
● 目标状态： 尽管任何状态都可以作为目标状态，但我们通常用有序编号指定目标状态，如图3-3所示。
● 动作代价： 每个动作的代价都为1。
注意，每个问题的形式化都涉及抽象。8数码问题中的动作被抽象为它们的开始状态和结束状态，忽略滑块滑动的中间位置。我们已经通过抽象除去了一些动作，例如，当滑块被卡住时需要晃动木板，并排除了用刀取出滑块然后再放回去的可能性。最终只剩下对规则的描述，避免了实际操作的所有细节。
图3-3 8数码问题的一个典型实例
我们介绍的最后一个标准化问题是由高德纳（Knuth, 1964）设计的，它说明了无限状态空间是如何产生的。高德纳推测，通过只由平方根、向下取整和阶乘操作组成的序列可以从数字4得到任何正整数。例如，我们可以这样从4得到5：
问题定义很简单，如下所述。
● 状态： 正实数。
● 初始状态： 4。
● 动作： 应用平方根、向下取整或阶乘操作（阶乘仅用于整数）。
● 转移模型： 根据运算的数学定义给出。
● 目标状态： 所求的正整数。
● 动作代价： 每个动作的代价都是1。
这一问题的状态空间是无限的：对于任意大于2的整数，阶乘操作总是产生一个更大的整数。这个问题很有趣，因为它探索了非常大的数字：从4到5的最短路径生成了数字(4!)! = 620 448 401 733 239 439 360 000。无限状态空间经常出现在涉及数学表达式生成、电路、证明、程序和其他递归定义对象的任务中。
我们已经了解了如何根据指定的位置和沿着它们之间的边进行的位置转移来定义 寻径问题 （route-finding problem）。寻径算法有许多应用场景。其中一些是上文中罗马尼亚例子的直接扩展，例如提供导航的网站和车载系统等。（需要考虑的主要复杂因素是因与交通相关的延迟而导致的代价变化，以及因道路封闭而导致的路线变更。）另一些例如计算机网络中的视频流路由、军事行动规划和飞机航线规划系统等，则更加复杂。下面介绍旅行规划网站必须解决的航空旅行问题。
● 状态： 每个状态显然包括当前位置（例如，某个机场）和当前时间。此外，由于每个动作（一个航段）的代价可能依赖于之前的航段、票价基础以及它们是国内航班还是国际航班，状态必须记录这些额外的“历史”信息。
● 初始状态： 用户家所在的机场。
● 动作： 在当前时间之后，从当前位置乘坐任意航班任意舱位起飞，如果需要，还要留出足够的时间在机场中转。
● 转移模型： 乘坐航班产生的结果状态将航班的目的地作为新的当前位置，将航班的到达时间作为新的当前时间。
● 目标状态： 目的地城市。有时目标可能更复杂一点，例如“乘坐直达航班到达目的地”。
● 动作代价： 金钱成本、等待时间、飞行时间、海关和入境手续、舱位质量、当日时间、飞机类型、常旅客奖励积分等的组合。
商业旅行咨询系统使用的就是上述问题的形式化。不过，在处理航空公司错综复杂的票价结构时，还会有许多额外的复杂因素。例如，任何有经验的旅行者都知道，并不是所有的航空旅行都能按计划进行。因此，一个真正好的系统应该包括应变规划——如航班延误或者错过转机时的应对方案。
旅行问题 （touring problem）描述的是一组必须访问的地点，而非单一目的地。 旅行商问题 （traveling salesperson problem，TSP），就是一个旅行问题，即地图上每个城市都必须被访问。其目标是找到代价小于 C 的旅行路线（在优化版本中，目标是找到代价最低的旅行路线）。为了提高TSP算法的性能，科研人员付出了大量的努力。该算法也可以扩展到处理车队问题。例如，规划波士顿校车路线的搜索优化算法为人们节约了500万美元，减少了交通拥堵和空气污染，同时还为司机和学生节省了时间（Bertsimas et al. , 2019）。除了规划行程，搜索算法还被用于规划自动电路板钻孔机钻头的运动和装料机在车间内的移动等任务。
超大规模集成电路布图 （VLSI layout）问题需要在一个芯片上定位数百万个元件和连接点，以最小化芯片面积、电路延迟和杂散电容，并最大化成品率。布图问题在逻辑设计阶段之后，通常分为两个部分： 单元布图 （cell layout）和 通道布线 （channel routing）。在单元布图中，电路的基本元件分组为若干单元，每个单元执行一些特定功能。每个单元都有固定的占用区域（大小和形状），并且需要与其他每个单元建立一定数量的连接。单元布图的目的是将单元彼此不重叠地放置在芯片上，并且单元之间有足够的空间布置连线。通道布线的目的则是通过单元之间的间隙为每条导线寻找特定的路线。这些搜索问题极其复杂，但绝对值得研究。
机器人导航 （robot navigation）是寻径问题的一个推广。机器人不必沿着明确的路径（如罗马尼亚的道路）行走，而是可以四处游走，实际上是自己走自己的路。对于在平面上移动的圆形机器人，空间本质上是二维的。当机器人的手臂和腿也必须受到控制时，搜索空间就变成了多维的——每个关节角都是一个维度。为了使基本上连续的搜索空间变成有限空间，需要一些更先进的技术（见第26章）。除了问题的复杂性外，真正的机器人还必须处理传感器读取错误、电动机控制中的错误、部分可观测性以及可能改变环境的其他智能体等问题。
自20世纪70年代以来，由机器人对复杂物体（例如电动机）进行 自动装配排序 （automatic assembly sequencing）已成为标准的工业实践。算法首先找到一个可行的装配序列，然后对装配过程进行优化。将装配线上的人工劳动减少到最低限度可以节省大量时间和成本。装配问题的目标是找到某个对象的各个零件的组装顺序。如果顺序错误，那么只能撤消某些已完成的工序，否则无法在序列的后面添加其他部分。检查序列中动作的可行性是与机器人导航问题密切相关的几何搜索难题。因此，合法动作的生成是装配排序问题中代价较高的部分。任何实用算法都必须尽量避免探索全部的状态空间，而应只探索状态空间中的很小一部分。一类重要的装配问题是 蛋白质设计 （protein design），其目的是找到一种氨基酸序列，该序列能够折叠成具有正确特性的三维蛋白质结构，以治疗某些疾病。