现实世界问题

我们已经看到寻径问题是如何根据特定的位置和沿它们之间的连接进行的转移而定义的。寻径算法在实际中有许多不同的应用，诸如计算机网络的路由、军事行动的规划，以及飞机航线旅行规划系统。这些问题都是典型的描述起来很复杂的问题。考虑一个飞机航线旅行问题的简化例子，设定如下：

状态：每个状态由位置（例如机场）和当前的时间来表示。

初始状态：由具体问题而定。

后继函数：返回的状态是下列因素的结果：乘坐的航班（可能会进一步由座位等级及位置决定），起飞时刻距当前时刻的时间差加上从当前的机场到另一个机场所需要的飞行时间。

目标测试：我们是否在某个预定时间内到达了目的地？

路径耗散：取决于金钱的花费、等待的时间、飞行时间、过海关和入境的过程、座位的质量、一天中的哪个时间段、飞机类型、飞行常客的里程奖，等等。

商业旅行建议系统使用了这种问题形式化的方法，同时要考虑很多附加的复杂因素以应付航空公司强加的繁复的收费结构。然而，任何经常坐飞机的乘客都知道并不是所有的飞行旅行都能按计划顺利进行。一个真正的好的系统应该包括应急计划——诸如预定可供选择的其它航班作为后备——这些扩展计划要由所需要的花费和原始计划失败的可能性来判定是否合适。

旅行问题与寻径问题有很近的关系，但是有很重要的区别。例如，考虑“访问图 3.2 中的每个城市至少一次，要求以Bucharest为起点和终点”这样一个问题。如寻径一样，行动还是对应于临近城市间的旅行。然而，状态空间就非常不一样了。每个状态不仅必须包括当前所在的位置，还必须包括智能体已经访问过的城市集合。因此初始状态应该是“In Bucharest; visited {Bucharest}”，一个典型的中间状态可能是“In Vaslui; visited {Bucharest, Urziceni, Vaslui}”，而目标测试应该是检测智能体是否在Bucharest并且已经访问过所有的20个城市。

旅行商问题（TSP）是每个城市都只能被访问一次的旅行问题。它的目标是找到最短的路程。这个问题已知是NP难题，但还是有很多人做了大量的努力来提高TSP算法的能力。除了为旅行商规划旅程之外，旅行商算法还用于诸如规划电路板的自动钻孔机的运动和规划商店库房的货物码放机器的运动这样的问题。

超大规模集成电路的布局问题要求在一个芯片上放置上百万个元器件以及连线，还要达到芯片面积最小、电路延迟最小、杂散电容最小和产量最大的要求。这个布线问题出现在逻辑设计阶段之后，通常被划分为两部分：单元布局和通道寻径。在单元布局中，基本的电路元器件被分组安排在各单元中，每个单元履行某个经过验证的功能。每个单元都有固定的占用区域（大小和形状）并需要和其它单元之间有一定数量的连线。目标是能把这些单元不重叠地放置在芯片上并且留有足够的空间来布设单元之间的连线。通道寻径要为每一条导线找到通过单元之间的缝隙的特定路径。这些搜索问题是极端复杂的，但无疑是值得解决的。在第四章中，我们将看到一些有能力解决这类问题的算法。

机器人导航问题是前面所述的寻径问题的推广。与寻找离散的路径集不同，机器人可以在连续的空间上运动并且（原则上）可能的行动和状态的集合都是无限的。对于一个在平面上往复运动的机器人来说，空间基本上是二维的。当机器人有需要控制的机器臂、机器腿或者轮子的时候，搜索空间就变成很多维的了。因此需要先进的技术来使它的搜索空间有限。我们将在第二十五章中考察一些这样的技术。除了问题的复杂性之外，真实机器人还必须处理传感器读入和发动机控制的错误。

由机器人完成复杂物体的自动装配排序问题最早是由 FREDDY（Michie，1972）演示的。从那时起这个问题的研究进展一直是缓慢而可靠的，在装配诸如电动机这样的复杂物体方面已经达到经济上可行的程度。在装配问题中，目标是找到一个装配物体各个部件的次序。如果选择了一个错误的装配次序，迟早会遇到无法安装序列中的下一个零件的情况，只能撤消前面已完成的工作。检查安装序列中的某一步的可行性是一个近似于机器人导航问题的困难的几何搜索问题。因此，产生合法后继是装配排序中开销最大的部分。任何实用算法都必须避免搜索所有的状态空间而只是搜索其中的很小一部分。另外一个重要的装配问题是蛋白质设计问题，它的目标是寻找一个氨基酸的序列，该序列叠放在三维的蛋白质结构里，具有能够治愈某些疾病的合适特性。

近几年，对软件机器人的需求在不断增长，它能够完成因特网搜索，寻找问题的答案、相关信息，或者购物交易信息。这是搜索技术的一个很好的应用，因为我们可以很容易把因特网概念化为一个通过链接联系起来的节点（网页）构成的图。对于因特网的搜索的全面描述将放在第十章中讨论。